Una macchina, tramite un dispositivo di lettura e scrittura, sa esaminare i caratteri scritti su una striscia di carta divisa in quadretti, un carattere per quadretto.
La macchina procede a scatti e, ad ogni scatto, può cambiare il carattere che sta esaminando e può rimanere ferma o spostarsi per esaminare il carattere di destra o quello di sinistra; ad ogni scatto, il comportamento della macchina (che viene qui descritto da una riga di una tabella) dipende dallo stato in cui la macchina si trova e dal carattere in esame.Ad esempio supponiamo che la striscia contenga i seguenti caratteri:
A 1 2 B e la macchina sia posizionata sul carattere A mentre si trova nello stato S1; la tabella che descrive il comportamento sia la seguente:
Scatti Carattere
lettoStato
correnteCarattere
scrittoStato
successivoMovimento 1 A S1 A S1 destra 2 1 S1 1 S1 destra 3 2 S1 1 S1 destra 4 B S1 Z S2 sinistra 5 1 S2 1 S2 sinistra 6 1 S2 1 S2 sinistra 7 A S2 A S2 fermo In questo caso, dopo il primo scatto (descritto dalla prima riga della tabella), il carattere e lo stato rimangono invariati e il prossimo carattere letto sarà quello di destra.
Al quarto scatto, leggendo B nello stato S1, il carattere letto viene sostituito da Z, lo stato diventa S2 e il prossimo carattere letto sarà quello di sinistra.
Dopo il settimo scatto la macchina si ferma nello stato S2 sulla prima casella e il contenuto della striscia è il seguente:
A 1 1 Z La macchina si ferma quando non cambiano né lo stato né il contenuto della cella e non c’è movimento.
Si supponga che il contenuto iniziale del nastro sia il seguente, che il dispositivo di lettura sia posizionato sul carattere A mentre si trova nello stato S1:
A 2 1 B e che la tabella che descrive il comportamento della macchina sia la seguente:
Scatti Carattere
lettoStato
correnteCarattere
scrittoStato
successivoMovimento 1 A S1 A S2 fermo 2 A S2 A S2 destra 5 A S3 B S1 destra 6 0 S1 0 S3 destra 7 1 S3 1 S2 sinistra 8 0 S2 0 S3 destra 9 1 S3 3 S1 sinistra 10 0 S1 0 S1 fermo Trovare lo stato S in cui si trova la macchina al termine dei suoi movimenti, e i contenuti C1, C2, C3 e C4 delle 4 caselle del nastro, elencati da sinistra a destra.