Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro il bit di parità. Tale bit è 1 se e solo se vi sono un numero dispari di 1 nella sequenza iniziale; altrimenti vale 0.
Esempi
NASTRO INIZIALE
NASTRO FINALE
1011100010
1
0001100101
0
0000
0
Algoritmo
Lo stato 0 rappresenta la parità, cambia in 1 se legge 1
Lo stato 1 rappresenta la non parità, cambia in 0 se legge 1
Se termina in 0 scrive 0, se termina in 1 scrive 1