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 sequenza che si ottiene da quella iniziale rimpiazzando due o più A consecutive con una sola A e due o più B consecutive con una sola B.
Esempi
| Nastro iniziale | Nastro finale | |
|---|---|---|
| 1° | ABAABBBA | ABABA |
| 2° | BBAABBBAB | ABAB |
| 3° | AAA | A |
| 4° | BB | B |
Diagramma di stato
- Riconosce una sequenza di A (B) terminata da una B (A)
- Va a destra e scrive X (Y)
- Ritorna a sinistra e ricomincia
- Quando le A e le B sono finite trasforma le X in A e le Y in B.
Quintuple
(0,A,A,-,>) | Inizia una sequenza di A |
(A,A,A,-,>) | |
(A,BXY,X,BXY,>) | La sequenza di A è finita |
(X,ABXY,X,ABXY,>) | Va a destra per scrivere X |
(X,-,S,X,<) | Scrive X |
(0,B,B,-,>) | Inizia una sequenza di B |
(B,B,B,-,>) | |
(B,AXY,Y,AXY,>) | La sequenza di B è finita |
(Y,ABXY,Y,ABXY,>) | Va a destra per scrivere Y |
(Y,-,S,Y,<) | Scrive Y |
(S,ABXY,S,ABXY,<) | Torna a sinistra |
(S,-,0,-,>) | Ricomincia |
(0,XY,0,AB,>) | Trasforma le X e le Y in A e B |