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 | |
|---|---|---|
| 1° | ailatiditalia | |
| 2° | ailatidtalia | d |
| 3° | satorras | torr |
Algoritmo
- 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).
- Quindi scorriamo tutta la stringa, mantenendo memoria nello stato di quale carattere avevamo letto, e riscrivendo sempre il carattere letto.
- 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.
- In caso positivo, si cancella il carattere e si ritorna in cima alla stringa, ripetendo poi l’algoritmo (fino a consumare tutta la stringa).
- In caso negativo si interrompe il calcolo, lasciando sul nastro la parte di stringa non palindroma.
Quintuple
(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,-,>) | … |