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 #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
….