machine de Turing

machine universelle

CALCUL
INFORMATIQUE

Une machine de Turing est un modèle de machine théorique fondamental en informatique. Elle est à la base des ordinateurs et du concept d’algorithme.
Le principe en est dû à Alan Turing qui mit au point en 1944 le premier ordinateur électromécanique destiné à décoder les messages des allemands.
Elle est constituée d’une tête de lecture comportant un nombre fini d’états internes, d’un ruban supposé de longueur infinie et d’un symbole pouvant être utilisé une infinité de fois. Cela suffit à effectuer toutes les opérations possibles.
On peut en donner la définition suivante :
Une machine de Turing est la donnée d’un quintuplet (Q, A, p, b, d) où
Q est l’ensemble (fini) des états;
A est l’alphabet (fini);
p est l’état initial (élément de Q);
b est un symbole n’appartenant pas à A appelé symbole blanc;
d est la fonction de transition de Q x B dans (B U {}) x Q, avec B := A U {b}.