Edizione III – Problema 1

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

Quintuple #1

(0,A,0,A,<)	Si posiziona a sinistra
(0,1,1,-,>)	Per ogni cifra da 1 a 9…
(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,>)	Salta le A
(1,-,0,A,<)	Scrive A e ricomincia

Algoritmo #2

Riassumere?

(0,A,0,A,<)	Si posiziona a sinistra
(0,123456789,1,-012345678,>)	Per ogni cifra da 1 a 9…
(0,-,H,-,>)
(1,A,1,A,>)	Salta le A
(1,-,0,A,<)	Scrive A e ricomincia