Edizione IV – Problema 1

di

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 inizialeNastro finale
1°10111000101
2°00011001010
3°00000

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

01–
00, -, >1, -, >H, 0, -
11, -, >0, -, >H, 1, -
H———

Quintuple

(0, 0, 0, -, >)Legge 0, pari
(0, 1, 1, -, >)Legge 1, dispari
(0, -, H, 0, -)Finito, scrive 0
(1, 0, 1, -, >)Legge 0, dispari
(1, 1, 0, -, >)Legge 1, pari
(1, -, H, 1, -)Finito, scrive 1

Lascia un commento