Machine de Turing universelle

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. Cette machine est considérée par certains (par exemple, Martin Davis) 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

Machine de Turing

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

Turing a conçu sa machine universelle pour étudier un problème posé par David Hilbert en 1928 : le problème de décision (de l'allemand 'Entscheidungsproblem'). Ce problème a été formulé dans le cadre du programme de Hilbert ayant pour but d’assurer le fondement des mathématiques, en axiomatisant rigoureusement diverses branches du domaine. Ce programme énonce les trois 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 de sa véracité.

Le problème de décision, est précisément une tentative de formalisation du problème de la décidabilité, à l'aide d'un formalisme développé par Gottlob Frege, le calcul des prédicats. Un des énoncés possibles de ce problème est le suivant :

Trouver un algorithme qui détermine si une phrase énoncée dans le formalisme du calcul des prédicats est valide, c'est-à-dire vraie quelle que soit la sémantique des objets et relations qu'elle met en œuvre.

C’est maintenant que les logiciens Alonzo Church et Alan Turing entrent en scène.

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.

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. Il parvient également à démontrer qu'il existe des phrases dont on ne peut déterminer la validité par un algorithme en mettant en évidence le problème de l'arrêt.

Encodage d'une machine de Turing

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ée 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é

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 machine altérer ses instructions en est un bon mécanisme. »^{[réf. nécessaire]}

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 …

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 à être de plus en plus intrigué par les machines de Turing universelles.

En 1945, il publia le Premier brouillon de rapport de l’EDVAC, 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.

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 Cambridge qui décroche le titre de « premier ordinateur électronique numérique à programme enregistré complet et opérationnel » le 6 mai 1949.

Simulation d'une machine de Turing

Idées générales

Comme le nombre d'états d'une machine est a priori fini, 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

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. 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.

Une machine de Turing n'est pas le meilleur moyen de coder de façon compacte un calculateur universel. Le lambda-calcul binaire (en) est un outil qui en augmente beaucoup plus la densité. John Tromp, qui en est à l'origine, propose un terme de ce calcul qui code un interpréteur universel en 657 bits d’information.

Annexes

Articles connexes

• Turing-complet
• Machine de Turing non déterministe
• Machine de Turing probabiliste
• Automate fini
• Théorie de la complexité des algorithmes
• Complexité de Kolmogorov
• Brainfuck

Bibliographie

• (en) Sanjeev Arora et Boaz Barak, Computational complexity : a modern approach, Cambridge New York, Cambridge University Press, 2009, 579 p. (ISBN 978-0-521-42426-4, lire en ligne), chap. 1.4 & 1.7 (« Machines as strings and the universal Turing machine » et « Proof of theorem 1.9 »)
• (en) Jack Copeland (éditeur), The Essential Turing : Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Oxford UK, Oxford University Press, 2004, 613 p. (ISBN 0-19-825079-7)
• (en) Martin Davis (What is Computation?) et Lynn Arthur Steen (éditeur), Mathematics Today : Twelve Informal Essays, New York NY, Vintage Books (Random House) (ISBN 978-0-394-74503-9).
• (en) Martin Davis, Engines of Logic : Mathematicians and the Origin of the Computer, New York NY, W. W. Norton & Company, 2000, 1^re éd., 257 p. (ISBN 0-393-32229-7)