Machine de Turing, ai-je tout compris?

[Tengri]

Bonsoir,

Ayant fait philo et me plongeant régulièrement dans la philosophie de l'esprit, j'ai été amené à me pencher sur la fameuse machine de Turing (je n'ai jamais eu cours dessus).

le problème est que lorsque l'on cherche sur internet des explications claires du fonctionnement de cette machine abstraite, on ne trouve quasi aucune ressource suffisamment claire et pédagogique. beaucoup de chiffres en tous sens, emplois de termes pas toujours définis, etc.

par exemple wikipedia me semble un sommet d'info incompréhensibles

Je suis parvenu à y voir plus clair à force de recoupements

on a une machine constituée d'un ruban parfois infini parfois non, (ça dépend des modèles). ce ruban étant placé sous une tête de lecture écriture . Une table de transition et un programme donnent des instructions à la machine qui a la capacité donc d'écrire et d'effacer sur le ruban . Donc machine à transmettre de l'information et à la formaliser, d'où sa position de l’ancêtre de l'ordinateur.

exemple:

Dans état e0 la machine va forcément écrire A et se déplacer à gauche d'une case, puis passer en e1

puis:

e1 (B;à gauche) passage vers e2
e2 (C; à droite) -------------- e3
e3(D; à gauche) -------------- e0

Donc un programme très court et circulaire vu que ici la machine ne s’arrête jamais. J'aurais pu tout aussi bien le faire sur 10 ou 35 lignes et décider pour que ce ne soit pas infini que la machine s’arrête à mettons e15. e14 prévoit alors une lettre mais aucun déplacement ni nouvel état (déplacement et état étant indissociables au fond...)

Et c'est là une machine de Turing pure; L'universelle serait une machine à capacité d'exécuter ce programme mais aussi d'autres, peut être une infinité.

Ai je tout bien compris?

Merci de votre aide
-----

[Garion]

On peut dire que c'est la machine la plus simple capable d’exécuter n'importe quel algorithme.
Mais ce n'est surement pas la plus efficace

[Deedee81]

Salut,

Ai je tout bien compris?

Tout ça me semble correcte, peut-être par trop clair ni complet mais juste.

La présentation ici est pas mal je trouve : http://zanotti.univ-tln.fr/turing/
ou ici : https://librecours.net/module/cultur...e-turing.xhtml

Il faut bien comprendre aussi que la "machine" de Turing était initialement un objet mathématique purement abstrait (et encore maintenant même si on en a réalisé en vrai).
C'est une façon de modéliser de manière très élémentaire les principes de calcul et d'algorithme.
Il a même des liens avec https://fr.wikipedia.org/wiki/Lambda-calcul dont tu peux voir le coté particulièrement abstrait (notons qu'il a inspiré un truc concret que j'aime beaucoup : le langage de programmation Lisp, j'en avais réalisé de interpréteurs en C++, je m'étais surtout penché sur un mécanisme de "garbage collector" automatique et se faisant au fur et à mesure de manière efficace, qu'est-ce que j'ai pu m'amuser avec le Lisp ).

Ceci explique donc la présentation parfois abstraites et peu lisibles aux non mathématiciens dans certains cas, comme Wikipedia. Il y a même des versions avec "oracle" et compagnie (difficile de trouver un oracle dans le monde réel ).

On démontre l'universalité de la machine de Turing (au moins pour un ruban infini, je ne sais pas si la démonstration existe pour un ruban fini ou un théorème équivalent).
https://fr.wikipedia.org/wiki/Machin...ng_universelle (plus compréhensible que l'autre lien wikipedia)
on démontre qu'une machine de Turing peut calculer tout algorithme déterministe quel qu'il soit. Et on peut même créer un programme qui prend en entrée des données et un autre programme/algo et qui simule cet algo. Donc UNE machine avec UN programme capable de calculer tout ce qui est calculable.

Le point remarquable est qu'on peut alors démontrer que tout algorithme n'est pas réalisable. Ou plus précisément qu'il existe des fonctions non calculables (dans un sens précis). Et c'est généralement basé sur le problème de l'arrêt.
https://fr.wikipedia.org/wiki/Probl%...l%27arr%C3%AAt
un cours assez complet : http://www.discmath.ulg.ac.be/cours/main_calcul.pdf
Un exemple que j'avais beaucoup aimé était la fonction F(n) = le plus grand nombre qu'on peut écrire avec n chiffres (après avoir précisé quelques règles d'écriture et en excluant les formulations paradoxales). Cette fonction croit incroyablement vite ce qui est souvent caractéristique des fonctions non calculables.

Ce genre de travail entre aussi dans le cadre des indécidabilités : théorèmes de complétude et incomplétude (on peut dire que c'est assez complémentaire de la calculabilité).
Le fameux problème de l'hydre de Lerne indécidable en ZFC a clairement des liens avec l'algorithmique. https://fr.wikipedia.org/wiki/Th%C3%...e_de_Goodstein

Par contre cela n'aide pas beaucoup pour la complexité. La conjecture P=NP (un million de dollars à la clef ) utilise une machine de Turing pour sa formulation mais le résoudre.... c'est tout autre chose !!!! (comme dit Garion Turing c'est pas le plus efficace, l'universalité concerne ce que peut faire une machine pas son efficacité).
Ca entre aussi dans le cadre de la théorie des automates finis : https://fr.wikipedia.org/wiki/Th%C3%..._des_automates
j'avais vu un très bon cours au début de l'ère internet mais pour le retrouver, aie. Mais j'ai trouvé ceci : http://deptinfo.cnam.fr/~barthe/NFP1...-automates.pdf pas aussi complet mais très bien.

Bref c'est un domaine, vaste, avec pleins de ramifications et très passionnant

Bonnes lectures (si ça te dit).

[Tengri]

Oulalala tout ça va créer encore plus de questions

J'ai de la lecture en effet.

je n'ai pas tout compris dans ce que tu as écrit : je n'ai aucune formation scientifique , j'ai fait L et ensuite master de philo. Il se peut que je me décide à tenter l'agrégation mais comme je me sens encore trop fragile sur bien des points je repousse, parmi ces points logique-épistémologie-philosophie de la connaissance .

Donc je suppose que tout ce que tu as écrit ressortit plus à des études de maths-logique que de philo. En philo on nous demande de connaitre principes, théories, sans rentrer dans du technique (au sens mathématique du terme), c'est pourquoi je cherche sur Turing des explications à tonalité plutôt littéraire. Les frontières sont brouillées: j'ai eu un prof de logique épistémologie à la fac qui était titulaire aussi d'une licence de maths, à certains moment le discours devenait trop ardu pour non initié...

Quand tu dis que ce n'est pas assez clair ou complet, tu veux dire d'un point de vue études de maths-logique? Ayant fait que philo je doute de pouvoir aller , pour comprendre Turing, au dela de ce que j'ai écrit.

Alors justement, parmi l'ensemble des trucs que j'ai pu consulter, il y en a un qui m'a particulièrement frappé: https://www.youtube.com/watch?v=F9jjj0TaaKI

A partir de 1:30 apparait un schéma dont je ne comprends pas iun traitre mot...

Pourtant jusque là ce que dit ce jeune homme est clair. Mais lorsqu'il commente le schéma je trouve que ça n'a aucun sens: f(n)=2n ne pose en soi aucune difficulté je connais depuis la troisième. Mais quel rapport entre ça et la table de transition montrée juste après ? J'ai soigneusement suivi la table de transition, je ne trouve absolument pas 1111 à l'arrivée

vraiment je comprends pas...

[A voir en vidéo sur Futura]

[ThM55]

Si vous lisez l'anglais, il y a une ressource de bonne qualité, c'est le site "Stanford Encyclopedia of Philosophy". Ils sont assez bon pour ce genre de sujet (la logique est bien enseignées dans les facs de philosophie anglo-saxonnes, question de tradition sans doute). Voir ici: https://plato.stanford.edu/entries/turing-machine/ .

[Deedee81]

SAlut,

Quand tu dis que ce n'est pas assez clair ou complet, tu veux dire d'un point de vue études de maths-logique?

Oui, c'est ça, la rigueur du mathématicien ou du logicien.

Ayant fait que philo je doute de pouvoir aller , pour comprendre Turing, au dela de ce que j'ai écrit.

Oh ce n'est pas difficile. C'est pas comme si on avait donné des références sur la topologie algébrique (là moi aussi je dit gasp) ou sur la relativité générale

Les automates programmables, les machines de Turing, c'est très abordable. Avec une... bonne référence.

Si vous lisez l'anglais, il y a une ressource de bonne qualité, c'est le site "Stanford Encyclopedia of Philosophy". Ils sont assez bon pour ce genre de sujet (la logique est bien enseignées dans les facs de philosophie anglo-saxonnes, question de tradition sans doute). Voir ici: https://plato.stanford.edu/entries/turing-machine/ .

Et ça c'est très bien. J'aurais dû penser à l'encyclopédie de Stanford, je l'ai beaucoup utilisée (pour la mécanique quantique, beaucoup de chose sont très approfondies, et aussi pour la logique, les réseaux booléens...).

Je te remercie.

£Juste un mot là-dessus si ça peut aider.

A partir de 1:30 apparait un schéma dont je ne comprends pas iun traitre mot...

Pourtant jusque là ce que dit ce jeune homme est clair. Mais lorsqu'il commente le schéma je trouve que ça n'a aucun sens: f(n)=2n ne pose en soi aucune difficulté je connais depuis la troisième. Mais quel rapport entre ça et la table de transition montrée juste après ? J'ai soigneusement suivi la table de transition, je ne trouve absolument pas 1111 à l'arrivée

vraiment je comprends pas...

Je n'ai regardé que le schéma pas le reste, donc sous réserve....

Ce qui est montré n'est pas la table de transition mais le ruban avant et après. La boite c'est une machine de Turing (la table de transition est en dessous juste après mais tu l'as forcément vu, je préfère enfoncer une porte ouverte que d'oublier d'en ouvrir une ).
Et on a un ruban avant et après exécution. Le nombre de "1" donne la valeur du nombre.
et la machine implémenter "faire le double" qui je te l'accord n'est pas du plus compliqué Et donc "doit multiplier par 2 le nombre de 1 inscrit sur le ruban"

il ne le détaille pas dans la suite de la vidéo ? (ah non, de ce qu'il me semble, dommage, c'est bien d'avoir un exemple détaillé pour comprendre, au moins une fois)
Mais ici :
https://interstices.info/comment-fon...ine-de-turing/

Tu as un exemple ou tu peux choisir ce cas avec la même table de transition et tu peux exécuter la machine pas à pas (et comme valeur tu rentres juste 11, tu choisis le programme "doubler une liste de 1")
Ca marche super bien, j'ai essayé

[Tengri]

salut,

Donc il faut prendre les chiffres par groupe? Dans ce cas là , la table de transition sert à quoi?

Sinon oui, on prend 11 , on le transforme par f(x)=2x, et ça donne un double de 11

Mais je ne vois pas comment ça s'articule avec la table ! Si c'est juste pour doubler, la formule seule suffit.

il dit qu'on commence en e1 et déjà ça colle pas, vu que on est obligé de lire "1", et la table met: VIDE...

[Superbenji]

Bonsoir,
Non, il dit qu'on commence dans l'état e2, mais en fait, à regarder la table donnée, on devrais en effet commencer dans l'état e1, mais avec la tête positionnée sur la première case vide à droite des 1.
C'est très simple, voilà ce que ça donne si on fait le calcul de l'exemple de la vidéo (en commençant dans l'état e1):

Le symbole # représente une case vide, le gras représente la position de la tête.

e1:   11#
e2:   11#
e3:   10#
e2:   100
e2:   100
e3:   000
e3:   000
e3:   000#
e2:   0000
e2:   0000
e2:   0000
e2:  #0000
e4:  #0000
e4:  #1000
e4:  #1100
e4:  #1110
e4:  #1111#
fin: #1111##

[Bounoume]

Alors justement, parmi l'ensemble des trucs que j'ai pu consulter, il y en a un qui m'a particulièrement frappé: https://www.youtube.com/watch?v=F9jjj0TaaKI
A partir de 1:30 apparait un schéma dont je ne comprends pas iun traitre mot...
Pourtant jusque là ce que dit ce jeune homme est clair. Mais lorsqu'il commente le schéma je trouve que ça n'a aucun sens: f(n)=2n ne pose en soi aucune difficulté je connais depuis la troisième. Mais quel rapport entre ça et la table de transition montrée juste après ? J'ai soigneusement suivi la table de transition, je ne trouve absolument pas 1111 à l'arrivée
vraiment je comprends pas...

Bonjour Dedee et Tengri
Permettez de jouer le rôle de Candide: Tengri, j' ai l' impression que tu te poses une question différente de 'qu' est-ce que la machine de Turing' / comment marche la machine / et plein de choses concernant la machine et ce qui y rentre, ce qui y sort......
La question qui me semble bloquer est autre:
c' est : comment concevoir l' algorithme matérialisé par la table de transition?
ou encore 'comment un esprit humain [ou une machine supposée 'intelligente'] arrive-t-il à concevoir, organiser les instructions, de manière à obtenir LE résultat attendu?

C' est différent du 'comment la machine fait-elle' (question avec avec anthropomorphisme sous-jacent éventuel)

[Tengri]

Bonsoir,
Non, il dit qu'on commence dans l'état e2, mais en fait, à regarder la table donnée, on devrais en effet commencer dans l'état e1, mais avec la tête positionnée sur la première case vide à droite des 1.
C'est très simple, voilà ce que ça donne si on fait le calcul de l'exemple de la vidéo (en commençant dans l'état e1):

Le symbole # représente une case vide, le gras représente la position de la tête.

e1:   11#
e2:   11#
e3:   10#
e2:   100
e2:   100
e3:   000
e3:   000
e3:   000#
e2:   0000
e2:   0000
e2:   0000
e2:  #0000
e4:  #0000
e4:  #1000
e4:  #1100
e4:  #1110
e4:  #1111#
fin: #1111##

Mais comment on relie la fonction 2n, avec cette table? Et si on place le point rouge de la vidéo au dessus du vide le plus à droite, il semble qu'on soit en bout de bande, impossible d'aller à gauche!

Où y a t il des caractères en gras dans la liste?

[Ernum]

Salut,

salut,

Donc il faut prendre les chiffres par groupe? Dans ce cas là , la table de transition sert à quoi?

non, la machine lit et interprerte la table(*), elle n'est capable que de fonctions les plus élémentaires possibles, à savoir :

• lire une case du ruban avec trois états possibles: VIDE,0,1

• écrire une case du ruban avec trois états possibles: VIDE,0,1

• déplacer d'une case à droite ou à gauche
• passer à l'étape suivante, définie par la table: e(n) ou fin

Sinon oui, on prend 11 , on le transforme par f(x)=2x, et ça donne un double de 11.
...Mais je ne vois pas comment ça s'articule avec la table ! Si c'est juste pour doubler, la formule seule suffit

La machine ne sait pas ce qu'est une multiplication, on pourrait par exemple implémenter mécaniquement la fonction multiplication (on connaît les machines à calculer mécaniques), mais ça ne serait plus une machine élémentaire.
(*)La table constitue le programme, le langage utilisé est celui de la machine, on lui donne les instructions quelle connaît (lire, écrire, déplacer le ruban, s’arrêter(fin))

il dit qu'on commence en e1 et déjà ça colle pas, vu que on est obligé de lire "1", et la table met: VIDE...

Il s'agit de l'état initial de la machine, son état fondamental.

[Superbenji]

Rebonoir,
On ne voit pas très bien le gras avec la balise CODE... mais c'était trop tard pour modifier quand je m'en suis rendu compte. ^^ Je refais.

e1:   11#
e2:   11#
e3:   10#
e2:   100
e2:   100
e3:   000
e3:   000
e3:   000#
e2:   0000
e2:   0000
e2:   0000
e2:  #0000
e4:  #0000
e4:  #1000
e4:  #1100
e4:  #1110
e4:  #1111#
fin: #1111##

Le schéma peut laisser suggérer que le ruban est fini, mais non, le ruban s'étend à l'infini vers la droite et la gauche, il y a toujours de nouvelles cases pour la tête si le calcul l'y amène.
Comment cela se relie à la fonction f(n) = 2n ? Regarde bien, le nombre n est représenté en unaire sur le ruban, par la suite de 1 consécutif, pour l'entrée comme pour le résultat. C'est tout bête.

[Tengri]

Je ne comprends pas vraiment...

Si l'on suit la vidéo à la lettre : le point rouge étant au dessus du niveau du 1 (et si l'on est en e2) alors on devrait remplacer ce 1 par 0... ou alors faut calculer 2n avant?

[Superbenji]

Bah oui. Tu suis bêtement et mécaniquement les instructions données. Et une fois que tu atteint l'état d'arrêt, calculer 2n est exactement ça, l'ensemble de ces transitions que tu as appliqué une a une en suivant les règles.

Que se passe t-il si tu applique la même table, mais avec 111111 écrit initialement sur le ruban ? tu auras 111111111111 à l'état final. Et si tu le fais avec 1111111111111, tu auras 11111111111111111111111111 à la fin. Et ainsi de suite. Autrement dit, cette table est une procédure qui double le nombre de 1 présents sur le ruban au départ, puis s'arrête. C'est tout.

[Ernum]

C'est tout, comme tu dis et ça tombe bien c'est exactement ce qu'on veut.

Peut-être qu'il y a ambiguïté entre doubler le nombre de 11 (par exemple) et multiplier par deux la valeur binaire 11?

[Tengri]

Si vous lisez l'anglais, il y a une ressource de bonne qualité, c'est le site "Stanford Encyclopedia of Philosophy". Ils sont assez bon pour ce genre de sujet (la logique est bien enseignées dans les facs de philosophie anglo-saxonnes, question de tradition sans doute). Voir ici: https://plato.stanford.edu/entries/turing-machine/ .

Merci !

J'ai regardé, l'anglais utilisé m'a l'air assez basique. Après c'est toujours le même problème avec tout document de philosophie analytique: dès que le langage formel est employé, si les auteurs ne font pas l'effort de rendre les choses le plus pédagogique possible. Par exemple quand vous lisez le Tractatus de Wittgenstein, déjà faut comprendre le texte... Mais en plus constater que le formalisme logique employé n'est absolument pas expliqué...