Machine de Turing

Un article de Wikipedia, l'encyclopedie libre.

En informatique theorique, une machine de Turing est un modele abstrait du fonctionnement des appareils mecaniques de calcul, tel un ordinateur. Ce modele a ete imagine par Alan Turing en 1936, en vue de donner une definition precise au concept d'algorithme ou de << procedure mecanique >>. Il est toujours largement utilise en informatique theorique, en particulier dans les domaines de la complexite algorithmique et de la calculabilite.

A l'origine, le concept de machine de Turing, invente avant l'ordinateur, etait cense representer une personne virtuelle executant une procedure bien definie, en changeant le contenu des cases d'un ruban infini, en choisissant ce contenu parmi un ensemble fini de symboles. D'autre part, a chaque etape de la procedure, la personne doit se placer dans un etat particulier parmi un ensemble fini d'etats. La procedure est formulee en termes d'etapes elementaires du type : << si vous etes dans l'etat 42 et que le symbole contenu sur la case que vous regardez est << 0 >>, alors remplacer ce symbole par un << 1 >>, passer dans l'etat 17, et regarder maintenant la case adjacente a droite >>.

La these de Church postule que tout probleme de calcul fonde sur une procedure algorithmique peut etre resolu par une machine de Turing. Cette these n'est pas un enonce mathematique, puisqu'elle ne suppose pas une definition precise des procedures algorithmiques. En revanche, il est possible de definir une notion de << systeme acceptable de programmation >> et de demontrer que le pouvoir de tels systemes est equivalent a celui des machines de Turing (ils sont Turing-complets).

Quoique son nom de << machine >> puisse conduire a croire le contraire, une machine de Turing est un concept abstrait, c'est-a-dire un objet mathematique. Une machine de Turing comporte les elements suivants :

1. Un ruban infini divise en cases consecutives. Chaque case contient un symbole d'un alphabet fini donne. L'alphabet contient un symbole special appele << symbole blanc >> ('0' dans les exemples qui suivent), et un ou plusieurs autres symboles. Le ruban est suppose etre de longueur illimitee vers la gauche et vers la droite, en d'autres termes la machine doit toujours avoir assez de longueur de ruban pour son execution. On considere que les cases du ruban contiennent par defaut le << symbole blanc >> ;
2. Une tete de lecture/ecriture qui peut lire et ecrire les symboles sur le ruban, et se deplacer vers la gauche ou vers la droite du ruban ;
3. Un registre d'etat qui memorise l'etat courant de la machine de Turing. Le nombre d'etats possibles est toujours fini, et il existe un etat special appele << etat de depart >> qui est l'etat initial de la machine avant son execution ;
4. Une table d'actions qui indique a la machine quel symbole ecrire sur le ruban, comment deplacer la tete de lecture (par exemple << ${\displaystyle \leftarrow }$ >> pour une case vers la gauche, << ${\displaystyle \rightarrow }$ >> pour une case vers la droite), et quel est le nouvel etat, en fonction du symbole lu sur le ruban et de l'etat courant de la machine. Si aucune action n'existe pour une combinaison donnee d'un symbole lu et d'un etat courant, la machine s'arrete.

Plusieurs definitions formelles proches les unes des autres peuvent etre donnees d'une machine de Turing. L'une d'elles^[1], relativement courante, est choisie ici. Une machine de Turing est un quintuplet ${\displaystyle (Q,\Gamma ,q_{0},\delta ,F)}$ ou :

• ${\displaystyle Q}$ est un ensemble fini d'etats ;
• ${\displaystyle \Gamma }$ est l'alphabet de travail des symboles de la bande, contenant ${\displaystyle B}$ un symbole particulier (dit blanc), ${\displaystyle B\in \Gamma }$ ;
• ${\displaystyle q_{0}}$ est l'etat initial, ${\displaystyle q_{0}\in Q}$ ;
• ${\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{\leftarrow ,\rightarrow \}}$ est la fonction de transition ;
• ${\displaystyle F}$ est l'ensemble des etats acceptants (ou finals^[2], terminaux), ${\displaystyle F\subseteq Q}$.

Il s'agit d'un modele de machine de Turing complete et deterministe ; i.e ${\displaystyle \forall q\in Q,\forall \gamma \in \Gamma ,\delta (q,\gamma )}$ est definie et unique^[3].

