Machine de Turing, dispositif de calcul hypothétique présenté en 1936 par le mathématicien et logicien anglais Alan M. Turing. À l’origine, Turing concevait la machine comme un outil mathématique capable de reconnaître infailliblement les propositions indécidables – c’est-à-dire les énoncés mathématiques qui, dans un système d’axiomes formels donné, ne peuvent être démontrés comme étant vrais ou faux. (Le mathématicien Kurt Gödel avait démontré que de telles propositions indécidables existent dans tout système suffisamment puissant pour contenir l’arithmétique). Turing a plutôt prouvé qu’il ne peut jamais exister de méthode algorithmique universelle pour déterminer si une proposition est indécidable.
La machine de Turing n’est pas une machine au sens ordinaire du terme mais plutôt un modèle mathématique idéalisé qui réduit la structure logique de tout dispositif de calcul à l’essentiel. Telle qu’elle est envisagée par Turing, la machine exécute ses fonctions selon une séquence d’étapes discrètes et ne prend qu’un seul d’une liste finie d’états internes à un moment donné. La machine elle-même se compose d’une bande infiniment extensible, d’une tête de bande capable d’effectuer diverses opérations sur la bande, et d’un mécanisme de contrôle modifiable dans la tête qui peut stocker des instructions à partir d’un ensemble fini d’instructions. La bande est divisée en carrés, chacun d’entre eux étant soit vierge, soit imprimé d’un nombre fini de symboles. La tête de bande a la capacité de se déplacer, de lire, d’écrire et d’effacer n’importe quel carré et peut également passer à un autre état interne à tout moment. Tout acte de ce type est déterminé par l’état interne de la machine et la condition de la case balayée à un moment donné. La sortie de la machine, c’est-à-dire la solution à une question mathématique, peut être lue à partir du système une fois que la machine s’est arrêtée. (Cependant, dans le cas des propositions indécidables de Gödel, la machine ne s’arrêterait jamais, et cela est devenu connu sous le nom de « problème de l’arrêt »)
En incorporant toutes les caractéristiques essentielles du traitement de l’information, la machine de Turing est devenue la base de tous les ordinateurs numériques ultérieurs, qui partagent le schéma de base de la machine, à savoir un dispositif d’entrée/sortie (bande et lecteur), une mémoire (stockage du mécanisme de contrôle) et une unité centrale de traitement (mécanisme de contrôle).