Una sequenza si dice palindroma se la sua lettura da sinistra verso destra è uguale alla sua lettura da destra verso sinistra.
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale è palindroma, la sola sequenza NO altrimenti.
Esempi
| Nastro iniziale | Nastro finale | |
|---|---|---|
| 1° | ABABA | SI |
| 2° | ABBA | SI |
| 3° | BABBA | NO |
A | SI |
Diagramma di stato
- Se la prima lettera è una A / B la elimina e va a cercarla a destra
- Se trova la lettera cercata la cancella e torna a sinistra per ricominciare
- Se non trova la lettera cercata elimina tutto e scrive NO
- Se finiscono le lettere scrive SI
Quintuple
(0,A,A,-,>) | Va a destra |
(A,AB,A,AB,>) | |
(A,-,AA,-,<) | Torna a sinistra |
(AA,[A-],S,-,<) | Ha trovato la A |
(AA,B,N,-,<) | Ha trovato una B |
(0,B,B,-,>) | Va a destra |
(B,AB,B,AB,>) | |
(B,-,BB,-,<) | Torna a sinistra |
(BB,A,N,-,<) | Ha trovato una A |
(BB,[B-],S,-,<) | Ha trovato la B |
(S,AB,S,AB,<) | Torna a sinistra |
(S,-,0,-,>) | Ricomincia |
(0,-,SI,S,>) | Scrive SI |
(SI,-,H,I,>) | … |
(N,[AB],N,-,<) | Cancella tutto |
(N,-,NO,N,>) | Scrive NO |
(NO,-,H,O,>) | … |