Les fleches dans la definition de ${\displaystyle \delta }$ representent les deux deplacements possibles de la tete de lecture/ecriture, a savoir le deplacement a gauche et le deplacement a droite. La signification de cette fonction de transition peut etre expliquee sur l'exemple suivant : ${\displaystyle \delta (q_{1},x)=(q_{2},y,\leftarrow )}$ signifie que si la machine de Turing est dans l'etat ${\displaystyle q_{1}}$ et qu'elle lit le symbole ${\displaystyle x}$, alors elle ecrit ${\displaystyle y}$ a la place de ${\displaystyle x}$, va dans l'etat ${\displaystyle q_{2}}$, puis deplace sa tete de lecture vers la gauche.

Le fonctionnement de la machine de Turing est alors le suivant : a chaque etape de son calcul, la machine evolue en fonction de l'etat dans lequel elle se trouve et du symbole inscrit dans la case du ruban ou se trouve la tete de lecture. Ces deux informations permettent la mise a jour de l'etat de la machine grace a la fonction de transition. A l'instant initial, la machine se trouve dans l'etat ${\displaystyle q_{0}}$, et le premier symbole du ruban est l'entree du programme. La machine s'arrete lorsqu'elle rentre dans un etat terminal. Le resultat du calcul est alors le mot forme par les symboles successivement lus par la machine.

On peut contraindre un alphabet des entrees possibles ${\displaystyle \Sigma }$ dans la definition. On peut ainsi travailler plus precisement sur cet alphabet en reservant certains symboles de l'alphabet complet ${\displaystyle \Gamma }$ pour les etapes de calcul de la machine. En particulier, le symbole blanc ${\displaystyle B}$ ne doit pas faire partie de l'entree et peut donc definir la fin de cette derniere^{[pas clair]}.

Le premier exemple ci-dessous utilise une version tres legerement differente de machine de Turing dans laquelle une machine s'arrete si elle est dans un etat terminal et qu'elle lit un certain caractere sur le ruban (ici le symbole blanc). Le deuxieme exemple ci-dessous est le premier exemple historique donne par Turing dans son article de 1936 : c'est une machine qui ne s'arrete pas.

La machine de Turing qui suit possede un alphabet {'0', '1'}, '0' etant le << symbole blanc >>. On suppose que le ruban contient une serie de '1', et que la tete de lecture/ecriture se trouve initialement au-dessus du '1' le plus a gauche. Cette machine a pour effet de doubler le nombre de '1', en intercalant un '0' entre les deux series. Par exemple, << 111 >> devient << 1110111 >>.
L'ensemble d'etats possibles de la machine est {e1, e2, e3, e4, e5} et l'etat initial est e1.
La table d'actions est la suivante :

Exemple de table de transition

Ancien etat	Symbole lu	Symbole ecrit	Mouvement	Nouvel etat
e1	0	(Arret)
	1	0	Droite	e2
e2	1	1	Droite	e2
	0	0	Droite	e3
e3	1	1	Droite	e3
	0	1	Gauche	e4
e4	1	1	Gauche	e4
	0	0	Gauche	e5
e5	1	1	Gauche	e5
	0	1	Droite	e1

L'execution de cette machine pour une serie de deux '1' serait (la position de la tete de lecture/ecriture sur le ruban est inscrite en caracteres gras et rouges) :

Execution (1) Etape Etat Ruban 1 e1 11 2 e2 01 3 e2 010 4 e3 0100

Execution (2) Etape Etat Ruban 5 e4 0101 6 e5 0101 7 e5 0101 8 e1 1101

Execution (3) Etape Etat Ruban 9 e2 1001 10 e3 1001 11 e3 10010 12 e4 10011

Execution (4) Etape Etat Ruban 13 e4 10011 14 e5 10011 15 e1 11011 (Arret)

Le comportement de cette machine peut etre decrit comme une boucle :

• Elle demarre son execution dans l'etat e1, remplace le premier 1 par un 0.
• Puis elle utilise l'etat e2 pour se deplacer vers la droite, en sautant les 1 (un seul dans cet exemple) jusqu'a rencontrer un 0 (ou un blanc), et passer dans l'etat e3.
• L'etat e3 est alors utilise pour sauter la sequence suivante de 1 (initialement aucun) et remplacer le premier 0 rencontre par un 1.
• L'etat e4 permet de revenir vers la gauche jusqu'a trouver un 0, et passer dans l'etat e5.
• L'etat e5 permet ensuite a nouveau de se deplacer vers la gauche jusqu'a trouver un 0, ecrit au depart par l'etat e1.
• La machine remplace alors ce 0 par un 1, se deplace d'une case vers la droite et passe a nouveau dans l'etat e1 pour une nouvelle iteration de la boucle.

