Voir la source de Machine de Turing

{{voir homonymes|Turing}}
[[Fichier:Hiérarchie d'automates.svg|thumb|upright=1.5|Fig. 1 : Une hiérarchie d'automates.]]
[[Image:Maquina.png|thumb|alt=Vue d’artiste d’une Machine de Turing (sans la table de transition)|Fig. 2 : Vue d’artiste d’une machine de Turing : un ruban infini muni d'une tête de lecture/écriture. La machine dispose également d'une table de transition, non représentée sur l'image.]]

En [[informatique théorique]], une '''machine de Turing''' est un modèle abstrait du fonctionnement des [[Calculatrice mécanique|appareils mécaniques de calcul]], tel un [[ordinateur]]. Ce modèle a été imaginé par [[Alan Turing]] en 1936, en vue de donner une définition précise au concept d’[[Algorithmique|algorithme]] ou de « procédure mécanique ».
Il est toujours largement utilisé en [[informatique théorique]], en particulier dans les domaines de la [[Théorie de la complexité des algorithmes|complexité algorithmique]] et de la [[calculabilité]].

À l'origine, le concept de machine de Turing, inventé avant l'ordinateur, était censé représenter une personne virtuelle exécutant une procédure bien définie, en changeant le contenu des cases d'un ruban infini, en choisissant ce contenu parmi un [[ensemble fini]] de [[symbole]]s. D'autre part, à chaque étape de la procédure, la personne doit se placer dans un état particulier parmi un ensemble fini d'états. La procédure est formulée en termes d'étapes élémentaires du type : « si vous êtes dans {{nobr|l'état 42}} et que le symbole contenu sur la case que vous regardez est « 0 », alors remplacer ce symbole par un « 1 », passer dans {{nobr|l'état 17}}, et regarder maintenant la case adjacente à droite ».

La [[thèse de Church]] postule que tout problème de calcul fondé sur une procédure algorithmique peut être résolu par une machine de Turing. Cette thèse n'est pas un énoncé mathématique, puisqu'elle ne suppose pas une définition précise des procédures algorithmiques. En revanche, il est possible de définir une notion de « système acceptable de programmation » et de démontrer que le pouvoir de tels systèmes est équivalent à celui des machines de Turing (ils sont [[Turing-complet]]s).

== Définition ==
Quoique son nom de « machine » puisse conduire à croire le contraire, une machine de Turing est un concept abstrait, c'est-à-dire un objet mathématique. Une machine de Turing comporte les éléments suivants :
# Un '''ruban infini''' divisé en cases consécutives. Chaque case contient un symbole d'un [[alphabet]] fini donné. L'alphabet contient un symbole spécial appelé « symbole blanc » ('0' dans les exemples qui suivent), et un ou plusieurs autres symboles. Le ruban est supposé être de longueur illimitée vers la gauche et vers la droite, en d'autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution. On considère que les cases du ruban contiennent par défaut le « symbole blanc » ;
# Une '''tête de lecture/écriture''' qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban ;
# Un '''registre d'état''' qui mémorise l'état courant de la machine de Turing. Le nombre d'états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l'état initial de la machine avant son exécution ;
# Une '''table d'actions''' qui indique à la machine quel symbole écrire sur le ruban, comment déplacer la tête de lecture (par exemple « <math>\leftarrow</math> » pour une case vers la gauche, « <math>\rightarrow</math> » pour une case vers la droite), et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l'état courant de la machine. Si aucune action n'existe pour une combinaison donnée d'un symbole lu et d'un état courant, la machine s'arrête.

== Définition formelle ==

Plusieurs définitions formelles proches les unes des autres peuvent être données d'une machine de Turing. L'une d'elles<ref>{{en}} [[:en: Harry R. Lewis|Harry R. Lewis]] et [[Christos Papadimitriou]], ''Elements of the Theory of Computation''. [[Prentice-Hall]], 1982; second edition September 1997.</ref>, relativement courante, est choisie ici. Une machine de Turing est un quintuplet <math>(Q,\Gamma, q_0, \delta, F)</math> où :
* <math>Q</math> est un ensemble fini d'''états'' ;
* <math>\Gamma</math> est l'''alphabet de travail'' des symboles de la bande, contenant <math>B</math> un symbole particulier (dit ''blanc''), <math>B\in\Gamma</math> ;
<!-- * <math>\Sigma</math> est l'''alphabet'' des symboles en entrée avec <math>\Sigma\subseteq\Gamma\setminus\{B\}</math>, c'est-à-dire l'ensemble des symboles apparaissant sur la bande à l'entrée du programme ; -->
* <math>q_0</math> est l'''état initial'', <math>q_0\in Q</math> ;
* <math>\delta : Q\times \Gamma\to Q\times\Gamma\times\{\leftarrow,\rightarrow\}</math> est la ''fonction de transition'' ;
* <math>F</math> est l'ensemble des ''états acceptants'' (ou finals<ref>[http://www.cnrtl.fr/definition/final « FINAL »], CNRTL : {{Citation|En fait, il y a flottement entre ''finals'' et ''finaux'' : le {{1er}} semble être le plur. de la lang. cour. et des écrivains, le second celui des linguistes et des économistes}}.</ref>, terminaux), <math>F\subseteq Q</math>.
Il s'agit d'un modèle de machine de Turing complète et déterministe ; i.e <math>\forall q \in Q, \forall \gamma \in \Gamma, \delta(q, \gamma)</math> est définie et unique<ref>{{Lien web |langue=fr |auteur=Kévin Perrot |titre=Calculabilité. Cours 1 : machines de Turing |url=http://pageperso.lif.univ-mrs.fr/~kevin.perrot/documents/2018/calculabilite/Cours01_18.pdf |site=univ-mrs.fr |date=printemps 2019|consulté le=novembre 2020}}</ref>.

Les flèches dans la définition de <math>\delta</math> représentent les deux déplacements possibles de la tête de lecture/écriture, à savoir le déplacement à gauche et le déplacement à droite. La signification de cette fonction de transition peut être expliquée sur l'exemple suivant : 
<math>\delta(q_1,x)=(q_2,y,\leftarrow)</math> signifie que si la machine de Turing est dans l'état <math>q_1</math> et qu'elle lit le symbole <math>x</math>, alors elle écrit <math>y</math> à la place de <math>x</math>, va dans l'état <math>q_2</math>, puis déplace sa tête de lecture vers la gauche.

Le fonctionnement de la machine de Turing est alors le suivant : à chaque étape de son calcul, la machine évolue en fonction de l'état dans lequel elle se trouve et du symbole inscrit dans la case du ruban où se trouve la tête de lecture. Ces deux informations permettent la mise à jour de l'état de la machine grâce à la fonction de transition. À l'instant initial, la machine se trouve dans l'état <math>q_0</math>, et le premier symbole du ruban est l'entrée du programme. La machine s'arrête lorsqu'elle rentre dans un état terminal. Le résultat du calcul est alors le mot formé par les symboles successivement lus par la machine.

On peut contraindre un alphabet des entrées possibles <math>\Sigma</math> dans la définition. On peut ainsi travailler plus précisément sur cet alphabet en réservant certains symboles de l'alphabet complet <math>\Gamma</math> pour les étapes de calcul de la machine. En particulier, {{Pas clair|le symbole blanc <math>B</math> ne doit pas faire partie de l'entrée et peut donc définir la fin de cette dernière|Il semble que le terme "entrée" est ici utilisé à la fois pour désigner le symbole lu par la machine à l'état initial, et pour désigner l'ensemble des symboles lus jusqu'à l'état terminal.|date=juin 2020}}.

Le premier exemple ci-dessous utilise une version très légèrement différente de machine de Turing dans laquelle une machine s'arrête si elle est dans un état terminal et qu'elle lit un certain caractère sur le ruban (ici le symbole blanc). Le deuxième exemple ci-dessous est le premier exemple historique donné par Turing dans son article de 1936 : c'est une machine qui ne s'arrête pas.

== Exemples ==

=== Doubler le nombre de ‘1’ ===

La machine de Turing qui suit possède un alphabet {‘0’, ‘1’}, ‘0’ étant le « symbole blanc ». On suppose que le ruban contient une série de ‘1’, et que la tête de lecture/écriture se trouve initialement au-dessus du ‘1’ le plus à gauche. Cette machine a pour effet de doubler le nombre de ‘1’, en intercalant un ‘0’ entre les deux séries. Par exemple, « 111 » devient « 1110111 ».<br />
L’ensemble d’états possibles de la machine est {e1, e2, e3, e4, e5} et l’état initial est e1.<br />
La table d’actions est la suivante :
{|cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"
|+Exemple de table de transition
|-
!scope="col"| Ancien état!!scope="col"|Symbole lu!!scope="col"|Symbole écrit!!scope="col"|Mouvement!!scope="col"|Nouvel état
|-
!scope="row" rowspan="2"|e1!!scope="row"|0
|colspan="3" align="center"|''(Arrêt)''
|-
!scope="row"|1
|0||Droite||e2
|-
!scope="row" rowspan="2"|e2!!scope="row"|1
|1||Droite||e2
|-
!scope="row"|0
|0||Droite||e3
|-
!scope="row" rowspan="2"|e3!!scope="row"|1
|1||Droite||e3
|-
!scope="row"|0
|1||Gauche||e4
|-
!scope="row" rowspan="2"|e4!!scope="row"|1
|1||Gauche||e4
|-
!scope="row"|0
|0||Gauche||e5
|-
!scope="row" rowspan="2"|e5!!scope="row"|1
|1||Gauche||e5
|-
!scope="row"|0
|1||Droite||e1
|}

L’exécution de cette machine pour une série de deux '1' serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et rouges) :<br />
{|
||
{|cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"
|-
|+ Exécution (1)
!scope="col"| Étape!!scope="col"| État!!scope="col"| Ruban
|-
!scope="row" |1
|e1||{{Rouge|'''1'''}}1
|-
!scope="row" |2
|e2||0{{Rouge|'''1'''}}
|-
!scope="row" |3
|e2||01{{Rouge|'''0'''}}
|-
!scope="row" |4
|e3||010{{Rouge|'''0'''}}
|}
||
{|cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"
|+ Exécution (2)
|-
!scope="col"| Étape!!scope="col"| État!!scope="col"| Ruban
|-
!scope="row" |5
|e4||01{{Rouge|'''0'''}}1
|-
!scope="row" |6
|e5||0{{Rouge|'''1'''}}01
|-
!scope="row" |7
|e5||{{Rouge|'''0'''}}101
|-
!scope="row" |8
|e1||1{{Rouge|'''1'''}}01
|}
||
{|cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"
|+ Exécution (3)
|-
!scope="col"| Étape!!scope="col"| État!!scope="col"| Ruban
|-
!scope="row" |9
|e2||10{{Rouge|'''0'''}}1 
|-
!scope="row" |10
|e3||100{{Rouge|'''1'''}}
|-
!scope="row" |11
|e3||1001{{Rouge|'''0'''}}
|-
!scope="row" |12
|e4||100{{Rouge|'''1'''}}1
|}
||
{|cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"
|+ Exécution (4)
|-
!scope="col"| Étape!!scope="col"| État!!scope="col"| Ruban
|-
!scope="row" |13
|e4||10{{Rouge|'''0'''}}11
|-
!scope="row" |14
|e5||1{{Rouge|'''0'''}}011
|-
!scope="row" |15
|e1||11{{Rouge|'''0'''}}11
|-
!scope="row" |&nbsp;
|colspan="2" align="center"|''(Arrêt)''
|}
|}
Le comportement de cette machine peut être décrit comme une boucle :
* Elle démarre son exécution dans l’état e1, remplace le premier 1 par un 0.
* Puis elle utilise l’état e2 pour se déplacer vers la droite, en sautant les 1 (un seul dans cet exemple) jusqu'à rencontrer un 0 (ou un blanc), et passer dans l'état e3.
* L’état e3 est alors utilisé pour sauter la séquence suivante de 1 (initialement aucun) et remplacer le premier 0 rencontré par un 1.
* L'état e4 permet de revenir vers la gauche jusqu’à trouver un 0, et passer dans l’état e5.
* L'état e5 permet ensuite à nouveau de se déplacer vers la gauche jusqu’à trouver un 0, écrit au départ par l’état e1.
* La machine remplace alors ce 0 par un 1, se déplace d’une case vers la droite et passe à nouveau dans l’état e1 pour une nouvelle itération de la boucle.
Ce processus se répète jusqu’à ce que e1 tombe sur un 0 (c’est le 0 du milieu entre les deux séquences de 1) ; à ce moment, la machine s’arrête.

=== Calculer un tiers en binaire ===

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

{|cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"
|+Exemple de table infinie
|-
!scope="col"| Ancien état!!scope="col"|Symbole écrit!!scope="col"|Mouvement!!scope="col"|Nouvel état
|-
!scope="row" |a
|0||Droite||b
|-
!scope="row" |b
|1||Droite||a
|}

L’exécution de cette machine serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et [[Magenta (couleur)|magenta]]) :

