modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur
imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique »
largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité
La procédure est formulée en termes d'étapes élémentaires du type : « si vous êtes dans l'état 42 et que le symbole contenu sur la case que vous regardez est « 0 », alors remplacer ce symbole par un « 1 », passer dans l'état 17, et regarder maintenant la case adjacente à droite »
Définition:
une machine de Turing est un concept abstrait
Comporte les éléments suivants:
Un ruban infini divisé en cases consécutives.
Chaque case contient un symbole d'un alphabet fini donné.
L'alphabet contient un symbole spécial appelé « symbole blanc » ('0' dans les exemples qui suivent), et un ou plusieurs autres symboles
de longueur infinie vers la gauche ou vers la droite
les cases du ruban contiennent par défaut le « symbole blanc »
Une tête de lecture/écriture qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban
Un registre d'état qui mémorise l'état courant de la machine de Turing.
Le nombre d'états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l'état initial de la machine avant son exécution
Une table d'actions qui indique à la machine quel symbole écrire sur le ruban, comment déplacer la tête de lecture (par exemple « <- » pour une case vers la gauche)
Si aucune action n'existe pour une combinaison donnée d'un symbole lu et d'un état courant, la machine s'arrête
Fonctionnement:
À chaque étape de son calcul, la machine évolue en fonction de l'état dans lequel elle se trouve et du symbole inscrit dans la case du ruban où se trouve la tête de lecture.
Ces deux informations permettent la mise à jour de l'état de la machine grâce à la fonction de transition.
À l'instant initial, la machine se trouve dans l'état q_{0} , et le mot inscrit sur le ruban est l'entrée du programme.
La machine s'arrête lorsqu'elle rentre dans un état terminal.
Le résultat du calcul est alors le mot inscrit sur le ruban.