Monthly Archives: novembre 2014

Edizione I – Problema 2

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro una sola T se la sequenza iniziale contiene almeno una B, una sola F altrimenti.

Esempi

NASTRO INIZIALE NASTRO FINALE
BABBAB T
B T
AAA F

0102Algoritmo

  • Lo stato 0 indica che non c’è alcuna B e se l’input finisce scrive F
  • Lo stato 1 indica che c’è almeno una B e se l’input finisce scrive T

Codice 1

(0,A,0,-,>)
(0,B,1,-,>)
(0,-,H,F,>)
(1,A,1,-,>)
(1,B,1,-,>)
(1,-,H,T,>)
Finché A rimani in 0
Se B vai in 1
Se l'input è finito scrivi F
Finché A oppure B rimani in 1
'
Se l'input è finito scrivi T

Codice 2

(0,A,0,-,>)
(0,B,1,-,>)
(0,-,H,F,>)
(1,[AB],1,-,>)
(1,-,H,T,>)
Finché A rimani in 0
Se B vai in 1
Se l'input è finito scrivi F
Finché A oppure B rimani in 1
Se l'input è finito scrivi T