La macchina di Alan Turing

Nastro iniziale: 
Programma:
(0,*) > (1,C,s) (1,*) > (2,I,s) (2,*) > (3,A,s) (3,*) > (4,O,s)

Carica un esempio: Ciao Ciao infinito Mistero

Canvas needed for this page!

Istruzioni

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

• Innanzitutto la macchina è dotata di un nastro composto da infinite caselle — ciascuna capace di ospitare una lettera; in nastro può scorrere verso destra o verso sinistra di una casella alla volta.
• Vi è poi un dispositivo, chiamato testina, in grado di leggere la lettera presente nella casella sulla quale è posizionato, e di sostituirla con una nuova lettera.
• In ogni momento la macchina si trova in un stato (inizialmente lo stato 0).
• Il funzionamento della macchina è dettato da un programma, ovvero un catalogo di mosse; ciascuna mossa determina, a partire dallo stato in cui si trova la macchina e dal simbolo letto dalla testina, qual è il prossimo stato in cui si troverà la macchina, come sostituire il simbolo letto, e in che direzione far scorrere il nastro di una casella.
  Più precisamente, una mossa è della forma ( S1, x ) > ( S2, y, a ) dove S1 e S2 sono stati, x e y sono lettere, e a può valere s (come sinistra), d (come destra) o - (per indicare nessun movimento); il significato di questa mossa è il seguente: "Se la macchina è nello stato S1 e la testina legge la lettera x, si passi nello stato S2, si scriva la lettera y al posto di x e si muova il nastro di una casella nella direzione indicata da a".

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:

• Ogni mossa va scritta su di una sola riga
• I nomi degli stati (S1 e S2) possono essere composti solo dai caratteri ABCDEFGHIJKLMNOPQRSTUVXYWZ0123456789
• Le lettere che vengono lette e scritte sul nastro (x e y) possono essere solo ABCDEFGHIJKLMNOPQRSTUVXYWZ. La cella vuota si indica con il simbolo *
• Le azioni (a) sono uno dei caratteri d, s, - indicanti rispettivamente uno spostamento del nastro di una casella verso destra, verso sinistra e nessun movimento.

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".