{|cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"
|+Exécution de la Machine infinie
|-
!scope="col"| Étape!!scope="col"|État!!scope="col"|Ruban
|-
!scope="row" |1
|a||{{Magenta|'''0'''}}
|-
!scope="row" |2
|b||0{{Magenta|'''1'''}}
|-
!scope="row" |3
|a||01{{Magenta|'''0'''}}
|-
!scope="row" |4
|b||010{{Magenta|'''1'''}}
|-
!scope="row" |5
|a||0101{{Magenta|'''0'''}}
|-
!scope="row" |6
|b||01010{{Magenta|'''1'''}}
|-
!scope="row" |7
|a||010101{{Magenta|'''0'''}}
|-
!scope="row" |8
|b||0101010{{Magenta|'''1'''}}
|-
!scope="row" |...
|...||01010101{{Magenta|'''...'''}}
|}

Le comportement de cette machine peut être décrit comme une boucle infinie :
* Elle démarre son exécution dans l’état a, ajoute un 0 et se déplace à droite.
* Puis elle passe à l'état b, ajoute un 1 et se déplace à droite.
* Elle revient dans l'état a et réitère la première étape.
Cette machine est la contrepartie du calcul de un tiers dont l'écriture en binaire est 0,010101010101...; en effet dans le système binaire <math>0.0101 = \frac{1}{4}+\frac{1}{16} </math> et 

