Machine de Turing universelle

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

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

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

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

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

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.

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

• (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)