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

	Nastro iniziale	Nastro finale
1°	148	SI
2°	2763	NO

Algoritmo #1

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

Quintuple

(0,02468,0,-,>)	Per ogni cifra pari rimane nello stato 0
(0,13579,1,-,>)	Per ogni cifra dispari passa allo stato 1
(0,-,I,S,>)	Se finisce scrive SI
(I,-,H,I,-)
(1,02468,0,-,>)	Per ogni cifra pari passa allo stato 0
(1,13579,1,-,>)	Per ogni cifra dispari rimane nello stato 1
(1,-,O,N,>)	Se finisce scrive NO
(O,-,H,O,-)

Algoritmo #2

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