Qfyilyi

Cet article ou cette section ne s'appuie pas, ou pas assez, sur des sources secondaires ou tertiaires (mars 2013).

Pour améliorer la vérifiabilité de l'article ou de cette section, merci de citer les sources primaires à travers l'analyse qu'en ont faite des sources secondaires indiquées par des notes de bas de page (modifier l'article).

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 |

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 |

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 |

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

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

Idées générales |

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 |

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 |

Annexes |

Articles connexes |

• Machine de Turing non déterministe


• Machine de Turing probabiliste


• Automate fini


• Théorie de la complexité des algorithmes

Bibliographie |

• (en) Sanjeev Arora et Boaz Barak, Computational complexity : a modern approach, Cambridge New York, Cambridge University Press, 2009(ISBN 9780521424264, 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(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. (ISBN 0-393-32229-7)

• Portail de l'informatique théorique