Machine de Turing (Turing machine)

Une machine de Turing représente un modèle informatique mathématique, conceptualisant un dispositif abstrait qui traite les symboles sur une bande sur la base d'un ensemble de règles prédéfinies. Malgré sa simplicité inhérente, ce modèle possède la capacité d'exécuter n'importe quel algorithme informatique imaginable.

Une machine de Turing est un modèle mathématique de calcul décrivant une machine abstraite qui manipule des symboles sur une bande de ruban adhésif selon un tableau de règles. Malgré la simplicité du modèle, il est capable d'implémenter n'importe quel algorithme informatique.

Ce dispositif informatique fonctionne à l'aide d'une bande mémoire infiniment longue, segmentée en cellules distinctes. Chaque cellule est capable de stocker un seul symbole, sélectionné dans une collection finie connue sous le nom d'alphabet de la machine. La machine intègre une « tête » qui, pendant toute phase opérationnelle, est située sur l'une de ces cellules, à côté d'un « état » choisi parmi un ensemble fini d'états possibles. A chaque cycle opérationnel, la tête lit le symbole présent dans sa cellule courante. Par la suite, en fonction du symbole lu et de l'état actuel de la machine, la machine écrit un nouveau symbole dans la même cellule, déplace la tête d'une position vers la gauche ou la droite, ou termine le calcul. La détermination du symbole à écrire, la direction du mouvement de la tête et la décision de s'arrêter sont régies par une table de transition finie, qui dicte l'action appropriée pour chaque combinaison de l'état actuel et du symbole lu. De manière analogue aux programmes informatiques pratiques, une machine de Turing peut entrer dans une boucle infinie, empêchant sa terminaison.

Alan Turing a conçu la machine de Turing en 1936, la qualifiant initialement de « a-machine » (machine automatique). La nomenclature « Machine de Turing » a ensuite été introduite par son directeur de doctorat, Alonzo Church, dans le cadre d'une revue. Grâce au développement de ce modèle, Turing a réussi à fournir des réponses négatives à deux questions importantes :

• Est-il possible de construire une machine capable de déterminer si une machine arbitraire représentée sur sa bande présente un comportement « circulaire », comme le gel ou l'échec de son processus de calcul ?
• Peut-on concevoir une machine qui détermine si une machine arbitraire, telle qu'elle est codée sur sa bande, produira un jour un symbole spécifique ?

En fournissant une description mathématique d'un dispositif remarquablement simple capable d'effectuer des calculs arbitraires, Turing a établi les propriétés fondamentales du calcul de manière générale, démontrant spécifiquement l'incalculabilité du Entscheidungsproblem, également connu sous le nom de « problème de décision » (la question de savoir si chaque énoncé mathématique peut être prouvé ou réfuté).

Les machines de Turing ont démontré de manière concluante les limites inhérentes régissant les capacités du calcul mécanique.

Bien que Les machines de Turing sont théoriquement capables de représenter n'importe quel calcul, leur architecture minimaliste les rend peu pratiques pour les exigences de vitesse de calcul du monde réel. Les ordinateurs contemporains, en revanche, utilisent des conceptions distinctes, intégrant notamment une mémoire vive, qui diffère du modèle à accès séquentiel des machines de Turing.

L'exhaustivité de Turing fait référence à la capacité d'un modèle informatique ou d'un jeu d'instructions à émuler les opérations d'une machine de Turing. Un langage de programmation présentant l'exhaustivité de Turing est, en principe, capable d'articuler toutes les tâches que les ordinateurs peuvent effectuer ; la plupart des langages de programmation atteignent la complétude de Turing lorsque les contraintes pratiques telles que la mémoire finie sont ignorées.

Vue d'ensemble

Une machine de Turing sert de représentation idéalisée d'une unité centrale de traitement (CPU), régissant toutes les manipulations de données au sein d'un ordinateur. Le modèle canonique utilise une mémoire séquentielle pour le stockage des données, généralement conceptualisée comme une bande infiniment longue sur laquelle la machine exécute des opérations de lecture et d'écriture.

Dans le domaine de la théorie du langage formel, une machine de Turing (ou un automate) possède la capacité d'énumérer un sous-ensemble arbitraire de chaînes valides d'un alphabet donné. Une collection de chaînes énumérables par cette méthode est désignée comme un langage énumérable de manière récursive. Alternativement, une machine de Turing peut être conceptualisée comme un modèle conçu pour reconnaître les chaînes d'entrée valides, plutôt que de simplement énumérer les chaînes de sortie.

Considérant une machine de Turing M et une chaîne arbitraire s, il est généralement indécidable si M générera finalement des s. Cette indécidabilité découle de l'insolvabilité inhérente du problème de l'arrêt, un phénomène ayant de profondes implications pour les limites théoriques du calcul.

Une machine de Turing capable de simuler n'importe quelle autre machine de Turing est désignée machine de Turing universelle (UTM), ou simplement machine universelle. Parallèlement, Alonzo Church a introduit le calcul lambda, un autre formalisme mathématique présentant une caractéristique « universelle » comparable. Les contributions de Church, combinées à celles de Turing, ont jeté les bases de la thèse Church-Turing. Cette thèse postule que les machines de Turing, le calcul lambda et les formalismes informatiques analogues résument avec précision le concept informel de méthodes efficaces en logique et en mathématiques. Par conséquent, ils offrent un modèle mathématiquement précis pour analyser des algorithmes ou des « procédures mécaniques », indépendant de tout formalisme spécifique. La recherche sur les attributs abstraits des machines de Turing a considérablement fait progresser la compréhension de l'informatique, de la théorie de la calculabilité et de la théorie de la complexité.

Conception physique

Dans son essai de 1948, « Intelligent Machinery », Turing a décrit sa machine comme comprenant :

...une capacité de mémoire illimitée, réalisée comme une bande infinie segmentée en carrés, chacun capable de contenir un symbole imprimé. A un instant donné, la machine contient un seul symbole, appelé symbole scanné. La machine peut modifier ce symbole scanné, et son comportement opérationnel en est en partie dicté ; cependant, les symboles situés ailleurs sur la bande n'influencent pas les actions immédiates de la machine. Néanmoins, la bande peut être déplacée de manière bidirectionnelle à travers la machine, ce qui constitue l'une de ses opérations fondamentales. Par conséquent, n'importe quel symbole sur la bande peut éventuellement être consulté et traité.

