Machine de Turing

Modèle abstrait de calcul composé d'une bande infinie (ou non bornée) divisée en cellules, d'une tête de lecture/écriture se déplaçant à gauche ou à droite, d'un ensemble fini d'états et d'une fonction de transition qui associe (état courant, symbole courant) à (état suivant, symbole à écrire, déplacement de la tête).