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
ABAABBBA
ABABA
BBAABBBAB
ABAB
AAA
A
BB
B
Algoritmo
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.