Machine de Turing universelle

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Une machine de Turing quelconque M réalise un calcul à partir d'une entrée écrite sur son ruban. Une machine de Turing universelle U simule le calcul de M sur l'entrée de M à partir d'une description de M et de l'entrée de M écrits sur le ruban de U.

En informatique, plus précisément en informatique théorique, une machine de Turing universelle est une machine de Turing qui peut simuler n'importe quelle machine de Turing sur n'importe quelle entrée. Une machine universelle prend en entrée la description de la machine à simuler et l'entrée de cette dernière.

Alan Turing a imaginé une telle machine en 1936[réf. nécessaire]. Cette machine est considérée par certains (par exemple, Martin Davis[réf. nécessaire]) comme l'origine de l'ordinateur à programme enregistré conçu par John von Neumann (1946) qui porte maintenant son nom : l'architecture de von Neumann.

Principe d'une machine de Turing universelle[modifier | modifier le code]

Machine de Turing[modifier | modifier le code]

Une machine de Turing est un modèle de calcul composé d'un système de transitions, d'un ruban et d'une tête de lecture/écriture. Étant donné un mot d'entrée m, la machine effectue des opérations élémentaires de calcul ː lire un caractère, écrire un caractère, déplacer la tête de lecture/écriture à gauche ou à droite d'une case. Si la machine s'arrête, on appelle f(m) le contenu du ruban. Sinon, si la machine boucle, f(m) n'est pas défini. Ainsi, la machine calcule le résultat d'une fonction partielle f. En ce sens, une machine de Turing se comporte comme un ordinateur avec un programme déterminé.

Origine de la machine de Turing universelle[modifier | modifier le code]

L’année 1900 est une année marquante pour les mathématiques.

C’est en effet au cours de la conférence au congrès international des mathématiciens à Paris de cette même année que le mathématicien David Hilbert a proposé la liste des 23 problèmes non résolus qu’il jugeait des plus importants.

Le deuxième problème énoncé est le suivant :

« Peut-on prouver la cohérence de l'arithmétique ? En d'autres termes, peut-on démontrer que les axiomes de l'arithmétique ne sont pas contradictoires ? »

Hilbert s’opposant pertinemment au pessimisme scientifique de l’époque, ou autrement la doctrine « Ignorabimus », prônée notamment par le physiologiste allemand Emil du Bois-Reymond pour qui il était tout à fait normal que des questions sur les aspects de l’univers restaient sans réponses, ne s’est pas arrêté là. Il a en effet lancé le programme de Hilbert[1], avec l’aide de logiciens notables de cette époque, dont Wilhelm Ackermann, John von Neumann et Jacques Herbrand, qui avait pour but d’assurer le fondement des mathématiques, en axiomatisant rigoureusement diverses branches du domaine. C’est alors qu’il énonce les 3 axes les plus importants à prouver pour la fondation d’un système mathématique solide, à savoir :

-La complétude, ou le fait que tout prédicat juste dans le système peut être prouvé.

-La cohérence, ou le fait qu’il ne doit pas y avoir de contradictions dans le système.

-La décidabilité, ou le fait que pour un prédicat donné, nous pouvons par le biais d’une « méthode efficace » (la notion d’algorithme n’étant pas d’actualité à l’époque) décider sa véracité.

Le mathématicien allemand Kurt Gödel commence par énoncer son premier théorème de l’incomplétude en 1930, qui stipule que pour un système supposé cohérent, il existe certains prédicats qui ne peuvent être ni prouvés ni réfutés dans ce système, autrement dit que ce système est incomplet (Ces mêmes prédicats peuvent être par contre prouvés dans des systèmes plus grand).

Ayant assisté à l’exposé de Gödel sur le premier théorème, von Neumann le contacte en affirmant avoir trouvé un corollaire prouvant qu’il n’est pas possible de prouver la cohérence des systèmes. Mais Gödel était arrivé à ce résultat indépendamment, qu’il publie en 1931 sous le nom du deuxième théorème de l’incomplétude qui énonce que pour un système supposé cohérent, la cohérence même n’est pas prouvable dans ce même système, répondant au fameux second problème de Hilbert.

Gerhard Gentzen, lui, montre en 1935 que la cohérence de l’arithmétique peut par contre être prouvée en élargissant notre système, à savoir en assumant l’induction transfinie.

