Programmare con la Macchina di Turing

Date due sequenze di 1 separate da *, scrive 1 se sono uguali, 0 altrimenti

Esempi

Algoritmo

• Elimina un 1 a sinistra e un 1 a destra finché non rimane soltanto *
• Nei casi di errore cancella tutto e scrive 0

Tabella

Delle transizione di stato

Codice

(0,1,D,-,>)
(0,*,F,-,>)
(F,-,H,1,>)
(F,1,FF,-,>)
(FF,1,FF,-,>)
(FF,-,H,0,>)

(D,1*,D,1*,>)
(D,-,DD,-,<)
(DD,1,S,-,<)
(DD,*,SS,-,<)
(SS,1,SS,-,<)
(SS,-,H,0,<)

(S,1*,S,1*,<)
(S,-,0,-,>)

Elimina un 1 a sinistra
'
'
'
'
'

Vai a destra
'
'
'
'
'

Elimina un 1 a destra
Vai a sinistra

Se sul nastro trova CIAO scrive 0, se sul nastro trova BYE scrive 1.

Esempi

Algoritmo

Ci sono due percorsi distinti di lettura controllata del nastro

• Input iniziale è CIAO allora scrive 0
• input iniziale è BYE allora scrive 1

Codice

(0,C,1,-,>)
(1,I,2,-,>)
(2,A,3,-,>)
(3,O,H,0,>)
(0,B,4,-,>)
(4,Y,5,-,>)
(5,E,H,1,>)

Inizia con C
...
...
Scrive 0
Inizia con B
...
Scrive 1

Se sul nastro trova 0 scrive CIAO, se trova 1 scrive BYE.

Esempi

Algoritmo

Ci sono due percorsi distinti di scrittura su nastro

• Input iniziale è 0 allora scrive CIAO
• input iniziale è 1 allora scrive BYE

Codice

(0,0,1,C,>)
(1,-,2,I,>)
(2,-,3,A,>)
(3,-,H,O,>)
(0,1,4,B,>)
(4,-,5,Y,>)
(5,-,H,E,>)

Inizia con C
...
...
...
Inizia con B
...
...

Scrivere CIAO con il nastro inizialmente vuoto

Esempi

Algoritmo

Codice 1

(0,-,1,C,>)
(1,-,2,I,>)
(2,-,3,A,>)
(3,-,H,O,>)

Scrive C
... I
... A
... O

Tratto dal sito ufficiale

Consideriamo una macchina che modifica una sequenza di A rimpiazzando ogni A in posizione dispari con una B.
La prima A ha posizione pari uguale a 0.

Esempi

Algoritmo

• Lo stato 0 è pari, A rimane
• Lo stato 1 è dispari, A diventa B

Codice

(0,A,1,A,>)
(1,A,0,B,>)

A dispari
A pari diventa B

Aggiunge, a destra, il bit di parità a una sequenza binaria

Esempi

Algoritmo

1. I bit 0 mantengono lo stato Pari oppure Dispari
2. I bit 1 cambiano lo stato da Dispari in Pari, oppure da Pari in Dispari
3. Se termina in Pari scrive 0
4. Se termina in Dispari scrive 1

Codice

(0,0,P,0,>)
(0,1,D,1,>)
(P,0,P,0,>)
(P,1,D,1,>)
(P,-,H,0,>)
(D,0,D,0,>)
(D,1,P,1,>)
(D,-,H,1,>)

0
1
0
1, cambia...
Scrive 0
0
1, cambia...
Scrive 1

Se il numero di 1, in una sequenza unaria, è pari/dispari scrive EVEN/ODD.

Esempi

Algoritmo

• All’inizio il numero di 1 è pari (0…)
• Per ogni 1 cambia stato: 0 -> 1 -> 0 -> … (Pari -> Dispari -> Pari -> …)
• Se il nastro è vuoto scrive EVEN…

Codice

(0,1,1,-,>)
(0,-,2,E,>)
(2,-,3,V,>)
(3,-,4,E,>)
(4,-,H,N,>)
(1,1,0,-,>)
(1,-,5,O,>)
(5,-,6,D,>)
(6,-,H,D,>)

-> Dispari
Inizia a scrivere EVEN
...
...
...
-> Pari
Inizia a scrivere ODD
...
...

Incrementare di 1 per sempre…

Esempi

Algoritmo

1. Si sposta a destra, sull’ultima cifra
2. Se incontra una cifra diversa da 9 scrive la cifra successiva e ritorna a destra
3. Se incontra un 9 scrive 0 col riporto di 1… e continua a sinistra

Codice

(0,0123456789,0,0123456789,>)
(0,-,S,-,<)
(S,012345678-,0,1234567891,>)
(S,9,S,0,<)

Vai a destra
Comincia
Scrivi il successivo, ritorna a destra
Scrivi 0 col riporto di 1

Tratto dal sito ufficiale

Scrivere un programma per macchina di Turing che, ricevuta sul nastro una stringa sull’alfabeto a-z, lasci il nastro vuoto alla fine della computazione se e solo se la stringa originale era palindroma.

Si dicono palindrome le stringhe che si leggono identicamente da sinistra a destra o da destra verso sinistra.

Esempi

NASTRO INIZIALE	NASTRO FINALE
ailatiditalia
ailatidtalia	d
satorras	torr

Algoritmo

1. Posizionati sul primo carattere a sinistra della stringa, lo cancelliamo, memorizziamo nel nome dello stato il carattere letto, passando nello stato lettoa (se abbiamo letto una a) fino a lettoz (se abbiamo letto una z).
2. Quindi scorriamo tutta la stringa, mantenendo memoria nello stato di quale carattere avevamo letto, e riscrivendo sempre il carattere letto.
3. Arrivati in fondo alla stringa, ci spostiamo di una cella a destra (sempre mantenendo il carattere letto originalmente nello stato), e verifichiamo di trovare all’estremità sinistra della stringa lo stesso carattere che avevamo letto a destra.
4. In caso positivo, si cancella il carattere e si ritorna in cima alla stringa, ripetendo poi l’algoritmo (fino a consumare tutta la stringa).
5. In caso negativo si interrompe il calcolo, lasciando sul nastro la parte di stringa non palindroma.

Codice 1

(0,[a..z],letto[a..z],-,>)
(letto[a..z],{a..z},letto[a..z],{a..z},>)
(letto[a..z],-,destra[a..z],-,<)
(destra[a..z],[a..z],ritorno,-,<)
(ritorno,[a..z],ritorno,[a..z],<) (ritorno,-,0,-,>)

Data un numero naturale incrementare di 1 il suo valore

Esempi

Algoritmo

1. Si sposta a destra
2. Se la prima cifra a destra è diversa da 9 scrive la cifra successiva e ha finito
3. Se la prima cifra a destra è 9 scrive 0 col riporto di 1… e continua a sinistra

Codice

(0,0123456789,0,0123456789,>)
(0,-,S,-,<)
(S,012345678-,H,1234567891,>)
(S,9,S,0,<)

Vai a destra
Comincia...
Scrivi il successivo
Scrivi 0 col riporto di 1...