Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero n compreso tra 1 e 9, termina la sua esecuzione lasciando sul nastro A…A (n consecutive).
Esempi
| Nastro iniziale | Nastro finale | |
|---|---|---|
| 1° | 1 | A |
| 2° | 5 | AAAAA |
| 3° | 9 | AAAAAAAAA |
Diagramma di stato
- 0: Ritorna a sinistra, se trova una cifra la riscrive diminuita di 1 e passa allo stato 1
- 0: Se non trova la cifra (c’è –) ha finito
- 1: Salta le A finché non trova lo spazio, scrive A e ricomincia
Tabella delle transizioni di stato
| 1 | 2 | … | 9 | A | – | |
|---|---|---|---|---|---|---|
| 0 | 1, -, > | 1, 1, > | … | 1, 8, > | 0, A, < | H, -, > |
| 1 | — | — | — | — | 1, A, > | 0, A, < |
| H | — | — | — | — | — | — |
Quintuple #1
(0, A, 0, A, <)
(0, 1, 1, -, >)
(0, 2, 1, 1, >)
(0, 3, 1, 2, >)
(0, 4, 1, 3, >)
(0, 5, 1, 4, >)
(0, 6, 1, 5, >)
(0, 7, 1, 6, >)
(0, 8, 1, 7, >)
(0, 9, 1, 8, >)
(0, -, H, -, >)
(1, A, 1, A, >)
(1, -, 0, A, <)
- Si posiziona a sinistra
- Per ogni cifra da 1 a 9 scrive la precedente
- …
- …
- …
- …
- …
- …
- …
- …
- Se la cifra iniziale è stata azzerata finisce
- Salta le A
- Scrive A e ricomincia da sinistra
Quintuple #2
(0, A, 0, A, <)
(0, 123456789, 1, -12345678, >)
(0, -, H, -, >)
(1, A, 1, A, >)
(1, -, 0, A, <)