En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été 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 ».
Une machine de Turing est composée des éléments suivants :
Un ruban infini divisé en case consécutives.
Une tête de lecture qui peut lire et écrire des symboles sur les cases
Un registre d'état qui mémorise l'état courant de de la machine de Turing
Une table d'actions qui indique à la machine quel symbole écrire sur le ruban ou bien comment déplacer la tête de lecture.
Son fonctionnement est alors le suivant : à 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 à une fonction de transition
Pour ajouter 1, on utilise la table d'action suivante :
Elle se lit de cette manière pour les deux premières lignes :
Si elle est à l’état 1 et trouve une case vide, elle n’écrit rien, décale le ruban d’une case à gauche et passe à l’état 2.
Si elle est à l’état 2 et lit un 0, elle écrit 0, décale le ruban à gauche et reste à l’état 2.