Ce processus se repete jusqu'a ce que e1 tombe sur un 0 (c'est le 0 du milieu entre les deux sequences de 1) ; a ce moment, la machine s'arrete.

Dans l'exemple qui suit, la machine de Turing possede un ruban vide et permet de construire la suite 01010101010101...

Exemple de table infinie

Ancien etat	Symbole ecrit	Mouvement	Nouvel etat
a	0	Droite	b
b	1	Droite	a

L'execution de cette machine serait (la position de la tete de lecture/ecriture sur le ruban est inscrite en caracteres gras et magenta) :

Execution de la Machine infinie

Etape	Etat	Ruban
1	a	0
2	b	01
3	a	010
4	b	0101
5	a	01010
6	b	010101
7	a	0101010
8	b	01010101
...	...	01010101...

Le comportement de cette machine peut etre decrit comme une boucle infinie :

• Elle demarre son execution dans l'etat a, ajoute un 0 et se deplace a droite.
• Puis elle passe a l'etat b, ajoute un 1 et se deplace a droite.
• Elle revient dans l'etat a et reitere la premiere etape.

Cette machine est la contrepartie du calcul de un tiers dont l'ecriture en binaire est 0,010101010101...; en effet dans le systeme binaire ${\displaystyle 0.0101={\frac {1}{4}}+{\frac {1}{16}}}$ et

${\displaystyle 0.01010101...=\sum _{k=1}^{+\infty }{\frac {1}{4^{k}}}={\frac {1}{4}}\sum _{k=0}^{+\infty }{\frac {1}{4^{k}}}={\frac {1}{4}}*{\frac {4}{3}}={\frac {1}{3}}}$ soit un tiers ecrit dans le systeme binaire.

1) Etablir une bijection entre les entiers naturels et les points du plan de coordonnees entieres et positives^[4].

2) Inversion d'une chaine de caracteres en utilisant une suite de transpositions

3) Verification de la conjecture de Collatz

Comme Alan Turing le montre dans son article fondateur, il est possible de creer une machine de Turing qu'on appelle << machine de Turing universelle >> et qui est capable de << simuler >> le comportement de n'importe quelle autre machine de Turing. << Simuler >> signifie que si la machine de Turing universelle recoit en entree un codage d'une machine T et des donnees D, elle produit le meme resultat que la machine T a laquelle on donnerait en entree les donnees D.

Une machine de Turing universelle a la capacite de calculer tout ce qui est calculable : on dit alors qu'elle est Turing-complete. En lui fournissant le codage adequat, elle peut simuler toute fonction recursive, analyser tout langage recursif, et accepter tout langage partiellement decidable. Selon la these de Church-Turing, les problemes resolubles par une machine de Turing universelle sont exactement les problemes resolubles par un algorithme ou par une methode concrete de calcul.

Une machine de Turing est un objet de pensee : son ruban est infini, et donc la memoire d'une machine de Turing est infinie. Une machine de Turing n'engendre jamais de debordement de memoire, contrairement a un ordinateur dont la memoire est finie. En oubliant ce probleme de memoire, on peut simuler une machine de Turing sur un ordinateur moderne.

Il est aussi possible de construire des machines de Turing purement mecaniques. La machine de Turing, objet de pensee, a pu ainsi etre reifiee a de nombreuses reprises en utilisant des techniques parfois assez originales, dont voici quelques exemples.

• En avril 2011, Jim MacArthur a realise une machine de Turing mecanique compacte, a 5 symboles, avec des billes comme support d'informations sur le ruban^[5].
• En mars 2012, a l'occasion de l'annee Turing (en), une equipe d'etudiants de l'Ecole normale superieure de Lyon a realise une machine de Turing entierement faite de pieces Lego sans electronique^[6],[7].
• En novembre 2013, Marc Raynaud elabore un prototype electromecanique de la machine de Turing a 3 symboles, 12 etats et 100 cases sur le ruban. Il fonctionne a la frequence de 1 Hertz^[8]. Facilement transportable, ce prototype est utilise regulierement , dans le cadre de recherches algorithmiques, par des professeurs, des etudiants et des lyceens.
• En 2019, des chercheurs anglo-saxons realisent une machine de Turing a l'aide d'un combo dans le jeu de cartes Magic : L'Assemblee^[9].

