Edizione X – Problema 1

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 INIZIALENASTRO FINALE
11+11111111
1111111+111111111
1+111
1+1
+ 

Algoritmo #1

  • 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,-,>)Legge 1, va a destra con D
(0,+,H,-,>)Legge +, termina
(D,1,D,1,>)Salta 1
(D,+,D,+,>)Salta +
(D,-,S,1,<)Scrive 1, va a sinistra con S
(S,1,S,1,<)Salta 1
(S,+,S,+,<)Salta +
(S,-,0,-,>)Ricomincia

Algoritmo #2

….

Lascia un commento