Vai al contenuto

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

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

Codice

CodiceCommenti
(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

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *