La macchina di Alan Turing



Nastro iniziale: 
Programma:

Canvas needed for this page!

Istruzioni

Il funzionamento della Macchina di Turing si basa su pochi concetti.

Una volta avviata, la macchina continua l'esecuzione del programma fintanto che esiste una mossa che riporta come primo elemento lo stato attuale della macchina e come secondo la lettera letta dalla testina. Se non c'è una mossa di questo tipo, la macchina si ferma. Valgono inoltre le seguenti regole:

Per esempio: l'istruzione ( 0,* ) > ( 1,C,s ) significa:"Se la macchina è nello stato 0 e la testina legge una casella vuota, si passi nello stato 1, si scriva la lettera C e si muova il nastro di una casella verso sinistra".