<math>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} </math>  soit un tiers écrit dans le système binaire.<gallery widths="400" heights="400" caption="Deux exemples de machines de Turing donnés sous forme de schémas">
Fichier:Calcul pgcd.jpg|alt=Un schéma des états de la machine, et une explication du rôle de chaque état.|Calcul du [[plus grand commun diviseur|PGCD]] de deux entiers X et Y écrits en unaire, avec l'algorithme d'Euclide<ref name="iam">[https://images-archive.math.cnrs.fr/La-machine-de-Turing-4.html Explications sur math.cnrs.fr]</ref>. 
Fichier:Bijection N plan.jpg|alt=Le graphe des états de la machine, un tableau de correspondance entre les 16 premiers entiers et paires d'entiers et la représentation graphique de cette bijection, qui parcours les paires en zig-zag : d'abord (0, 0) puis (0, 1) puis (1, 0) puis (0, 2) etc.|Établir une bijection entre les entiers naturels et les points du plan de coordonnées entières et positives<ref name="iam"/>.
</gallery>

== Machines de Turing universelles ==
{{Article détaillé|Machine de Turing universelle}}
[[Fichier:Model of a Turing machine.jpg|vignette|Un modèle de la machine de Turing.]]
Comme Alan Turing le montre dans son article fondateur, il est possible de créer 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 reçoit en entrée un codage d'une machine ''T'' et des données ''D'', elle produit le même résultat que la machine ''T'' à laquelle on donnerait en entrée les données ''D''.

Une machine de Turing universelle a la capacité de calculer tout ce qui est calculable : on dit alors qu'elle est [[Turing-complet|Turing-complète]]. En lui fournissant le codage adéquat, elle peut simuler toute [[fonction récursive]], analyser tout [[langage récursif]], et accepter tout [[langage partiellement décidable]]. Selon la [[thèse de Church-Turing]], les problèmes résolubles par une machine de Turing universelle sont exactement les problèmes résolubles par un ''algorithme'' ou par une ''méthode concrète de calcul''.

== Réalisation d'une machine de Turing ==
[[Fichier:Machine de turing.jpg|vignette|La machine de Turing de Marc Raynaud.|gauche]]

Une machine de Turing est un objet de pensée : son ruban est infini, et donc la mémoire d'une machine de Turing est infinie. Une machine de Turing n'engendre jamais de [[out of memory|débordement de mémoire]], contrairement à un ordinateur dont la mémoire est finie. En oubliant ce problème de mémoire, on peut [[simulation informatique|simuler]] une machine de Turing sur un ordinateur moderne.

Il est aussi possible de construire des machines de Turing purement mécaniques. La machine de Turing, objet de pensée, a pu ainsi être [[wikt:réifier|réifiée]] à de nombreuses reprises en utilisant des techniques parfois assez originales, dont voici quelques exemples.[[Fichier:Lego Turing Machine.jpg|thumb|alt=Illustration d’une réalisation de machine de Turing en Lego créée pour l’année Turing|La machine de Turing en Lego créée à l’occasion du projet Rubens de l'ENS-Lyon.]]
* En {{date-|avril 2011}}, Jim MacArthur a réalisé une machine de Turing mécanique compacte, à 5 symboles, avec des  billes comme support d'informations sur le ruban<ref>{{Lien web
 | langue      = en 
 | url         = http://srimech.blogspot.fr/search/label/turingmachine
 | titre       = Turing machine
 | auteur      = Jim MacArthur
 | site        = srimech.blogspot.fr
 | date        = 8 juin 2012
 | consulté le=20 février 2018
}}.</ref>.
* En {{date-|mars 2012}}, à l’occasion de l’{{Lien|trad=Alan Turing Year|année Turing}}, une équipe d'étudiants de l'[[École normale supérieure de Lyon]] a réalisé une machine de Turing entièrement faite de pièces [[Lego]] sans électronique<ref>{{Lien web
 | url         = http://rubens.ens-lyon.fr/fr/
 | titre       = Projet RUBENS
 | site        = rubens.ens-lyon.fr
 | date        = mars 2012
 | consulté le=20 février 2018
}}.</ref>{{,}}<ref>{{Lien web 
 | url         = https://www.lemonde.fr/sciences/article/2012/06/22/l-ordinateur-en-lego-inspire-par-alan-turing_1723058_1650684.html
 | titre       = Une machine entièrement mécanique qui ne manque pas d'air
 | auteur      = David Larousserie, [[Le Monde]]
 | site        = lemonde.fr
 | date        = 22 juin 2012
 | consulté le=20 février 2018
}}.</ref>.
* En novembre 2013, Marc Raynaud élabore un prototype électromécanique de la machine de Turing à 3 symboles, 12 états et 100 cases sur le ruban. Il fonctionne à la fréquence de 1 Hertz<ref>{{Lien web |titre=Images des mathématiques |url=https://images-archive.math.cnrs.fr/La-machine-de-Turing-1.html |site=images-archive.math.cnrs.fr |consulté le=2024-07-03}}</ref>. Facilement transportable, ce prototype est utilisé régulièrement , dans le cadre de recherches algorithmiques, par des professeurs, des étudiants et des lycéens.
[[Fichier:Machine de Turing pédagogique.jpg|vignette|Machine de Turing programmable avec 3 symboles et au plus 12 états.]]
* En octobre 2020, une machine de Turing pédagogique conçue par Thierry Delattre (Dunkerque), programmable pour des algorithmes ayant au maximum 12 états et avec un alphabet de 3 symboles. 50 algorithmes peuvent être stockés en mémoire. Une version ayant 22 états et 8 symboles date de février 2021<ref>{{Lien web |langue=fr-FR |titre=Machine de Turing – Codez puis faites exécuter des animations lumineuses attrayantes, des calculs mathématiques sur des nombres binaires, des séries de nombres, ou tout autre application que vous inventerez à loisir ! |url=https://machine-de-turing.fr/ |consulté le=19 mars 2021}}.</ref>.

== Références et bibliographie ==
<!-- == Notes, références et bibliographie ==
=== Notes ===
{{Références|groupe=note}} On remettra tout ça quand il y aura des notes... -->

=== Références ===
{{Références}}

=== Bibliographie ===
{{Légende plume}}
<!-- Manuels -->
;Manuels
* {{Ouvrage
 |langue=fr
 |auteur1=Olivier Carton
 |titre=Langages formels, calculabilité et complexité
 |sous-titre=licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques
 |lieu=Paris
 |éditeur=[[Vuibert]]
 |année=2008
 |pages totales=237
 |isbn=978-2-7117-2077-4
 |sudoc=128299258
 |plume=oui
}}
* {{Ouvrage
 |auteur1=Jean-Michel Autebert
 |titre=Calculabilité et décidabilité
 |lieu=Paris
 |éditeur=Masson
 |année=1992
 |pages totales=118
 |isbn=978-2-225-82632-0
 |sudoc=002676494
 |plume=oui
}}
* {{Ouvrage
 |langue=fr
 |auteur1=Éric Jacopin
 |titre=Les machines de Turing
 |sous-titre=Introduction à la caractérisation de la complexité d'un problème
 |lieu=Toulouse
 |éditeur=[[Éditions Cépaduès]]
 |année=2009
 |pages totales=264
 |isbn=978-2-85428-865-0
 |sudoc=132323214
 |plume=oui
}}
<!-- Turing -->
;Turing
* {{Ouvrage|auteur1=[[Alan Turing]]|auteur2=[[Jean-Yves Girard]]|titre=La machine de Turing|lieu=Paris|éditeur=Éditions du Seuil|année=1995|date=|pages totales=192|isbn=9782020369282|lire en ligne=|référence simplifiée=Référence:La machine de Turing}} ; cet ouvrage comprend notamment une traduction en français (par Julien Basch et Patrice Blanchard) de l'article original, ainsi qu'une correction par [[Emil Post]] des erreurs y figurant ;
* {{en}} {{article
 |auteur=Alan Turing
 |titre=On Computable Numbers, with an Application to the Entscheidungsproblem
 |journal=Proceedings of the London Mathematical Society, série 2|volume=45|pages=230-265|année=1936|lire en ligne=https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf}} ;
* {{fr}} {{Ouvrage|auteur1=Alan Turing|titre=Précis of ‘Computable Numbers’|éditeur=|année=|isbn=|lire en ligne=http://www.turingarchive.org/browse.php/K/4}}. — <small>Un brouillon pour une Note aux Comptes-Rendus de l’académie des Sciences de Paris.</small>
<!-- Kleene -->
;Kleene
* {{Ouvrage
 |auteur1=[[Stephen Cole Kleene]]
 |titre=Introduction to Metamathematics
 |lieu=Amsterdam
 |éditeur=North-Holland
 |année=1952
 |pages totales=x+550
 |sudoc=005505526
 |présentation en ligne=https://books.google.com/books?id=HZAjPwAACAAJ
}} {{commentaire biblio SRL| Nombreuses réimpressions, en 1957, 1959, 1962, 1964, 1967, 1971, 1974, 1980, 1988, 1991, 1996, 2000, 2009 notamment par Wolters-Noordhoff (Groningen) {{ISBN|0720421039}}}}, d'après la notice Sudoc. Nombreuses traductions.
* {{mul|en|fr}} {{Ouvrage
|auteur1=Stephen Cole Kleene
|titre=Mathematical Logic
|éditeur=[[Dover Publications|Dover]]
|année=1967
}} — Réimpression Dover reprint, 2001, {{ISBN|0-486-42533-9}}. Traduction française par [[Jean Largeault]], ''Logique mathématique'', Armand Colin, 1971 et Gabay 1987 {{ISBN|2-87647-005-5}}.

== Voir aussi ==
{{Autres projets
  | commons = Category:Turing machines
  | wikt = machine de Turing
  | wikiversity = Calculabilité et complexité
  | wikiversity titre = Calculabilité et complexité
}}

=== Articles connexes ===
* [[Machine de Turing non déterministe]]
* [[Machine de Turing probabiliste]]
* [[Machine de Turing alternante]]
* [[Machine de Turing symétrique]]
* [[Machine de Blum-Shub-Smale]] : une généralisation à des machines calculant sur <math>\mathbb{R}</math>
* [[Problème de la décision]]
* [[Expérience de pensée]]
* [[Oracle (machine de Turing)]]
* ''[[Imitation Game]]'', film sur la vie d'[[Alan Turing]] avec [[Benedict Cumberbatch]]
* [[Fonction constructible]]

=== Liens externes ===
*Le film [http://videotheque.cnrs.fr/doc=3001 « La Machine de Turing réalisée »] de Christophe Gombert et Hugo Deboise à visionner en ligne gratuitement.
*[http://smf.emath.fr/content/conf%C3%A9rence-bnf-2014-b-chazelle Le génie interrompu d'Alan Turing] : présentation et bibliographie d'une conférence [[Bibliothèque nationale de France|BnF]] de [[Bernard Chazelle]], programmée pour le {{date-|19 mars 2014}}
*{{article | auteur = Hamdi Ben Abdallah | lire en ligne = https://interstices.info/comment-fonctionne-une-machine-de-turing/ | titre = Comment fonctionne une machine de Turing ?| périodique = Interstices | date=22 mars 2013}}, <small>article permettant  d’essayer une machine de Turing.</small>

{{Palette|Informatique théorique}}{{Portail|informatique théorique}}

[[Catégorie:Logique mathématique]]
[[Catégorie:Calculabilité]]
[[Catégorie:Théorie de la complexité des algorithmes]]
[[Catégorie:Théorie des automates]]
[[Catégorie:Alan Turing]]
[[Catégorie:Modèle de calcul]]