Raddoppi
Si scriva un programma per macchina di Turing che, ricevuto in ingresso un numero intero, lasci sul nastro il doppio del numero indicato.
| Nastro iniziale | Nastro finale | |
|---|---|---|
| 1° | 31 | 62 |
| 2° | 1 | 2 |
| 3° | 1651 | 3302 |
| 4° | 9 | 18 |
Diagramma di stato
- Si porta sulla prima cifra a destra
- Lo stato 2 raddoppia senza riporto
- Lo stato R raddoppia con riporto, se le cifre finiscono scrive 1
Tabella delle transizioni di stato
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | – | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0,0,> | | 0,2,> | 0,3,> | 0,4,> | 0,5,> | 0,6,> | 0,7,> | | | 2,-,< |
| 2 | 2,0,< | | 2,4,< | 2,6,< | 2,8,< | R,0,< | R,2,< | R,4,< | | | H,-,> |
| R | 2,1,< | 2,3,< | 2,5,< | 2,7,< | 2,9,< | R,1,< | R,3,< | R,5,< | R,7,< | R,9,< | H,1,- |
| H | — | — | — | — | — | — | — | — | — | — | — |
Quintuple
(0, [0..9], 0, [0..9], >)
(0, -, 2, -, <)
(2, 01234, 2, 02468, <)
(2, 56789, R, 02468, <)
(2, - , H, -, >)
(R, 01234, 2, 13579, <)
(R, 56789, R, 13579, <)
(R, - , H, 1, -)
- Va destra
- Si posiziona sulla cifra a destra
- Il doppio, senza riporto
- Il doppio, c’è un riporto
- Finito, senza riporto
- Il doppio, con riporto, senza riporto
- Il doppio, con riporto, c’è riporto
- Finito, con riporto