Edizione X – Problema 1

  • by

Addizione unaria

Nei sistemi di numerazione posizionale, il valore denotato da un numero è ottenuto moltiplicando ogni cifra per la corrispondente potenza di una base.
Nel caso della notazione decimale, la base è 10; la cifra più a destra è moltiplicata per 100=1, quella successiva per 101=10, la terza da destra per 102=100, e così via.
Nella numerazione con base 1 (unaria), ciascuna cifra (si usa il carattere 1 per convenzione) viene moltiplicata per 1n=1, qualunque sia n.

Per esempio, 1210 = 1111111111111.
Si noti che lo 0 si esprime in unario con l’assenza completa del numero.

Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una addizione unaria (composta da due numeri unari separati da +), lasci sul nastro il risultato dell’addizione, sempre espresso in unario.

Esempi

NASTRO INIZIALE NASTRO FINALE
11+111 11111
1111111+1 11111111
1+1 11
1+ 1
+

Algoritmo

  • Sposta a destra ogni 1 a sinistra del segno +
  • Lo stato D va a destra per scrivere 1
  • Lo stato S va a sinistra per il prossimo 1
  • Se nello stato 0 trova + termina

Codice

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

(D,1,D,1,>)
(D,+,D,+,>)
(D,-,S,1,<)

(S,1,S,1,<)
(S,+,S,+,<)
(S,-,0,-,>)
Legge 1, va a destra con D
Legge +, termina
---
Salta 1
Salta +
Scrive 1
---
Salta 1
Salta +
Ricomincia

Lascia un commento

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