Indichiamo con AnBm una sequenza del tipo A…AB…B.
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo AnBm, con n>0 e m>0, termina la sua esecuzione lasciando sul nastro
- una sola A se n>m
- una sola B se m>n
- una sola C se n=m.
Esempi
| NASTRO INIZIALE | NASTRO FINALE |
|---|---|
| AAAABB | A |
| AAABBBBB | B |
| AAABBB | C |
Diagramma di stato
- Cancella una A a sinistra, va a destra e cancella una B, ritorna a sinistra
- Ripete finché è possibile…
- Se finiscono le A cancella le B rimaste e scrive B
- Se finiscono le B cancella le A rimaste e scrive A
- Se finiscono sia le A che le B allora scrive C
Quintuple
(0,A,A,-,>) | Ha trovato una A, va a destra |
(0,B,BB,-,>) | Ha trovato una B, cancella tutto |
(0,-,H,C,>) | Scrive C |
(A,AB,A,AB,>) | Va a destra |
(A,-,R,-,<) | In fondo… |
(R,A,A,-,<) | Cancella tutte le A |
(R,-,H,A,>) | Scrive A |
(B,AB,B,AB,<) | Va a sinistra |
(B,-,0,-,>) | In fondo… |
(BB,B,BB,-,>) | Cancella tutte le B |
(B,-,H,B,>) | Scrive B |