• En octobre 2020, une machine de Turing pedagogique concue par Thierry Delattre (Dunkerque), programmable pour des algorithmes ayant au maximum 12 etats et avec un alphabet de 3 symboles. 50 algorithmes peuvent etre stockes en memoire. Une version ayant 22 etats et 8 symboles date de fevrier 2021^[10].

: document utilise comme source pour la redaction de cet article.

Manuels

• Olivier Carton, Langages formels, calculabilite et complexite : licence et master de mathematiques ou d'informatique, option informatique de l'agregation de mathematiques, Paris, Vuibert, 2008, 237 p. (ISBN 978-2-7117-2077-4, SUDOC 128299258).
• Jean-Michel Autebert, Calculabilite et decidabilite, Paris, Masson, 1992, 118 p. (ISBN 978-2-225-82632-0, SUDOC 002676494).
• Eric Jacopin, Les machines de Turing : Introduction a la caracterisation de la complexite d'un probleme, Toulouse, Editions Cepadues, 2009, 264 p. (ISBN 978-2-85428-865-0, SUDOC 132323214).

Turing

• Alan Turing et Jean-Yves Girard, La machine de Turing, Paris, Editions du Seuil, 1995, 192 p. [detail de l'edition] (ISBN 9782020369282) ; cet ouvrage comprend notamment une traduction en francais (par Julien Basch et Patrice Blanchard) de l'article original, ainsi qu'une correction par Emil Post des erreurs y figurant ;
• (en) Alan Turing, << On Computable Numbers, with an Application to the Entscheidungsproblem >>, Proceedings of the London Mathematical Society, serie 2, vol. 45, 1936, p. 230-265 (lire en ligne) ;
• (fr) Alan Turing, Precis of 'Computable Numbers' (lire en ligne). -- Un brouillon pour une Note aux Comptes-Rendus de l'academie des Sciences de Paris.

Kleene

• Stephen Cole Kleene, Introduction to Metamathematics, Amsterdam, North-Holland, 1952, x+550 (SUDOC 005505526, presentation en ligne) -- Nombreuses reimpressions, en 1957, 1959, 1962, 1964, 1967, 1971, 1974, 1980, 1988, 1991, 1996, 2000, 2009 notamment par Wolters-Noordhoff (Groningen) (ISBN 0720421039), d'apres la notice Sudoc. Nombreuses traductions.
• (en + fr) Stephen Cole Kleene, Mathematical Logic, Dover, 1967 -- Reimpression Dover reprint, 2001, (ISBN 0-486-42533-9). Traduction francaise par Jean Largeault, Logique mathematique, Armand Colin, 1971 et Gabay 1987 (ISBN 2-87647-005-5).

• Machine de Turing non deterministe
• Machine de Turing probabiliste
• Machine de Turing alternante
• Machine de Turing symetrique
• Machine de Blum-Shub-Smale : une generalisation a des machines calculant sur ${\displaystyle \mathbb {R} }$
• Entscheidungsproblem (probleme de la decision)
• Experience de pensee
• Oracle (machine de Turing)
• Imitation Game, film sur la vie d'Alan Turing avec Benedict Cumberbatch
• Fonction constructible

• Le film << La Machine de Turing realisee >> de Christophe Gombert et Hugo Deboise a visionner en ligne gratuitement.
• Le genie interrompu d'Alan Turing : presentation et bibliographie d'une conference BnF de Bernard Chazelle, programmee pour le 19 mars 2014
• Hamdi Ben Abdallah, << Comment fonctionne une machine de Turing ? >>, Interstices, 22 mars 2013 (lire en ligne), article permettant d'essayer une machine de Turing.

• Portail de l'informatique theorique

Ce document provient de << https://fr.wikipedia.org/w/index.php?title=Machine_de_Turing&oldid=232829192 >>.

Categories :

• Logique mathematique
• Calculabilite
• Theorie de la complexite des algorithmes
• Theorie des automates
• Alan Turing
• Modele de calcul

Categories cachees :

• Article contenant un appel a traduction en anglais
• Categorie Commons avec lien local identique sur Wikidata
• Portail:Informatique theorique/Articles lies
• Portail:Informatique/Articles lies
• Portail:Mathematiques/Articles lies
• Portail:Sciences/Articles lies