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 | A |
| 5 | AAAAA |
| 9 | AAAAAAAAA |
Algoritmo #1
- 0: Per ogni cifra da 1 a 9: la riscrive diminuita di 1 e passa allo stato S
- S: Salta le A finché non trova lo spazio e scrive A
- R: Ritorna a sinistra, saltando le A
| Codice #1 | |
|---|---|
| (0,1,S,-,>) | Per ogni cifra… |
| (0,2,S,1,>) | |
| (0,3,S,2,>) | |
| (0,4,S,3,>) | |
| (0,5,S,4,>) | |
| (0,6,S,5,>) | |
| (0,7,S,6,>) | |
| (0,8,S,7,>) | |
| (0,9,S,8,>) | |
| (S,A,S,A,>) | Salta le A |
| (S,-,R,A,<) | Scrive A |
| (R,A,R,A,<) | Salta le A |
| (R,1,0,1,-) | Se trova una cifra ritorna nello stato 0 |
| (R,2,0,2,-) | |
| (R,3,0,3,-) | |
| (R,4,0,4,-) | |
| (R,5,0,5,-) | |
| (R,6,0,6,-) | |
| (R,7,0,7,-) | |
| (R,8,0,8,-) |
Algoritmo #2
Semplificare?