C’est maintenant que les logiciens Alonzo Church et Alan Turing entrent en scène, en résolvant le dernier mystère de Hilbert, la décidabilité[2].

Dans le but de répondre négativement au problème de la décision énoncé par Hilbert, Church définit le lambda calcul, la première théorie définissant rigoureusement ce qu’est une « méthode » ou « procédure » efficace à la résolution d’un problème et utilisant les notions de fonctions récursives introduites par Jacques Herbrand et Kurt Gödel. Il a en effet prouvé, par l’absurde, qu’une méthode générale décidant si un prédicat est juste ou pas ne peut exister[3].

Alan Turing, quant à lui, crée le concept des machines de Turing dans ce même but, indépendamment de Church, la même année[4].

Soit le prédicat P suivant : Tout nombre entier pair supérieur à 3 peut s’écrire comme la somme de deux nombres premiers.

D'après la thèse de Turing, nous pouvons créer une machine de Turing « semi-décidable » qui itère sur tous les entiers pairs et essaye de les écrire comme combinaison de deux nombres premiers et rejette au premier contre-exemple.

Forcément, une telle machine ne s’arrêtera jamais si le prédicat est vrai, et c’est principalement ce que veut démontrer Turing. S’il a pu réduire ce dernier prédicat en une telle machine, il doit aussi réduire le prédicat Q : « Nous pouvons prouver P », qui est en fait le vrai problème de la décidabilité, en une autre machine. C’est alors pourquoi la machine de Turing universelle a été créée.

En effet, de la même manière que le prédicat de la décidabilité se base sur le prédicat même qu’il doit décider, une Machine de Turing universelle se base sur la description de la machine qu’elle veut simuler.

Encodage d'une machine de Turing[modifier | modifier le code]

Mais, comme Alan Turing le décrivit[réf. nécessaire], on peut encoder la table d'actions d'une machine de Turing sous la forme d'une chaîne de caractères. On peut donc tenter de construire une machine de Turing qui suppose l'existence sur son ruban d'une chaîne de caractères encodant une table d'actions, suivie d'une chaîne de caractères constituant les données effectives du ruban, et calcule le contenu du ruban que la machine de Turing encodée aurait calculé.

Comme Alan Turing le montra dans son article fondateur, il est possible de créer une telle machine de Turing et, puisqu'elle peut simuler le comportement de n'importe quelle autre machine de Turing, on l'appelle « machine de Turing universelle ».

Grâce à cet encodage des tables d'actions sous forme de chaînes de caractères, il devient en principe possible que les machines de Turing répondent à des questions à propos du comportement d'autres machines de Turing. Cependant, la plupart de ces questions sont indécidables, c'est-à-dire que la fonction en question ne peut pas être calculée par une machine de Turing. Par exemple, la question de savoir si une machine de Turing atteint à un moment donné un état d'arrêt ou ne l'atteint jamais pour une entrée particulière, ou pour toutes les entrées possibles, connue sous le nom de problème de l'arrêt, fut démontré comme étant indécidable par Turing. Le théorème de Rice montre que toute propriété non triviale sur le langage accepté par une machine de Turing est indécidable.

Une machine de Turing universelle est Turing-complète. Elle peut calculer 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, en supposant une définition raisonnable de ces termes.

Ordinateur à programme enregistré[modifier | modifier le code]

Si la notion de la capacité à pouvoir simuler n’importe quelle autre machine de la même classe (à savoir, machine de Turing dans notre cas) a été introduite bien avant, par Charles Babbage et sa machine analytique (pouvant simuler n’importe quelle autre machine à calculer en l’ayant programmé au travers des cartes du métier Jacquard, devenant ainsi le premier concept ressemblant à un ordinateur à usage général), la machine de Turing universelle a marqué les constructeurs pionniers des ordinateurs par une autre idée révolutionnaire, à savoir, de stocker les programmes en mémoire non sur des cartes, pouvant ainsi les modifier.

Avec une telle architecture, la machine peut désormais changer sa table d’actions en cours d’action (puisque la tête peut à la fois lire et écrire), et donc se reprogrammer.

Alan Turing dit d’ailleurs à ce propos :

