Machine de Turing universelle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, une machine de Turing universelle est une machine de Turing qui peut simuler n'importe quelle machine de Turing sur n'importe quelle donnée d'entrée. La machine universelle réalise cela en lisant de son propre ruban la description de la machine à simuler et la donnée d'entrée de celle-ci.

Alan Turing a imaginé cette 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.

Fonctionnement et caractéristiques[modifier | modifier le code]

Toute machine de Turing calcule le résultat d'une fonction partielle sur des chaînes de caractères composées des caractères de son alphabet. En ce sens, une machine de Turing se comporte comme un ordinateur avec un programme déterminé.

Mais, comme Alan Turing le décrivit, 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.

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é tag system (en).

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[1]. 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.

Source[modifier | modifier le code]

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

  1. Annonce sur la page du Wolfram 2,3 Turing Machine Research Prize.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (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, 1e éd. (ISBN 0-393-32229-7)