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
10111000101
00011001010
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

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