Edizione VI – Problema 1

Si vuole realizzare l’odometro di Erone da Alessandria, ovvero un contatore a cifre decimali a lunghezza fissa che incrementa di uno il numero N.
Quando raggiunge il valore massimo 99…9, ritorna a 00…0.

Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro l’incremento di N con l’odometro.

Esempi

1. Si posiziona sull’ultima cifra a destra
2. Se la cifra è compresa fra 0 e 8, viene incrementata e l’esecuzione termina.
3. Se la cifra è 9 viene scritto 0 e si passa a incrementare la cifra a sinistra (riporto).

Tabella delle transizioni di stato

Quintuple #1

(0, 0, 0, 0, >)
(0, 1, 0, 1, >)
(0, 2, 0, 2, >)
(0, 3, 0, 3, >)
(0, 4, 0, 4, >)
(0, 5, 0, 5, >)
(0, 6, 0, 6, >)
(0, 7, 0, 7, >)
(0, 8, 0, 8, >)
(0, 9, 0, 9, >)
(0, -, 1, -, <)
(1, 0, H, 1, <)
(1, 1, H, 2, <)
(1, 2, H, 3, <)
(1, 3, H, 4, <)
(1, 4, H, 5, <)
(1, 5, H, 6, <)
(1 ,6, H, 7, <)
(1, 7, H, 8, <)
(1, 8, H, 9, <)
(1, 9, 1, 0, <)

Quintuple #2

(0, [0..9], 0, [0..9], >)
(0, -, 1, -, <)
(1, [0..8], H, [1..9], <)
(1, 9, 1, 0, <)