« Nous voulons une machine qui apprend de ses expériences […] et la possibilité de laisser la machiner altérer ses instructions en est un bon mécanisme. »

C’est d’ailleurs en 1945 qu’il rejoint le Laboratoire National de Physique à Londres sous la direction John Womersley, en publiant le premier document détaillant les spécifications de la construction d’un ordinateur à usage général et à programme enregistré, l'Automatic Computing Engine (ACE), dont un prototype a été construit pour la première fois en 1950 par Edward Newman, Jim Wilkinson, Michael Woodger et autres …[5]

Von Neumann, qui venait de rejoindre le groupe de construction de l’ENIAC dirigé par J. Presper Eckert et John Mauchly en 1944, commença à s’intriguer de plus en plus par les machines de Turing universelle[5].

En 1945, il publia le Premier brouillon de rapport de l’EDVAC[6], qui devint le premier article publié décrivant la conception d’un ordinateur à l’architecture que nous connaissons aujourd’hui au nom d’architecture de von Neumann. Malheureusement, l’EDVAC ne sera complètement opérationnel qu’en 1951.

Ce n’est qu’en 1948 que le Small-Scale Experimental Machine (SSEM) de l'Université de Manchester, construit par F.C. Williams et Tom Kilburn devient le premier « ordinateur » électronique ayant exécuté un programme enregistré en mémoire[5].

Mais le SSEM n’étant pas considéré comme un ordinateur achevé mais plutôt une démonstration de faisabilité du concept, c’est le EDSAC de Cambrige qui décroche le titre de « premier ordinateur électronique numérique à programme enregistré complet et opérationnel » le 6 mai 1949[5].

Simulation d'une machine de Turing[modifier | modifier le code]

Idées générales[modifier | modifier le code]

Comme le nombre d'états d'une machine est a priori fini mais quelconque, Papadimitriou suggère de représenter un état par un entier et donc de représenter un état par la représentation binaire de cet entier[réf. nécessaire].

Minimisation[modifier | modifier le code]

Si on élargit la définition pour y inclure les machines de Turing qui simulent des modèles de calcul Turing-complets, et non plus seulement les machines de Turing qui simulent directement d'autres machines de Turing, une machine de Turing universelle peut être relativement simple, et utiliser seulement quelques états et symboles. Par exemple, il existe une machine de Turing universelle de taille 2×18 (c'est-à-dire 2 états, et 18 symboles). Les plus petites machines de Turing universelles connues ont les tailles suivantes : 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. Ces dernières simulent un modèle appelé systèmes de tague.

Une machine de Turing de taille 2×3, proposée par Stephen Wolfram, a été annoncée comme la plus petite machine de Turing universelle[7]. La preuve est due à Alex Smith. Cependant la notion d'universalité utilisée dans cette preuve n'est pas la même que celle décrite informellement ci-dessus. En particulier, elle nécessite d'écrire une infinité de symboles initialement sur le ruban pour préparer le calcul.

Références[modifier | modifier le code]

  1. Richard Zach, The Stanford Encyclopedia of Philosophy, Metaphysics Research Lab, Stanford University, (lire en ligne)
  2. B. Jack Copeland, The Stanford Encyclopedia of Philosophy, Metaphysics Research Lab, Stanford University, (lire en ligne)
  3. (en) Alonzo Church, « A note on the Entscheidungsproblem », The Journal of Symbolic Logic, vol. 1, no 1,‎ , p. 40–41 (ISSN 0022-4812 et 1943-5886, DOI 10.2307/2269326, lire en ligne)
  4. (en) A. M. Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », Proceedings of the London Mathematical Society, vol. s2-42, no 1,‎ , p. 230–265 (ISSN 0024-6115, DOI 10.1112/plms/s2-42.1.230, lire en ligne)
  5. a, b, c et d « AlanTuring.net A Brief History of Computing », sur www.alanturing.net (consulté le 11 mai 2018)
  6. John von Neumann, « First Draft of a Report on the EDVAC », IEEE Annals of the History of Computing, vol. 15, no 4,‎ , p. 27–75 (ISSN 1058-6180, DOI 10.1109/85.238389, lire en ligne)
  7. Annonce sur la page du Wolfram 2,3 Turing Machine Research Prize.

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]