Une machine de Turing est équipée d'une bande infinie divisée en cellules. Chaque cellule peut contenir un symbole, et le ruban peut être déplacé vers la gauche ou vers la droite. Une tête de lecture/écriture est positionnée au-dessus du ruban. Elle peut lire le symbole présent sous elle, écrire un nouveau symbole, et déplacer le ruban vers la gauche ou la droite. La machine a un ensemble fini d'états internes. À chaque étape, la machine est dans l'un de ces états. La machine de Turing fonctionne en suivant une table de transition qui spécifie, pour chaque combinaison d'état actuel et de symbole lu, l'action à effectuer (écrire un symbole, se déplacer vers la gauche ou la droite, changer d'état, etc.).

La fonction de transition définit le comportement de la machine à chaque étape. Elle détermine comment la machine réagit en fonction de l'état actuel et du symbole lu. Ainsi le fonctionnement d'une machine de Turing fait intervenir trois types d'états  : 1) l'initialisation : la machine de Turing commence dans un état initial avec une certaine configuration du ruban; 2) transition : à chaque étape, la machine lit le symbole sous la tête de lecture/écriture, consulte la table de transition pour déterminer l'action à effectuer en fonction de l'état actuel et du symbole lu, puis effectue cette action; 3) répétition : ce processus se répète jusqu'à ce que la machine atteigne un état d'arrêt (acceptation ou rejet) ou entre dans une boucle infinie.