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?