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 10⁰=1, quella successiva per 10¹=10, la terza da destra per 10²=100, e così via.
Nella numerazione con base 1 (unaria), ciascuna cifra (si usa il carattere 1 per convenzione) viene moltiplicata per 1ⁿ=1, qualunque sia n.

Per esempio, 12₁₀ = 111111111111₁.
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

Algoritmo #1

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

Tabella delle transizioni di stato

Quintuple #1

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

Quintuple #2

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

….