Worldlex Wiki 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 selon une table de règles. Malgré la simplicité du modèle, il est capable d'implémenter n'importe quel algorithme informatique .
La machine fonctionne sur une bande mémoire infinie divisée en cellules discrètes , chacune pouvant contenir un symbole unique tiré d'un ensemble fini de symboles appelé alphabet de la machine. Elle possède une « tête » qui, à tout moment de son fonctionnement, est positionnée au-dessus de l'une de ces cellules, et un « état » sélectionné parmi un ensemble fini d'états. À chaque étape de son fonctionnement, la tête lit le symbole contenu dans sa cellule. Ensuite, en fonction du symbole et de son propre état actuel, la machine écrit un symbole dans la même cellule et déplace la tête d'une position vers la gauche ou la droite , ou interrompt le calcul. Le choix du symbole de remplacement à écrire, de la direction du déplacement de la tête et de l'arrêt du calcul est déterminé par une table finie qui spécifie l'action à entreprendre pour chaque combinaison de l'état actuel et du symbole lu. Comme pour un programme informatique réel, une machine de Turing peut entrer dans une boucle infinie qui ne s'arrêtera jamais.
La machine de Turing a été inventée en 1936 par Alan Turing [ qui l'a d'abord appelée « machine-a » (machine automatique) . C'est son directeur de thèse, Alonzo Church , qui a ensuite forgé l'expression « machine de Turing » dans une revue . Grâce à ce modèle, Turing a pu répondre par la négative à deux questions :
- Existe-t-il une machine capable de déterminer si une machine quelconque sur sa bande est « circulaire » (par exemple, bloquée ou incapable de poursuivre sa tâche de calcul) ?
- Existe-t-il une machine capable de déterminer si une machine quelconque sur sa bande imprime un symbole donné ?
Ainsi, en fournissant une description mathématique d'un dispositif très simple capable de calculs arbitraires, il a pu prouver des propriétés du calcul en général — et en particulier l' impossibilité de calculer l' Entscheidungsproblem , ou « problème de décision » (la question de savoir si toute proposition mathématique est prouvable ou réfutable).
Les machines de Turing ont prouvé l'existence de limitations fondamentales à la puissance du calcul mécanique.
Bien qu’elles puissent exprimer des calculs arbitraires, leur conception minimaliste les rend trop lentes pour le calcul en pratique : les ordinateurs du monde réel sont basés sur des conceptions différentes qui, contrairement aux machines de Turing, utilisent une mémoire à accès aléatoire .
La complétude de Turing désigne la capacité d'un modèle de calcul ou d'un système d'instructions à simuler une machine de Turing. Un langage de programmation Turing-complet est théoriquement capable d'exprimer toutes les tâches réalisables par un ordinateur ; presque tous les langages de programmation sont Turing-complets si l'on fait abstraction des limitations liées à la mémoire finie.
unité centrale de traitement (CPU) qui contrôle toutes les manipulations de données effectuées par un ordinateur. La machine canonique utilise une mémoire séquentielle pour stocker les données. Typiquement, cette mémoire séquentielle est représentée par une bande de longueur infinie sur laquelle la machine peut effectuer des opérations de lecture et d'écriture.En théorie des langages formels , une machine de Turing ( automate ) est capable d' énumérer un sous-ensemble quelconque de chaînes valides d'un alphabet . Un ensemble de chaînes pouvant être énumérées de cette manière est appelé langage récursivement énumérable . La machine de Turing peut également être définie comme un modèle qui reconnaît les chaînes d'entrée valides, plutôt que comme un modèle qui énumère les chaînes de sortie.
Étant donné une machine de Turing M et une chaîne de caractères s quelconque , il est généralement impossible de déterminer si M produira finalement s . Ceci est dû au fait que le problème de l'arrêt est insoluble, ce qui a des implications majeures sur les limites théoriques du calcul.
Une machine de Turing capable de simuler n'importe quelle autre machine de Turing est appelée machine de Turing universelle (MTU, ou simplement machine universelle). Un autre formalisme mathématique, le lambda-calcul , de nature « universelle » similaire, a été introduit par Alonzo Church . Les travaux de Church, étroitement liés à ceux de Turing, ont constitué la base de la thèse de Church-Turing . Cette thèse affirme que les machines de Turing, le lambda-calcul et d'autres formalismes de calcul similaires rendent compte de la notion informelle de méthodes effectives en logique et en mathématiques , et fournissent ainsi un modèle permettant de raisonner sur un algorithme ou une « procédure mécanique » de manière mathématiquement précise, sans être lié à un formalisme particulier. L'étude des propriétés abstraites des machines de Turing a permis de nombreuses avancées en informatique , en théorie de la calculabilité et en théorie de la complexité .
Description physique
Dans son essai de 1948, « Machines intelligentes », Turing écrivait que sa machine se composait de :
…une capacité de mémoire illimitée obtenue sous la forme d’une bande infinie divisée en carrés, sur chacun desquels un symbole pouvait être imprimé. À tout instant, la machine ne contient qu’un seul symbole ; on l’appelle le symbole scanné. La machine peut modifier le symbole scanné, et son comportement est en partie déterminé par ce symbole, mais les symboles présents ailleurs sur la bande n’affectent pas son comportement. Cependant, la bande peut être déplacée dans les deux sens à travers la machine, ce qui constitue l’une de ses opérations élémentaires. Tout symbole sur la bande peut donc éventuellement avoir un cycle.
— Turing 1948
Description
Plus précisément, une machine de Turing se compose de :
- Un ruban divisé en cellules contiguës. Chaque cellule contient un symbole d'un alphabet fini. Cet alphabet comprend un symbole blanc spécial (ici noté « 0 ») et un ou plusieurs autres symboles. Le ruban est supposé extensible à volonté vers la gauche et vers la droite, de sorte que la machine de Turing dispose toujours de la longueur de ruban nécessaire à ses calculs. Les cellules vierges sont initialement remplies avec le symbole blanc. Dans certains modèles, l'extrémité gauche du ruban est marquée d'un symbole spécial ; le ruban s'étend alors indéfiniment vers la droite.
- Une tête de lecture/écriture permet de lire et d'écrire des symboles sur la bande, et de déplacer cette dernière cellule par cellule, de gauche à droite. Dans certains modèles, la tête se déplace tandis que la bande reste immobile.
- Un registre d'état stocke l'état de la machine de Turing, parmi un nombre fini d'états. Parmi ceux-ci figure l' état initial spécial qui sert à initialiser le registre d'état. Ces états, écrit Turing, remplacent « l'état d'esprit » dans lequel se trouverait normalement une personne effectuant des calculs.
- Une table finie d'instructions qui, étant donné l' état ( q i ) dans lequel se trouve actuellement la machine et le symbole ( a j ) qu'elle lit sur la bande (le symbole actuellement sous la tête), indique à la machine d'effectuer les opérations suivantes dans l'ordre (pour les modèles à 5 tuples ) :
- Effacer ou écrire un symbole (en remplaçant un j par un j1 ).
- Déplacer la tête (ce qui est décrit par d k et peut prendre les valeurs suivantes : 'L' pour un pas à gauche ou 'R' pour un pas à droite ou 'N' pour rester au même endroit).
- Supposons le même état ou un nouvel état tel que prescrit (aller à l'état q i1 ).
Dans les modèles à 4 tuples, l'effacement ou l'écriture d'un symbole (a<sub> j1</sub> ) et le déplacement de la tête d'impression (d<sub> k </sub> ) sont spécifiés comme des instructions distinctes. La table indique à la machine (ia) d'effacer ou d'écrire un symbole ou (ib) de déplacer la tête d'impression, puis (ii) d'adopter l'état initial ou un nouvel état, mais pas les deux actions (ia) et (ib) dans la même instruction. Dans certains modèles, si aucune entrée ne correspond à la combinaison actuelle de symbole et d'état dans la table, la machine s'arrête ; d'autres modèles exigent que toutes les entrées soient renseignées.
Chaque partie de la machine (c'est-à-dire son état, ses collections de symboles et la bande utilisée à un moment donné) et ses actions (telles que l'impression, l'effacement et le mouvement de la bande) est finie , discrète et discernable ; c'est la quantité illimitée de bande et de temps d'exécution qui lui confère une quantité illimitée d' espace de stockage .
Définition formelle
D'après Hopcroft et Ullman (1979), une machine de Turing (à une seule bande) peut être formellement définie comme un 7- uplet
Une variante autorise « pas de décalage », par exemple N, comme troisième élément de l'ensemble des directions
Le 7-uplet du castor affairé à 3 états ressemble à ceci (voir plus d'informations sur ce castor affairé dans les exemples de machines de Turing ) :
Au départ, toutes les cellules de ruban sont marquées avec
| Symbole de ruban | État actuel A | État actuel B | État actuel C | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Écrire le symbole | Déplacer la bande | État suivant | Écrire le symbole | Déplacer la bande | État suivant | Écrire le symbole | Déplacer la bande | État suivant | |
| 0 | 1 | R | B | 1 | L | UN | 1 | L | B |
| 1 | 1 | L | C | 1 | R | B | 1 | R | ARRÊT |
Détails supplémentaires nécessaires pour visualiser ou implémenter des machines de Turing
Selon les mots de van Emde Boas (1990) : « L’objet ensembliste [sa description formelle en sept-uplets similaire à celle ci-dessus] ne fournit que des informations partielles sur la façon dont la machine se comportera et sur l’apparence de ses calculs. »
Par exemple,
- De nombreuses décisions devront être prises concernant l'apparence concrète des symboles, ainsi qu'une méthode infaillible pour les lire et les écrire indéfiniment.
- Les opérations de décalage à gauche et à droite peuvent déplacer la tête de lecture/écriture sur la bande, mais lors de la construction d'une machine de Turing, il est plus pratique de faire glisser la bande d'avant en arrière sous la tête.
- La bande peut être de longueur finie et s'étendre automatiquement avec des espaces vides au besoin (ce qui correspond le mieux à la définition mathématique). Cependant, on la conçoit plus souvent comme s'étendant à l'infini à une ou aux deux extrémités et pré-remplie d'espaces vides, sauf sur le fragment fini explicitement défini où se trouve la tête de lecture/écriture (ceci est, bien sûr, irréalisable en pratique). La longueur de la bande ne peut être fixe, car cela ne correspondrait pas à la définition donnée et limiterait considérablement les capacités de calcul de la machine à celles d'un automate linéaire borné si la bande était proportionnelle à la taille de l'entrée, ou à celles d'une machine à états finis si sa longueur était strictement fixe.
Définitions alternatives
Les définitions en littérature peuvent parfois différer légèrement afin de simplifier ou de clarifier les arguments ou les démonstrations, mais cela se fait toujours de manière à ce que la machine résultante possède la même puissance de calcul. Par exemple, l'ensemble pourrait être modifié comme suit :
La convention la plus courante représente chaque « instruction de Turing » dans une « table de Turing » par l'un des neuf 5-uplets, selon la convention de Turing/Davis (Turing (1936) et Davis (2000) ) :
- (définition 1) : (q i , S j , S k /E/N, L/R/N, q m )
- ( état actuel q i , symbole scanné S j , imprimer le symbole S k /effacer E /aucun N , déplacer_bande_d'une_case à gauche L /à droite R /aucun N , nouvel état q m )
D'autres auteurs (Minsky (1967), Hopcroft et Ullman (1979), Stone (1972), adoptent une convention différente, avec le nouvel état q m listé immédiatement 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 , nouvel état q m , imprimer le symbole S k /effacer E /aucun N , déplacer_bande_d'une_case à gauche L /à droite R /aucun N )
Pour le reste de cet article, nous utiliserons la « définition 1 » (la convention de Turing/Davis).
| État actuel | Symbole scanné | Symbole d'impression | Déplacer la bande | État final (c.-à-d. suivant) | 5-uplets |
|---|---|---|---|---|---|
| UN | 0 | 1 | R | B | ( A , 0, 1, R, B ) |
| UN | 1 | 1 | L | C | ( A , 1, 1, L, C ) |
| B | 0 | 1 | L | UN | ( B , 0, 1, L, A ) |
| B | 1 | 1 | R | B | ( B , 1, 1, R, B ) |
| C | 0 | 1 | L | B | ( C , 0, 1, L, B ) |
| C | 1 | 1 | N | H | ( C , 1, 1, N, H ) |
Dans le tableau suivant, le modèle original de Turing n'autorisait que les trois premières lignes, qu'il nommait N1, N2 et N3. Il autorisait l'effacement du « carré scanné » en nommant un symbole 0, S <sub>0 </sub>, qui signifie « effacer » ou « vide », etc. Cependant, il n'autorisait pas l'absence d'impression ; chaque ligne d'instruction comprenait donc « symbole d'impression S<sub> k</sub> » ou « effacer ». Les abréviations sont celles de Turing. Suite à la publication de l'article original de Turing en 1936-1937, les modèles de machines ont autorisé les neuf types possibles de quintuplets :
| Configuration m actuelle (état de Turing) | Symbole de ruban | Opération d'impression | Mouvement sur bande | Configuration m finale (état de Turing) | 5-uplets | commentaires en 5-tuples | 4-tuple | ||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| N1 | q i | S j | Imprimer(S k ) | Gauche L | q m | (q i , S j , S k , L, q m ) | 0 , 1 = S 1 , etc. | ||||||||||||||||||||||||||||||||||||
| N2 | q i | S j | Imprimer(S k ) | Droite R | q m | (q i , S j , S k , R, q m ) | 0 , 1 = S 1 , etc. | ||||||||||||||||||||||||||||||||||||
| N3 | q i | S j | Imprimer(S k ) | 0 , 1 = S 1 , etc. | (q i , S j , S k , q m ) | ||||||||||||||||||||||||||||||||||||||
| 4 | q i | S j | les exemples de machines de Turing . L'utilisation de 4-tuples est moins fréquente : ceux-ci représentent une atomisation supplémentaire des instructions de Turing. L'« État »Le terme « état », employé dans le contexte des machines de Turing, peut prêter à confusion, car il peut avoir deux significations. La plupart des commentateurs postérieurs à Turing ont utilisé « état » pour désigner le nom ou l’identifiant de l’instruction en cours d’exécution, c’est-à-dire le contenu du registre d’état. Or, Turing (1936) a établi une distinction nette entre l’enregistrement de ce qu’il appelait la « configuration m » de la machine et « l’état d’avancement » de la machine (ou de l’utilisateur) dans le calcul, soit l’état actuel du système global. Ce que Turing nommait « formule d’état » inclut à la fois l’instruction en cours et tous les symboles présents sur la bande. il explique comment écrire le nombre de Gödel de la « situation » d'une machine : il place le symbole de « configuration m » q₄ au -dessus du carré lu, approximativement au centre des six carrés non vides du ruban (voir la figure du ruban de Turing dans cet article), et le positionne à droite de ce carré. Kleene désigne cependant « q₄ » comme « l'état de la machine ». Hopcroft et Ullman nomment cette représentation composite la « description instantanée » et suivent la convention de Turing qui consiste à placer l'« état courant » (étiquette d'instruction, configuration m) à gauche du symbole lu (p. 149). Autrement dit, la description instantanée est la somme des symboles non vides à gauche (l'état de la machine), du symbole courant lu par la tête de lecture et des symboles non vides à droite.Exemple : état total du castor occupé à 3 états et 2 symboles après 3 « déplacements » (tiré de l’exemple « course » de la figure ci-dessous) :
Cela signifie : après trois mouvements, la bande contient … 000110000 …, la tête de lecture/écriture scanne le 1 le plus à droite et l’état est A. Les espaces (ici représentés par des « 0 ») peuvent faire partie de l’état total, comme illustré ici : B 01 ; la bande contient un seul 1, mais la tête de lecture/ écriture scanne le 0 (« espace ») à sa gauche et l’état est B. Dans le contexte des machines de Turing, il convient de préciser ce que l'on entend par « état » : l'instruction courante, la liste des symboles sur la bande avec l'instruction courante, ou la liste des symboles sur la bande avec l'instruction courante placée à gauche ou à droite du symbole analysé. Diagrammes d'état
 À droite : le tableau ci-dessus représenté sous forme de diagramme de « transition d'état ». Il est généralement préférable de laisser les grands tableaux sous forme de tableaux (Booth, p. 74). Leur simulation informatique est plus aisée sous cette forme (Booth, p. 74). Cependant, certains concepts, comme les machines à états de « réinitialisation » et les machines à motifs répétitifs (cf. Hill et Peterson, p. 244 et suivantes), sont plus faciles à appréhender sous forme de schéma. Il appartient au lecteur de décider, en fonction du contexte particulier, si un dessin représente une amélioration par rapport à son tableau.  Il convient de rappeler que de tels diagrammes représentent un instantané de leur table figé dans le temps, et non le déroulement (ou « trajectoire ») d'un calcul à travers le temps et l'espace. Alors que la machine « castor actif » suit toujours la même trajectoire d'état à chaque exécution, cela n'est pas vrai pour la machine « copieuse » qui peut recevoir des « paramètres » d'entrée variables. Le diagramme « progression du calcul » illustre la progression du calcul du castor actif à trois états, de son état (instruction) jusqu’à son terme. À l’extrême droite figure la « configuration complète » de Turing (la « situation » de Kleene et la « description instantanée » de Hopcroft-Ullman) à chaque étape. Si la machine était arrêtée et réinitialisée (effacement du registre d’état et de la bande entière), ces « configurations » permettraient de relancer un calcul à n’importe quel point de son avancement. Modèles équivalentsUne machine de Turing est équivalente à un automate à pile (PDA) à une seule pile, rendu plus flexible et concis grâce à l'assouplissement de la contrainte LIFO ( dernier entré, premier sorti ) de sa pile. De plus, une machine de Turing est également équivalente à un PDA à deux piles avec sémantique LIFO standard, une pile modélisant la bande à gauche de la tête et l'autre la bande à droite. À l'autre extrême, certains modèles très simples s'avèrent être équivalents à la machine de Turing , c'est-à-dire qu'ils possèdent la même puissance de calcul que le modèle de la machine de Turing. Les modèles équivalents courants sont la machine de Turing à plusieurs bandes , la machine de Turing à plusieurs pistes , les machines avec entrée et sortie, et la machine de Turing non déterministe (NDTM) par opposition à la machine de Turing déterministe (DTM) pour laquelle la table d'actions comporte au plus une entrée pour chaque combinaison de symbole et d'état. Les machines de Turing en lecture seule et à déplacement vers la droite sont équivalentes aux AFD (ainsi qu'aux ANF par conversion à l'aide de l' algorithme de conversion ANF vers AFD ). À des fins pratiques et didactiques, la machine à registres équivalente peut être utilisée comme un langage de programmation assembleur classique . Une question pertinente est de savoir si le modèle de calcul représenté par les langages de programmation concrets est Turing-équivalent. Si le calcul d'un ordinateur réel repose sur un nombre fini d'états et ne peut donc pas simuler une machine de Turing, les langages de programmation eux-mêmes ne présentent pas nécessairement cette limitation. Kirner et al. (2009) ont montré que parmi les langages de programmation généralistes, certains sont Turing-complets tandis que d'autres ne le sont pas. Par exemple, le C ANSI n'est pas Turing-complet, car toutes ses instanciations (différentes instanciations sont possibles, la norme laissant délibérément certains comportements indéfinis pour des raisons de compatibilité avec les systèmes existants) impliquent une mémoire de taille finie. En effet, la taille des types de données de référence mémoire, appelés pointeurs , est accessible au sein du langage. Cependant, d'autres langages de programmation comme Pascal ne possèdent pas cette caractéristique, ce qui leur permet d'être Turing-complets en principe. Ils ne le sont qu'en principe, car l'allocation de mémoire dans un langage de programmation peut échouer. Autrement dit, le langage peut être Turing-complet si l'on ignore les échecs d'allocation de mémoire, contrairement aux programmes compilés exécutables sur un ordinateur réel. Machines C de choix, machines O d'OracleDès le début de son article (1936), Turing établit une distinction entre une « machine automatique » — dont le « mouvement… est entièrement déterminé par la configuration » — et une « machine à choix » : machine de Turing non déterministe ; Turing a résolu le problème dans une note de bas de page et semble l’écarter de toute considération ultérieure.Une machine oracle ou machine o est une machine a de Turing qui interrompt son calcul à l'état « o » tandis que, pour terminer son calcul, elle « attend la décision » de « l'oracle » — une entité non spécifiée par Turing « si ce n'est pour dire qu'elle ne peut pas être une machine » (Turing (1939)). Machines de Turing universellesComme Turing l'a écrit dans L'Indécidable , (italiques ajoutés) : ordinateur à programme enregistré .complexité de calcul , une machine de Turing universelle à plusieurs bandes n'est plus lente que d' un facteur logarithmique par rapport aux machines qu'elle simule. Ce résultat a été obtenu en 1966 par FC Hennie et RE Stearns .Comparaison avec de vraies machines Les machines de Turing sont plus puissantes que certains autres types d'automates, tels que les automates à états finis et les automates à pile . Selon la thèse de Church-Turing , elles sont aussi puissantes que les machines réelles et capables d'exécuter n'importe quelle opération qu'un programme réel peut réaliser. Ce raisonnement omet un point essentiel : une machine réelle ne pouvant avoir qu'un nombre fini de configurations , elle n'est rien d'autre qu'un automate à états finis, tandis qu'une machine de Turing dispose d'un espace de stockage illimité pour ses calculs. Il existe plusieurs façons d'expliquer pourquoi les machines de Turing sont des modèles utiles d'ordinateurs réels :
Limitesthéorie de la complexité computationnelleInteractionAux débuts de l'informatique, l'utilisation des ordinateurs se limitait généralement au traitement par lots , c'est-à-dire à des tâches non interactives, chacune produisant des données de sortie à partir de données d'entrée données. La théorie de la calculabilité, qui étudie la calculabilité des fonctions reliant les entrées aux sorties et pour laquelle les machines de Turing ont été inventées, reflète cette pratique. Depuis les années 1970, l'utilisation interactive des ordinateurs s'est largement répandue. En principe, il est possible de la modéliser en faisant lire et écrire simultanément des données sur une bande magnétique par un agent externe, à l'instar d'une machine de Turing. Cependant, cette modélisation correspond rarement à la réalité ; c'est pourquoi, pour décrire l'interactivité, on privilégie généralement des alternatives telles que les automates d'entrée/sortie . Comparaison avec le modèle arithmétique du calculLe modèle arithmétique de calcul diffère du modèle de Turing sur deux points :
Certains algorithmes s'exécutent en temps polynomial dans un modèle, mais pas dans l'autre. Par exemple :
Cependant, si un algorithme s'exécute en temps polynomial dans le modèle arithmétique, et que de plus la longueur binaire de tous les nombres impliqués est polynomiale en la longueur de l'entrée, alors il s'exécute toujours en temps polynomial dans le modèle de Turing. On dit alors que cet algorithme s'exécute en temps fortement polynomial . Histoire
Gandy affirme que « les fonctions calculables par (1), (2) et (4) sont précisément celles qui sont calculables par une machine de Turing » . Il cite d'autres propositions de « machines à calculer universelles », notamment celles de Percy Ludgate (1909), Leonardo Torres Quevedo (1914) , Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936) et Howard Aiken (1937). Cependant : les problèmes de Hilbert posés par le célèbre mathématicien David Hilbert en 1900, un aspect du problème n° 10 a circulé pendant près de 30 ans avant d’être formulé précisément. L’énoncé original du problème n° 10 par Hilbert est le suivant :équation diophantienne à nombre quelconque d'inconnues et à coefficients entiers rationnels : concevoir un procédé permettant de déterminer, en un nombre fini d'opérations, si l'équation est résoluble dans l'ensemble des entiers rationnels. Le problème de décision en logique du premier ordre est résolu lorsqu'on connaît une procédure permettant de déterminer, pour toute expression logique donnée, en un nombre fini d'opérations, sa validité ou sa satisfaisabilité… Le problème de décision doit être considéré comme le problème fondamental de la logique mathématique.— cité, avec cette traduction et l’original allemand, dans Dershowitz et Gurevich, 2008 En 1922, cette notion d’ Entscheidungsproblem » s’était quelque peu développée, et H. Behmann a déclaré quecomplètes … Deuxièmement, les mathématiques sont-elles cohérentes … Et troisièmement, les mathématiques sont-elles décidables ? » Les deux premières questions furent résolues en 1930 par Kurt Gödel lors de cette même réunion où Hilbert prononça son discours d’adieu (à son grand regret) ; la troisième – le Alonzo Church de Princeton appellerait plus tard « calculabilité effective », et qu'en 1928, une telle définition n'existait pas. Mais au cours des six ou sept années suivantes, Emil Post a élaboré sa définition d'un ouvrier se déplaçant d'une pièce à l'autre pour écrire et effacer des marques selon une liste d'instructions , tout comme Church et ses deux étudiants, Stephen Kleene et J.B. Rosser, en utilisant le lambda-calcul de Church et la théorie de la récursivité de Gödel (1934). L'article de Church (publié le 15 avril 1936) a montré que le la calculabilité et critiquer la « définition » de Church, mais n'avait rien prouvé.La machine A d'Alan TuringAu printemps 1935, Turing, alors jeune étudiant en master au King's College de Cambridge , releva le défi ; il avait été stimulé par les conférences du logicien M. H.A. Newman « et avait appris d'eux les travaux de Gödel et le problème de la décision… Newman employait le terme « mécanique »… » Dans sa nécrologie de Turing en 1955, Newman écrit : — Gandy Gandy affirme que : raisonnement diagonal permettant de prouver l'indécidabilité.— ibid. Bien que Gandy considérât l'affirmation de Newman ci-dessus comme « trompeuse », cet avis n'est pas partagé par tous. Turing s'intéressa toute sa vie aux machines : « Alan rêvait d'inventer des machines à écrire dès son plus jeune âge ; [sa mère] Mme Turing possédait une machine à écrire ; et il aurait très bien pu commencer par se demander ce que signifiait qualifier une machine à écrire de "mécanique" » (Hodges, p. 96). Pendant ses études doctorales à Princeton, Turing construisit un multiplicateur à logique booléenne (voir ci-dessous). Sa thèse de doctorat, intitulée « Systèmes de logique basés sur les ordinaux », contient la définition suivante d'une « fonction calculable » : Turing (1939 , p. 166)Alan Turing inventa la « machine A » (machine automatique) en 1936. Il soumit son article le 31 mai 1936 à la London Mathematical Society pour publication dans ses Proceedings , mais il ne fut publié qu'au début de 1937 et des tirés à part furent disponibles en février 1937. C'est son directeur de thèse, Alonzo Church , qui forgea plus tard l'expression « machine de Turing » dans une revue. Grâce à ce modèle, Turing put répondre par la négative à deux questions :
Ainsi, en fournissant une description mathématique d'un dispositif très simple capable de calculs arbitraires, il a pu prouver des propriétés du calcul en général et, en particulier, l' incalculabilité de l' Entscheidungsproblem (« problème de décision »). À son retour au Royaume-Uni, Turing fut finalement coresponsable du décryptage des codes secrets allemands créés par les machines de chiffrement appelées « Enigma ». Il participa également à la conception de l'ACE ( Automatic Computing Engine ). « La proposition ACE de Turing était en réalité autonome et ne puisait pas son origine dans l' EDVAC [l'initiative américaine], mais dans sa propre machine universelle » (Hodges, p. 318). Les débats persistent quant à l'origine et à la nature de ce que Kleene (1952) a nommé la thèse de Turing . Ce que Turing a démontré avec son modèle de machine à calculer apparaît dans son article « On Computable Numbers, with an Application to the Entscheidungsproblem » (1937). relais électromécaniques (Hodges, p. 138). « La tâche d'Alan consistait à concrétiser la conception logique d'une machine de Turing dans un réseau de commutateurs actionnés par des relais… » (Hodges, p. 138). Si Turing n'était peut-être au départ qu'un esprit curieux et expérimental, des travaux sérieux dans la même direction étaient menés en Allemagne par Konrad Zuse (1938) et aux États-Unis par Howard Aiken et George Stibitz (1937) ; leurs travaux furent utilisés par les armées de l'Axe et des Alliés pendant la Seconde Guerre mondiale (cf. Hodges, p. 298-299). Au début des années 1950, Hao Wang et Marvin Minsky simplifièrent la machine de Turing (précurseur de la machine post-Turing de Martin Davis ). Parallèlement, des chercheurs européens réduisaient le nouvel ordinateur électronique à un objet théorique semblable à un ordinateur, équivalent à ce que l'on appelle aujourd'hui une « machine de Turing ». À la fin des années 1950 et au début des années 1960, les travaux parallèles de Melzak et Lambek (1961), Minsky (1961) et Shepherdson et Sturgis (1961) ont approfondi ces recherches et ramené la machine de Turing à un modèle abstrait plus convivial, semblable à un ordinateur : la machine à compteurs . Elgot et Robinson (1964), Hartmanis (1971) et Cook et Reckhow (1973) ont poussé ces travaux encore plus loin avec les modèles de la machine à registres et de la machine à accès aléatoire ; mais, fondamentalement, il s'agit toujours de machines de Turing à plusieurs bandes dotées d'un jeu d'instructions de type arithmétique.1970-présent : en tant que modèle de calculAujourd'hui, les compteurs, les registres et les machines à accès aléatoire, ainsi que leur ancêtre la machine de Turing, demeurent les modèles de prédilection des théoriciens qui étudient les questions de calcul théorique . La théorie de la complexité algorithmique , en particulier, recourt à la machine de Turing. Plus d articles de Worldlex WikiRevenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais. Explorer l index | ||||||||||||||||||||||||||||||||||||||||