Indichiamo con s e t due generiche sequenze formate da A e B.
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo sCtC, termina la sua esecuzione lasciando sul nastro la sequenza SI se S e T sono uguali, la sequenza NO altrimenti.
Esempi
| Nastro iniziale | Nastro finale | |
|---|---|---|
| 1° | ABACABAC | SI |
| 2° | BBBCBBBC | SI |
| 3° | BABACBBAC | NO |
| 4° | BBBCABC | NO |
Diagramma di stato
- Elimina la prima lettera a sinistra, si sposta a destra dopo la C in cerca della stessa lettera che diventa una C
- Torna a sinistra e ripete
- Se sul nastro rimangono solo C scrive SI
- Nei casi di errore cancella tutto e scrive NO
Quintuple
(0,A,A,-,>) | |
(0,B,B,-,>) | |
(0,C,C,-,>) | |
(A,AB,A,AB,>) | |
(A,C,AA,C,>) | |
(AA,C,AA,C,>) | |
(AA,A,S,C,<) | |
(AA,B-,X1,B-,<) | |
(B,AB,B,AB,>) | |
(B,C,BB,C,>) | |
(BB,C,BB,C,>) | |
(BB,B,S,C,<) | |
(BB,A-,X1,A-,<) | |
(S,ABC,S,ABC,<) | |
(S,-,0,-,>) | |
(C,C,C,-,>) | |
(C,-,SI,S,>) | |
(C,AB,X2,-,>) | |
(SI,-,H,I,>) | |
(X1,ABC,X1,ABC,<) | |
(X1,-,X2,-,>) | |
(X2,ABC,X2,-,>) | |
(X2,-,NO,N,>) | |
(NO,-,H,O,>) |