Edizione IV – Problema 1

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

Diagramma di stato

• 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

Tabella delle transizioni di stato

Quintuple

(0, 0, 0, -, >)
(0, 1, 1, -, >)
(0, -, H, 0, -)
(1, 0, 1, -, >)
(1, 1, 0, -, >)
(1, -, H, 1, -)