Edizione II – Problema 1

Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo k, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se k è un numero pari, la sola sequenza NO altrimenti.

Esempi

Diagramma di stato #1

• Per ogni cifra pari letta rimane/va nello stato 0
• Per ogni cifra dispari letta rimane/va nello stato D
• Se finisce l’input in 0 scrive SI
• Se finisce l’input in D scrive NO

Tabella delle transizioni di stato #1

Quintuple #1

(0, 02468, 0, -, >)
(0, 13579, D, -, >)
(0, -, SI, S, >)
(SI, -, H, I, -)
(D, 02468, 0, -, >)
(D, 13579, D, -, >)
(D, -, NO, N, >)
(NO, -, H, O, -)

Diagramma di stato #2

1. Raggiunge la prima cifra a destra
2. Se è 0/2/4/6/8 cancella tutto a sinistra e scrive SI
3. Se è 1/3/5/7/9 cancella tutto a sinistra e scrive NO

Quintuple #2

(0, 0..9, 0, 0..9, >)
(0, -, PD, -, <)
(PD, 02468, P, -, <)
(PD, 13579, D,  -, <)
(P, 0..9, P, -, <)
(D, 0..9, D, -, <)
(P, -, S, I, <)
(S, -, H, S, -)
(D, -, N, O, <)
(N, -, H, N, -)