Description opérationnelle

La machine de Turing fournit un modèle mathématique pour un appareil qui manipule mécaniquement une bande. Cette bande contient des symboles que la tête de bande de la machine peut lire et écrire séquentiellement. Son fonctionnement est entièrement régi par un ensemble fini d'instructions élémentaires, par exemple : "à l'état 42, si le symbole observé est 0, écrire un 1 ; si le symbole observé est 1, passer à l'état 17 ; à l'état 17, si le symbole observé est 0, écrire un 1 et passer à l'état 6", et ainsi de suite. Dans son article fondateur, « Sur les nombres calculables, avec une application au problème d'entscheidung », Turing a conceptualisé non pas un appareil mécanique, mais un « ordinateur » humain qui exécute avec diligence ces règles mécaniques déterministes (ou, comme Turing l'a décrit, « de manière décousue »).

Plus précisément, une machine de Turing comprend les composants suivants :

• Une bande, segmentée en cellules contiguës. Chaque cellule stocke un symbole tiré d'un alphabet fini. Cet alphabet comprend un symbole vide désigné (représenté ici par « 0 ») et au moins un autre symbole. La bande est supposée être extensible à l'infini dans les directions gauche et droite, garantissant que la machine de Turing dispose toujours de suffisamment de bande pour ses besoins informatiques. Les cellules non écrites sont présumées contenir le symbole vide. Certains modèles comportent une bande avec une limite gauche distincte, s'étendant ou étant indéfiniment extensible uniquement vers la droite.
• Une tête, capable de lire et d'écrire des symboles sur la bande, et de déplacer la bande précisément une cellule à la fois, à gauche ou à droite. Dans les modèles alternatifs, la tête elle-même bouge tandis que la bande reste fixe.
• Un registre d'état, qui conserve l'état actuel de la machine de Turing à partir d'un ensemble fini d'états possibles. Cet ensemble comprend un état de départ spécifique, utilisé pour initialiser le registre d'état. Turing a noté que ces états servent de substitut formel à « l'état d'esprit » qu'un ordinateur humain connaîtrait généralement lors des calculs.
• Une table finie d'instructions qui, en fonction de l'état actuel de la machine (q_i) et du symbole (a_j) lu sur la bande (c'est-à-dire le symbole sous la tête), ordonne à la machine d'effectuer les actions suivantes dans l'ordre (en particulier pour les 5 tuples). modèles) :

1. Pour effacer ou écrire un symbole (en remplaçant a_j par a_j1).
2. Pour déplacer la tête (représenté par d_k, avec des valeurs possibles : 'L' pour un seul pas vers la gauche, ou 'R' pour un seul pas vers la droite, ou 'N' pour rester immobile).
3. Pour passer au même état ou à un nouvel état comme spécifié (c'est-à-dire, passer à l'état q_i1).

Dans les modèles à 4 tuples, les opérations d'effacement ou d'écriture d'un symbole (a_j1) et de déplacement de la tête vers la gauche ou la droite (d_k) sont définies comme des instructions distinctes. Le tableau opérationnel de la machine indique qu'elle doit soit (ia) effacer ou écrire un symbole ou, soit (ib) déplacer la tête vers la gauche ou la droite, et ensuite (ii) passer à un état nouveau ou existant spécifié. Surtout, les actions (ia) et (ib) ne peuvent pas être exécutées dans la même instruction. Certains modèles précisent que la machine s'arrêtera si aucune entrée n'existe dans le tableau pour la combinaison symbole-état actuelle ; à l'inverse, d'autres modèles exigent que toutes ces entrées soient définies de manière exhaustive.

Chaque composant de la machine, englobant son état, ses collections de symboles et la partie utilisée de la bande à un moment donné, ainsi que ses opérations (par exemple, l'impression, l'effacement et le mouvement de la bande), est intrinsèquement fini, discret et distinguable. Néanmoins, la capacité de la machine en matière d'espace de stockage illimité découle de la bande et du temps d'exécution théoriquement illimités disponibles.

Définition formelle

Conforme à la formulation de Hopcroft & Ullman (1979), une machine de Turing à bande unique est formellement définie comme un 7-tuple : M = ⟨<!-- ⟨ --> Q , Γ<!-- Γ --> , b , Σ<!-- Σ --> , δ<!-- δ --> , q §4041§ , F ⟩ {\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle } où

• ${\displaystyle \Gamma }$ représente un ensemble fini et non vide de symboles alphabétiques de bande.
• ${\displaystyle b\in \Gamma }$ désigne le symbole vide, qui est le seul symbole autorisé à apparaître infiniment souvent sur la bande à n'importe quelle étape du calcul.
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}>$ représente l'ensemble des symboles d'entrée, en particulier les symboles autorisés dans la configuration initiale du bande.
• ${\displaystyle Q}$ est défini comme un ensemble fini et non vide d'états.
• q §1011§ ∈ Q {\displaystyle q_{0}\in Q} désigne l'état initial.
• ${\displaystyle F\subseteq Q>$ constitue l'ensemble des états finaux, également appelés états d'acceptation. Le contenu initial de la bande est considéré comme accepté par ${\displaystyle M}$ si la machine s'arrête finalement dans un état appartenant à ${\displaystyle F}$.
• L'expression ${\displaystyle \delta :(Q\setminus F)\times \Gamma \rightharpoonup Q\times \Gamma \times \{L,R\}}$ représente la fonction partielle connue sous le nom de fonction de transition, où « L » désigne un décalage vers la gauche et « R » signifie un décalage vers la droite. Devrait ${\displaystyle \delta }$ manque de définition pour l'état actuel et le symbole de la bande, la machine cessera de fonctionner. Conceptuellement, cette fonction de transition dicte l'état ultérieur à partir de l'état actuel, le symbole qui remplacera le symbole actuel sous la tête et la direction du prochain mouvement de la tête.

Une configuration alternative permet une opération "sans décalage", désignée par "N", qui fonctionne comme un troisième élément dans l'ensemble des mouvements directionnels ${\displaystyle \{L,R\}>$.

La spécification à 7 tuples pour le castor occupé à 3 états est présentée comme suit :

• ${\displaystyle Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}}$ (représentant l'ensemble des états) ;
• Γ<!-- Γ --> = { §1314§ , §1718§ } {\displaystyle \Gamma =\{0,1\}} (indiquant les symboles de l'alphabet de la bande) ;
• b = §1011§ {\displaystyle b=0} (identifiant le symbole vide) ;
• Σ<!-- Σ --> = { §1314§ } {\displaystyle \Sigma =\{1\}} (spécifiant les symboles d'entrée) ;
• q §1011§ = A {\displaystyle q_{0}={\mbox{A}}} (désignant l'état initial) ;
• ${\displaystyle F=\{{\mbox{HALT}}\}}$ (comprenant les états finaux) ;
• ${\displaystyle \delta =}$ (la fonction de transition, détaillée dans la table d'état suivante).

Initialement, chaque cellule de la bande est désignée par le symbole §67§ {\displaystyle 0} .

Des spécifications supplémentaires sont nécessaires pour la visualisation ou la mise en œuvre pratique des machines de Turing.

Selon van Emde Boas (1990), "L'objet de la théorie des ensembles [sa description formelle en sept tuples similaire à celle ci-dessus] ne fournit que des informations partielles sur la façon dont la machine se comportera et à quoi ressembleront ses calculs."

Par exemple,

• De nombreuses décisions doivent être prises concernant la représentation visuelle des symboles et le développement d'un mécanisme robuste pour leur lecture et écriture indéfinies.
• Alors que les opérations de décalage vers la gauche et vers la droite déplacent conceptuellement la tête de bande sur la bande, une approche plus pragmatique de construction d'une machine de Turing physique implique que la bande se déplace de manière bidirectionnelle sous une tête stationnaire.
• La bande peut être conceptualisée comme finie, s'étendant automatiquement avec des symboles vierges selon les besoins, ce qui correspond étroitement à la définition mathématique. Cependant, une perspective plus répandue considère que la bande s'étend à l'infini dans une ou dans les deux directions, pré-remplie de blancs, à l'exception du segment fini actuellement sous la tête de bande (un concept non réalisable en pratique). Surtout, la longueur de la bande ne peut pas être fixée, car cela s'écarterait de la définition établie et restreindrait considérablement les capacités de calcul de la machine. Une telle limitation réduirait sa puissance à celle d'un automate linéaire borné si la taille de la bande était proportionnelle à l'entrée, ou à celle d'une machine à états finis si sa longueur était strictement prédéterminée.

Définitions alternatives

Des variations dans les définitions apparaissent parfois dans la littérature académique, généralement pour simplifier les arguments ou améliorer la clarté des preuves. Ces modifications sont systématiquement mises en œuvre sans altérer la puissance de calcul fondamentale de la machine résultante. Par exemple, l'ensemble des mouvements possibles de la tête de bande pourrait être étendu à partir de ${\displaystyle \{L,R\}}$ pour inclure ${\displaystyle \{L,R,N\}}$, où N (représentant "Aucun" ou "Aucune opération") permet à la machine de rester sur sa cellule de bande actuelle plutôt que de se déplacer vers la gauche ou la droite. Une telle modification n'augmente pas la capacité de calcul inhérente de la machine.

Selon la convention établie par Turing (1936) et Davis (2000), l'approche la plus répandue définit chaque « instruction de Turing » dans une « table de Turing » comme l'un des neuf 5-uplets distincts.

(Définition 1) : (q_i, S_j, S_k/E/N, L/R/N, q_m)

( état actuel q_i , symbole scanné S_j , symbole à imprimer S_k/effacer E/aucune opération N , mouvement de la bande vers la gauche L/droite R/aucun mouvement N , état ultérieur q_m )

En revanche, d'autres chercheurs, dont Minsky (1967), Hopcroft et Ullman (1979) et Stone (1972), emploient une convention alternative dans laquelle le nouvel état q_m est positionné directement après le symbole scanné S_j.

(Définition 2) : (q_i, S_j, q_m, S_k/E/N, L/R/N)

( état actuel q_i , symbole scanné S_j , état ultérieur q_m , symbole à imprimer S_k/effacer E/aucune opération N , mouvement de la bande à gauche L/droite R/aucun mouvement N )

Dans le reste de cet article, la « Définition 1 », qui s'aligne sur la convention Turing/Davis, sera systématiquement utilisée.

Dans le tableau suivant, le modèle initial de Turing incorporait uniquement les trois premiers types d'instructions, qu'il désignait N1, N2 et N3. Il a facilité l'effacement du « carré numérisé » en définissant un 0ème symbole, S₀, comme « effacer » ou « vide ». Néanmoins, son cadre d'origine ne permettait pas les opérations sans impression, ce qui signifie que chaque ligne d'instruction imposait soit « imprimer le symbole S_k » ou « effacer ». Les abréviations utilisées sont celles introduites par Turing. Suite à la publication de l'article fondateur de Turing en 1936-1937, les modèles de machines ultérieurs se sont développés pour s'adapter aux neuf types potentiels de cinq-uplets.

Toute table de Turing, qui constitue une liste complète d'instructions, peut être formulée à l'aide des neuf 5-uplets susmentionnés. Pour des considérations techniques spécifiques, les trois instructions non imprimables ou « N » (types 4, 5 et 6) sont souvent considérées comme superflues.

Moins fréquemment, des 4-uplets sont rencontrés, ce qui signifie une atomisation plus granulaire des instructions de Turing.

Le concept d'« État »

Dans le discours entourant les machines de Turing, le terme « État » peut prêter à ambiguïté en raison de ses doubles interprétations. La plupart des commentateurs post-Turing définissent « état » comme l'identifiant ou le désignateur de l'instruction actuellement prévue pour exécution, faisant effectivement référence au contenu du registre d'état. Cependant, Turing (1936) lui-même a établi une distinction claire entre ce qu'il a appelé la « configuration m » de la machine (un enregistrement) et « l'état d'avancement » de la machine (ou de l'ordinateur humain) au cours d'un calcul, qui englobe l'état général de l'ensemble du système. La « formule d'état » de Turing intègre spécifiquement à la fois l'instruction actuelle et tous les symboles présents sur la bande.

La progression du calcul à une étape donnée est entièrement définie par l'ensemble d'instructions et les symboles présents sur la bande. Par conséquent, l'état du système peut être représenté par une expression singulière, une séquence de symboles comprenant le contenu de la bande, suivi d'un symbole delta (Δ, supposé unique), puis des instructions. Cette expression composite est appelée « formule d'état ».

Dans sa publication précédente, Turing a étendu ce concept en illustrant un exemple dans lequel un symbole représentant la « configuration m » actuelle (l'étiquette des instructions) était positionné sous le carré numérisé, à côté de tous les symboles sur la bande. Il a désigné cela comme la « configuration complète ». Pour restituer cette « configuration complète » sur une seule ligne, il a positionné l'étiquette d'état ou la configuration m à gauche du symbole scanné.

Kleene (1952) présente une variante de ce concept, démontrant la méthode de codage de la « situation » d'une machine à l'aide d'un nombre de Gödel. Il positionne le symbole de "configuration m" q₄ au-dessus du carré scanné, approximativement centré parmi les six carrés non vides de la bande, et le place à droite du carré scanné. Cependant, Kleene identifie spécifiquement « q₄ » comme « l'état de la machine ». En revanche, Hopcroft et Ullman se réfèrent à ce composite comme à la « description instantanée » et adhèrent à la convention de Turing consistant à placer « l'état actuel » (étiquette d'instruction, configuration m) à gauche du symbole numérisé (p. 149). Ainsi, une description instantanée comprend les symboles non vides à gauche, l'état de la machine, le symbole actuellement scanné par la tête et les symboles non vides à droite.

Exemple : L'état total d'un castor occupé à 3 états et 2 symboles après trois "mouvements" informatiques.

1A1

Cette notation indique qu'après trois opérations, la bande contient la séquence "...000110000...", la tête balayant actuellement le "1" le plus à droite, et l'état de la machine est désigné par A. Les symboles vides, représentés ici par des « 0 », peuvent être incorporés dans l'état total, comme illustré par B01. Dans ce cas, la bande contient un seul « 1 », mais la tête scanne le « 0 » (vierge) à sa gauche, et l'état est B.

Dans le domaine des machines de Turing, le terme « état » nécessite des éclaircissements quant à son référent spécifique : s'il désigne l'instruction actuelle, la compilation de symboles sur la bande combinée avec l'instruction actuelle, ou la compilation de symboles sur la bande avec l'instruction actuelle positionnée soit à gauche soit à droite de l'instruction actuelle. symbole scanné.

Diagrammes d'état

Le tableau précédent est représenté sous la forme d'un diagramme de « transition d'état ».

En règle générale, les ensembles de données étendus sont présentés plus efficacement sous forme de tableau (Booth, p. 74), facilitant leur simulation par ordinateur. Néanmoins, des éléments conceptuels spécifiques — tels que des machines incorporant des états de « réinitialisation » ou présentant des modèles répétitifs (cf. Hill et Peterson p. 244ff) — peuvent être mieux compris lorsqu'ils sont visualisés graphiquement.

La détermination de savoir si une représentation graphique offre une amélioration par rapport à son homologue tabulaire dépend de l'évaluation du lecteur dans le contexte spécifique.

Il est impératif de réitérer que ces diagrammes représentent une représentation statique de leurs tables correspondantes, un instantané figé dans le temps, et non la progression dynamique ou la « trajectoire » d'un calcul à travers des dimensions temporelles et spatiales. Bien qu'une machine castor occupée suive systématiquement une trajectoire d'état identique lors de chaque exécution, ce principe ne s'applique pas à une machine de « copie », qui prend en charge des « paramètres » d'entrée variables.

Le diagramme de « progression du calcul » illustre l'avancement séquentiel de « l'état » (instruction) du castor occupé à trois états tout au long de son processus de calcul. À l'extrême droite, la « configuration complète » de Turing (appelée alternativement « situation » de Kleene ou « description instantanée » de Hopcroft-Ullman) est présentée pour chaque étape. Si la machine était arrêtée et que son "registre d'état" et la bande entière étaient remis à blanc, ces "configurations" enregistrées permettraient la reprise d'un calcul à tout moment de sa progression.

Modèles équivalents

De nombreuses machines qui peuvent sembler posséder une plus grande capacité de calcul qu'une simple machine universelle de Turing sont manifestement équivalentes en puissance de calcul (Hopcroft et Ullman p. 159, cf. Minsky (1967)). Bien que de telles machines puissent offrir des avantages en termes de vitesse, d’efficacité de la mémoire ou de concision du jeu d’instructions, elles n’améliorent pas la puissance de calcul fondamentale, ce qui signifie qu’elles ne peuvent pas traiter un plus large éventail de fonctions mathématiques. Ce principe est en outre soutenu par la thèse Church-Turing, qui émet l'hypothèse que toute fonction calculable peut être calculée par une machine de Turing, affirmant ainsi l'universalité du calcul de Turing dans tous les modèles théoriques.

Une machine de Turing présente l'équivalence avec un automate pushdown à pile unique (PDA) lorsque la contrainte de pile dernier entré, premier sorti (LIFO) de ce dernier est relâchée, améliorant ainsi sa flexibilité et sa concision. De plus, une machine de Turing peut être modélisée comme un PDA à deux piles fonctionnant selon la sémantique LIFO standard, où une pile représente le segment de bande à gauche de la tête de lecture/écriture et l'autre modélise le segment à droite.

À l'inverse, il a été démontré que certains modèles informatiques très simplifiés possèdent l'équivalence de Turing, ce qui signifie une capacité de calcul identique au modèle de machine de Turing standard.

Les modèles équivalents fréquemment rencontrés incluent la machine de Turing multi-bandes, la machine de Turing multipiste, machines intégrant des mécanismes d'entrée et de sortie explicites et machine de Turing non déterministe (NDTM). Le NDTM contraste avec la machine de Turing déterministe (DTM), où la table d'action spécifie une transition unique pour chaque combinaison donnée de symbole et d'état.

Les machines de Turing limitées aux opérations de lecture seule et de déplacement vers la droite sont équivalentes aux automates finis déterministes (DFA) et, par extension, aux automates finis non déterministes (NFA) grâce à l'application de l'algorithme de conversion NFA en DFA.

Dans les applications pratiques et à des fins pédagogiques, la machine à registres équivalente sert de modèle pour un langage de programmation d'assemblage typique.

Une enquête pertinente concerne l'équivalence de Turing des modèles informatiques. incarné par des langages de programmation spécifiques. Bien que les calculs informatiques réels fonctionnent dans le cadre de contraintes d’états finis, excluant la simulation directe d’une machine de Turing, les langages de programmation eux-mêmes ne sont pas intrinsèquement soumis à cette limitation. Les recherches de Kirner et al. (2009) indique que les langages de programmation à usage général présentent une variabilité dans l'exhaustivité de Turing, certains possédant cette propriété et d'autres en manquant. Par exemple, ANSI C n'est pas Turing complet car toutes ses instanciations, même celles avec des comportements non définis autorisés par la norme de compatibilité héritée, présupposent un espace mémoire fini. Cette limitation provient de la capacité du langage à accéder à la taille des types de données de référence en mémoire, en particulier les pointeurs. A l’inverse, les langages de programmation comme Pascal, qui manquent de cette spécificité, peuvent être considérés comme Turing complets en principe. Cette exhaustivité « en principe » reconnaît que même si un langage peut être complet de Turing si les échecs d'allocation de mémoire sont ignorés, les programmes compilés exécutés sur du matériel physique restent limités par des ressources limitées.

Machines de choix et machines Oracle

Dans son article fondateur de 1936, Turing faisait la différence entre une « machine automatique », caractérisée par son « mouvement... entièrement déterminé par la configuration », et une « machine à choix », qu'il décrivait comme suit :

...dont le mouvement n'est que partiellement déterminé par la configuration... Lorsqu'elle rencontre une configuration ambiguë, une telle machine ne peut pas continuer jusqu'à ce qu'une sélection arbitraire soit effectuée par un opérateur externe. Ce scénario s'appliquerait aux machines utilisées dans l'analyse des systèmes axiomatiques.

Turing (1936) n'a pas fourni d'autres précisions sur les machines à choix au-delà d'une note de bas de page, dans laquelle il a décrit une méthode permettant à une machine automatique (une-machine) de "trouver toutes les formules prouvables du calcul [de Hilbert]" comme alternative à l'emploi d'une machine à choix. Il a postulé que « les choix sont toujours entre deux possibilités 0 et 1. Chaque preuve sera alors déterminée par une séquence de choix i₁, i₂, ..., i_n (i§67§ = 0 ou 1, i§8_{9§ = 0 ou 1, ..., in = 0 ou 1), et donc le nombre 2ⁿ + i§14}15_{16§n-1 + i§181920§n-2 + ... +in détermine complètement la preuve. La machine automatique exécute successivement la preuve 1, la preuve 2, la preuve 3,..."}

Cette méthode démontre efficacement comment une méthode déterministe (c'est-à-dire automatique) La machine de Turing peut émuler les opérations d'une machine de Turing non déterministe. Turing a abordé ce concept dans une note de bas de page, concluant apparemment sa discussion sur le sujet.

Une machine oracle, ou o-machine, fonctionne comme une machine de Turing qui arrête temporairement son calcul à l'état "o", en attendant une décision de "l'oracle" pour terminer son calcul. Turing (1939) a décrit cet oracle comme une entité dont la nature reste indéterminée, au-delà de la stipulation cruciale selon laquelle il ne peut pas être lui-même une machine.

Machines de Turing universelles

Comme l'explique Turing dans The Undecidable (c'est nous qui soulignons) :

Une machine unique peut être conçue pour calculer n'importe quelle séquence calculable. Si cette machine, désignée U, reçoit une bande contenant les quintuples séparés par des points-virgules d'une autre machine informatique, M, alors U calculera par la suite la séquence identique à M.

Bien que cette découverte soit désormais largement acceptée, elle a été considérée comme révolutionnaire en 1936. Le modèle informatique de Turing, qu'il a appelé la « machine universelle » (en abrégé « U »), est largement considéré comme l'avancée théorique fondamentale qui a ouvert la voie au concept d'ordinateur à programme stocké.

L'article fondateur de Turing englobe fondamentalement l'invention de l'ordinateur moderne et plusieurs techniques de programmation associées.

En ce qui concerne la complexité informatique, une machine de Turing universelle multi-bandes présente une réduction des performances d'un seul facteur logarithmique par rapport aux machines qu'elle simule. Cette découverte a été établie en 1966 par F. C. Hennie et R. E. Stearns.

Comparaison avec les machines physiques

Les machines de Turing possèdent une plus grande puissance de calcul que certains autres automates, notamment les machines à états finis et les automates pushdown. La thèse Church-Turing postule que les machines de Turing sont équivalentes en puissance aux ordinateurs physiques, capables d'exécuter n'importe quelle opération qu'un programme réel peut réaliser. Cependant, cette affirmation néglige une distinction essentielle : une machine physique, contrainte par un nombre fini de configurations, fonctionne fondamentalement comme une machine à états finis, alors qu'une machine de Turing bénéficie d'une capacité de stockage illimitée pour ses calculs.

Plusieurs justifications expliquent pourquoi les machines de Turing servent de modèles efficaces pour les ordinateurs physiques :

• Tout calcul réalisable par un ordinateur physique peut également être exécuté par une machine de Turing. Par exemple, « Une machine de Turing est capable de simuler n'importe quel type de sous-programme rencontré dans les langages de programmation, englobant les procédures récursives et tous les mécanismes de passage de paramètres établis » (Hopcroft et Ullman, p. 157). De plus, un automate à états finis (FSA) suffisamment grand peut modéliser n’importe quel ordinateur physique, à l’exclusion des opérations d’entrée/sortie. Par conséquent, toutes les limitations identifiées pour les machines de Turing s'appliquent également aux ordinateurs physiques.
• La seule distinction réside dans la capacité théorique d'une machine de Turing à manipuler une quantité illimitée de données. Néanmoins, dans un laps de temps fini, une machine de Turing, tout comme une machine physique, ne peut traiter qu'une quantité finie de données.
• À l'instar d'une machine de Turing, la capacité de stockage d'une machine physique peut être étendue progressivement grâce à l'ajout de disques ou d'autres supports de stockage.
• La description de programmes destinés à des machines physiques à l'aide de modèles abstraits plus simples entraîne souvent une complexité bien plus grande que celle utilisant des machines de Turing. Par exemple, un algorithme décrit par une machine de Turing peut impliquer seulement quelques centaines d'états, alors que son équivalent automate déterministe fini (DFA) sur une machine physique spécifique peut comprendre des quadrillions d'états, ce qui rend la représentation DFA peu pratique pour l'analyse.
• Les machines de Turing fournissent un cadre permettant de décrire les algorithmes, quelle que soit leur consommation de mémoire. Même si toutes les machines physiques actuelles ont une mémoire limitée, cette limite peut théoriquement augmenter indéfiniment au fil du temps. Par conséquent, les machines de Turing permettent de formuler des déclarations sur des algorithmes qui sont (théoriquement) perpétuellement valides, non affectés par les progrès de l'architecture des machines informatiques conventionnelles.
• Les algorithmes exécutés sur des machines abstraites équivalentes à Turing peuvent utiliser des types de données de précision arbitraire et ne sont pas soumis à des conditions inattendues, telles que l'épuisement de la mémoire.

Limitations

Théorie de la complexité informatique

Les machines de Turing présentent une limitation dans leur capacité à modéliser avec précision les avantages spécifiques de certaines configurations architecturales. Par exemple, les ordinateurs à programme stocké contemporains illustrent une machine abstraite plus spécialisée connue sous le nom de modèle de machine à programme stocké à accès aléatoire (RASP). Semblable à une machine de Turing universelle, la RASP stocke son « programme » dans une « mémoire » externe, distincte des « instructions » de la machine à états finis. Cependant, contrairement à une machine de Turing universelle, la RASP présente une gamme infinie de « registres » distincts, numérotés et illimités – des « cellules » de mémoire capables de contenir n'importe quel nombre entier (cf. Elgot et Robinson (1964), Hartmanis (1971) et Cook-Rechow (1973)). La machine à états finis du RASP intègre un adressage indirect, permettant au contenu d'un registre de servir d'adresse à un autre ; par conséquent, le « programme » du RASP peut accéder à n’importe quel registre de sa séquence. Cette différence fondamentale permet des optimisations informatiques basées sur des indices de mémoire inaccessibles avec une machine de Turing générale. Par conséquent, l'utilisation de machines de Turing pour établir des limites sur les temps d'exécution peut conduire à la dérivation d'une « fausse limite inférieure » pour certains algorithmes, attribuable à une hypothèse trop simpliste inhérente au modèle de la machine de Turing. La recherche binaire sert d'illustration pertinente, démontrant des performances supérieures lorsqu'elle est mise en œuvre à l'aide du modèle informatique RASP par rapport au modèle de machine de Turing.

Interaction

Au cours des premières étapes de l'informatique, l'utilisation de l'ordinateur se limitait principalement au traitement par lots, impliquant des tâches non interactives générant des données de sortie à partir d'entrées spécifiées. La théorie de la calculabilité, qui étudie la calculabilité des fonctions mappant les entrées aux sorties et pour lesquelles les machines de Turing ont été conçues, reflète ce paradigme opérationnel historique.

À partir des années 1970, l'application interactive des ordinateurs a gagné en popularité. Bien qu'il soit théoriquement possible de modéliser une telle interaction en supposant qu'un agent externe lise et écrit simultanément sur la bande d'une machine de Turing, cette approche représente rarement avec précision les processus interactifs du monde réel. Par conséquent, lors de la caractérisation de l'interactivité, des modèles alternatifs tels que les automates d'E/S sont généralement privilégiés.

Comparaison avec le modèle arithmétique de calcul

Le modèle arithmétique de calcul diverge du modèle de Turing sur deux points principaux :

• Dans le modèle arithmétique, chaque nombre réel occupe une seule cellule mémoire, alors que dans le modèle de Turing, les besoins de stockage d'un nombre réel dépendent du nombre de bits nécessaires à sa représentation.
• Dans le modèle arithmétique, les opérations arithmétiques fondamentales sur les nombres réels, notamment l'addition, la soustraction, la multiplication et la division, sont exécutées en une seule étape de calcul. A l'inverse, dans le modèle de Turing, le temps d'exécution de chaque opération arithmétique est déterminé par la longueur de ses opérandes.

Certains algorithmes présentent une complexité en temps polynomial dans un modèle mais pas dans l'autre. Par exemple :

• L'algorithme euclidien réalise une exécution en temps polynomial dans le modèle de Turing, mais ce n'est pas le cas dans le modèle arithmétique.
• Algorithme qui traite n nombres et calcule ensuite §910§ §1314§ n {\displaystyle 2^{2^{n}}} par quadrature répétée fonctionne en temps polynomial dans le modèle arithmétique, mais pas dans le modèle de Turing. Cet écart se produit car la longueur en bits requise pour représenter le résultat augmente de façon exponentielle avec la taille d'entrée.

Néanmoins, un algorithme qui s'exécute en temps polynomial dans le modèle arithmétique, à condition que la longueur binaire de tous les nombres impliqués soit également polynomiale dans la longueur d'entrée, présentera invariablement une complexité en temps polynomial dans le modèle de Turing. Un tel algorithme se caractérise par son exécution en temps fortement polynomial.

Contexte historique

Contexte historique : machines informatiques

Robin Gandy (1919-1995), ancien élève et associé de longue date d'Alan Turing (1912-1954), a retracé les origines conceptuelles de la « machine à calculer » jusqu'à Charles Babbage (vers 1834) et a articulé ce qu'il a appelé « la thèse de Babbage » :

Que l'intégralité du développement analytique et des opérations puisse désormais être exécutée par des machines.

L'analyse de Gandy du moteur analytique de Babbage définit cinq opérations fondamentales (Gandy, pp. 52-53) :

1. Celles-ci incluent les fonctions arithmétiques d'addition (+), de soustraction « appropriée » (−) et de multiplication (×), où la soustraction « appropriée » est définie de telle sorte que x − y = 0 si y ≥ x.
2. Toute séquence composée de ces opérations constitue une opération valide.
3. L'itération d'une opération, définie comme la répétition d'une opération P n fois.
4. Itération conditionnelle, impliquant la répétition d'une opération P n fois, conditionnée à la réussite d'un test T.
5. Transfert conditionnel, également appelé instruction "goto" conditionnelle.

Gandy affirme que "les fonctions qui peuvent être calculées par (1), (2) et (4) sont précisément celles qui sont calculables par Turing". Il fait également référence à d'autres propositions de « machines à calculer universelles », telles que celles de Percy Ludgate (1909), Leonardo Torres Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936) et Howard Aiken (1937). Néanmoins :

… l'accent est mis sur la programmation d'une séquence itérable fixe d'opérations arithmétiques. L'importance fondamentale de l'itération conditionnelle et du transfert conditionnel pour une théorie générale des machines à calculer n'est pas reconnue…

Le problème de l'Entscheidungs, communément appelé « problème de décision », trouve son origine dans la dixième question posée par Hilbert en 1900.

En ce qui concerne les problèmes formulés par le célèbre mathématicien David Hilbert en 1900, une facette spécifique du problème n°10 avait été discutée conceptuellement pendant près de trois décennies avant sa formulation précise. La déclaration originale de Hilbert pour le problème n° 10 est présentée ci-dessous :

10. Détermination de la solvabilité d'une équation diophantienne. Étant donné une équation diophantienne avec un nombre quelconque de quantités inconnues et avec des coefficients intégraux rationnels : Concevoir un processus selon lequel il peut être déterminé en un nombre fini d'opérations si l'équation est résoluble en nombres entiers rationnels. Le problème d'Entscheidungs [problème de décision pour la logique du premier ordre] est résolu lorsque nous connaissons une procédure qui permet à toute expression logique donnée de décider par un nombre fini d'opérations de sa validité ou de sa satisfiabilité... Le problème d'Entscheidungs doit être considéré comme le problème principal de la logique mathématique.

En 1922, le concept de « problème d'Entscheidung » avait évolué, conduisant H. Behmann à énoncer ceci :

... la forme la plus générale du problème d'Entscheidungs [est] la suivante :

Une prescription bien définie, généralement applicable, est requise qui permettra de décider en un nombre fini d'étapes la vérité ou la fausseté d'une assertion purement logique donnée...

Behmann remarque que... le problème général est équivalent au problème de décider quelles propositions mathématiques sont vraies.

Si l'on était capable de résoudre le problème d'Entscheidungs, alors on aurait une "procédure pour résoudre de nombreux (voire tous) problèmes mathématiques".

Lors du congrès international des mathématiciens de 1928, Hilbert "a formulé ses questions de manière assez précise. Premièrement, les mathématiques étaient-elles complètes... Deuxièmement, les mathématiques étaient-elles cohérentes... Et troisièmement, les mathématiques étaient-elles décidables ?" Kurt Gödel a fourni des réponses aux deux premières questions en 1930, lors de la même assemblée où Hilbert a prononcé son discours de retraite, une évolution qui aurait déplu à Hilbert. La troisième question, concernant le problème de l'Entscheidungs, est restée sans réponse jusqu'au milieu des années 1930.

Un défi principal était la condition préalable à une définition précise d'une "prescription générale applicable", un concept appelé plus tard "calculabilité effective" par le professeur Alonzo Church de Princeton. En 1928, une telle définition formelle n’existait pas. Cependant, au cours des six à sept années suivantes, Emil Post a formulé une définition impliquant un travailleur manipulant des marques dans des pièces conformément aux instructions. Parallèlement, Church, avec ses étudiants Stephen Kleene et J. B. Rosser, ont développé leurs propres définitions en utilisant le lambda-calcul de Church et la théorie de la récursion de Gödel (1934). L'article fondateur de Church, publié le 15 avril 1936, démontrait l'« indécidabilité » du problème de l'Entscheidungs, précédant de près d'un an les conclusions similaires de Turing (l'article de Turing fut soumis le 28 mai 1936 et publié en janvier 1937). Pendant ce temps, Emil Post soumit un article concis à l'automne 1936, établissant la priorité de Turing sur Post. Alors que Church servait d'arbitre pour l'article de Turing, Turing a eu l'occasion d'examiner le travail de Church et d'y annexer ensuite une annexe décrivant une preuve que le lambda-calcul de Church et ses propres machines pouvaient calculer des fonctions identiques.

L'approche de Church présentait cependant une méthodologie distincte et un peu moins robuste. En revanche, la construction de Turing offrait un argument plus direct dérivé de principes fondamentaux, résolvant ainsi les lacunes de la démonstration originale de Church.

Post, à l'inverse, avait simplement posé une définition de la calculabilité et critiqué la « définition » de Church sans fournir aucune preuve formelle.

La A-Machine d'Alan Turing

Au printemps 1935, alors qu'il était étudiant à la maîtrise au King's College de Cambridge, Turing accepta ce défi. Son intérêt a été éveillé par les conférences du logicien M. H. A. Newman, grâce auxquelles il s'est familiarisé avec le travail de Gödel et le problème de l'Entscheidungs. Newman a fréquemment employé le terme « mécanique », comme indiqué dans sa nécrologie de Turing de 1955, où il a déclaré : 

Lorsqu'on lui a demandé de définir un processus « mécanique », Turing a répondu de manière caractéristique : « Quelque chose qui peut être fait par une machine », entreprenant ensuite la tâche agréable d'analyser le concept global d'une machine informatique.

Gandy affirme :

Je suppose, bien que sans connaissance définitive, que l'objectif initial de Turing était de démontrer l'indécidabilité du problème de l'Entscheidungs. Il a raconté que « l'idée principale » de son article est née alors qu'il était dans les prés de Grantchester au cours de l'été 1935. Ce concept central aurait pu être soit son analyse détaillée du calcul, soit sa compréhension de l'existence d'une machine universelle, qui permettrait alors un argument diagonal pour établir l'insolvabilité.

Bien que Gandy ait considéré la déclaration susmentionnée de Newman comme « trompeuse », cette perspective n'est pas universellement acceptée. Turing a maintenu toute sa vie une fascination pour les machines ; par exemple, « Alan avait rêvé d'inventer des machines à écrire lorsqu'il était enfant ; [sa mère] Mme Turing avait une machine à écrire ; et il aurait très bien pu commencer par se demander ce que signifiait appeler une machine à écrire « mécanique » » (Hodges p. 96). Au cours de ses études doctorales à Princeton, Turing a construit un multiplicateur de logique booléenne. Sa thèse de doctorat, "Systèmes de logique basés sur des ordinaux", fournit la définition ultérieure d'une "fonction calculable" :

Comme indiqué précédemment, "une fonction est effectivement calculable si ses valeurs peuvent être déterminées par un processus purement mécanique". Cette affirmation peut être interprétée littéralement, définissant un processus purement mécanique comme un processus exécutable par une machine. Il est possible de fournir une description mathématique, sous une forme standardisée, des architectures de ces machines. La progression de ces concepts culmine dans la définition par l'auteur d'une fonction calculable et l'équivalence de la calculabilité avec la calculabilité effective. Démontrer l'équivalence de ces trois définitions [la troisième étant le λ-calcul], bien que n'étant pas intrinsèquement difficile, nécessite des efforts considérables.

Alan Turing a conçu la « a-machine » (machine automatique) en 1936. Il a soumis son article fondateur à la London Mathematical Society pour ses Actes le 31 mai 1936 ; cependant, il fut publié au début de 1937, et les tirés à part furent disponibles en février de la même année. Alonzo Church, le conseiller doctoral de Turing, a ensuite introduit le terme « machine de Turing » dans une revue. En utilisant ce modèle, Turing a fourni des réponses négatives à deux questions fondamentales :

• Existe-t-il une machine capable de déterminer si une machine arbitraire représentée sur sa bande est « circulaire » (c'est-à-dire qu'elle entre dans une boucle infinie ou arrête son processus de calcul) ?
• Peut-on construire une machine qui vérifie si une machine arbitraire représentée sur sa bande imprimera un jour un symbole spécifié ?

Par conséquent, en proposant une description mathématique d'un dispositif remarquablement simple capable d'effectuer des calculs arbitraires, il a réussi à démontrer les propriétés générales du calcul, en particulier l'incalculabilité du Entscheidungsproblem (le « problème de décision »).

À son retour au Royaume-Uni, Turing a finalement partagé la responsabilité du déchiffrement des codes secrets allemands générés par les machines de cryptage « The Enigma ». Il a également participé à la conception de l'Automatic Computing Engine (ACE), Hodges (p. 318) notant que « la proposition ACE [de Turing] était effectivement autonome et que ses racines ne résidaient pas dans l'EDVAC [l'initiative des États-Unis], mais dans sa propre machine universelle. » Des débats persistent concernant la genèse et le caractère de ce que Kleene (1952) a appelé la thèse de Turing. Néanmoins, ce que Turing a prouvé avec son modèle de machine informatique est présenté dans son article "Sur les nombres calculables, avec une application au problème d'Entscheidungs" (1937).

[que] le problème de Hilbert Entscheidungsproblem n'a pas de solution... Je propose donc de démontrer l'absence d'une procédure générale pour vérifier la prouvabilité d'une formule U donnée dans le calcul fonctionnel K, ce qui implique qu'aucune machine, lorsqu'elle est dotée d'une telle formule U, ne peut finalement déterminer sa prouvabilité.

La deuxième preuve de Turing illustre ce concept : la requête « Cette machine imprime-t-elle jamais 0 ? » représente un problème indécidable, indiquant l'absence d'une procédure algorithmique générale pour le résoudre.

1937-1970 : l'émergence de l'ordinateur numérique et la genèse de l'informatique

En 1937, pendant ses études doctorales à Princeton, Turing a construit indépendamment un multiplicateur numérique (logique booléenne), fabriquant ses relais électromécaniques (Hodges, p. 138). Son objectif était de mettre en œuvre l'architecture logique d'une machine de Turing en utilisant un réseau de commutateurs actionnés par relais (Hodges, p. 138). Parallèlement aux efforts exploratoires de Turing, d'importantes recherches parallèles étaient en cours : Konrad Zuse en Allemagne (1938) et Howard Aiken et George Stibitz aux États-Unis (1937) poursuivaient des développements similaires. Les résultats de ces efforts furent ensuite exploités par les forces de l’Axe et les forces alliées pendant la Seconde Guerre mondiale (cf. Hodges, pp. 298-299). Du début au milieu des années 1950, Hao Wang et Marvin Minsky ont simplifié la machine de Turing en une forme plus rudimentaire, qui a servi de précurseur à la machine Post-Turing de Martin Davis. Simultanément, des chercheurs européens ont conceptualisé l’ordinateur électronique naissant comme une entité théorique équivalente à ce qui est aujourd’hui reconnu comme une « machine de Turing ». La fin des années 1950 et le début des années 1960 ont été témoins des progrès convergents de Melzak et Lambek (1961), de Minsky (1961) et de Shepherdson et Sturgis (1961), qui ont étendu les travaux européens en affinant la machine de Turing pour en faire un modèle abstrait plus accessible, semblable à un ordinateur, connu sous le nom de contre-machine. Des recherches ultérieures menées par Elgot et Robinson (1964), Hartmanis (1971) et Cook et Reckhow (1973) ont approfondi ces concepts, en introduisant les modèles de machines à registres et de machines à accès aléatoire, qui représentent fondamentalement des machines de Turing multi-bandes équipées d'un jeu d'instructions de type arithmétique.

1970-présent : la machine de Turing comme modèle informatique

Actuellement, les machines à compteurs, à registres et à accès aléatoire, ainsi que leur ancêtre, la machine de Turing, restent les modèles préférés des théoriciens explorant les questions liées à la théorie du calcul. Notamment, la théorie de la complexité informatique utilise fréquemment la machine de Turing :

Dans la théorie de la complexité basée sur les machines, deux modèles ont pris de l'importance, en fonction des objets informatiques manipulés (par exemple, des entiers non négatifs ou des chaînes alphanumériques) :

la machine de Turing multibande hors ligne, qui sert de modèle conventionnel pour le calcul orienté chaînes ; et la machine à accès aléatoire (RAM), telle que conceptualisée par Cook et Reckhow, qui simule l'ordinateur idéalisé de style Von Neumann.

À l'inverse, dans le domaine connexe de l'analyse des algorithmes, le modèle RAM assume ce rôle principal.

Notes éditoriales

Remarques

Références bibliographiques

Littérature primaire, réimpressions et ouvrages collectifs

Thèse de l'Église