Machine de Turing universelle

vignette|upright=1.5|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. 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é.