Macchina di Turing che ricerca un numero su di un nastro illimitato

Stato iniziale : la testina di lettura e scrittura può essere posizionata su di una cella qualsiasi del nastro.

Stato finale : la testina di lettura e scrittura è posizionata sulla cifra meno significativa del n° .

Descrizione algoritmo : dato che il nastro è illimitato, la ricerca del n° non può avvenire solo in un verso in quanto se questo è errato, non si raggiunge mai il n° stesso. La ricerca avviene alternando i 2 passi :

a) ricerca del n° a sx con riscrittura delle X presenti e scrittura di una X al posto del 1° blank che segue le X.

b) ricerca del n° a dx con riscrittura delle X presenti e scrittura di una X al posto del 1° blank che segue le X.

Quando il n° viene individuato, vengono cancellate tutte le X inserite sul nastro e ci si posiziona sulla cifra meno significativa del n°.

Matrice funzionale

	b	X	" a Î A	descrizione
qo	X q1 sx	X q0 dx	a q2 sx	inserimento di una X a dx al posto del 1° blank
q1	X q0 dx	X q1 sx	a q3 dx	inserimento di una X a sx al posto del 1° blank
q2	b q2 dx	b q2 sx	a q4 dx	cancella le X a sx e si posiziona sulla cifra più significativa
q3	b q3 sx	b q3 dx	a q4 dx	cancella le X a dx e si posiziona sul blank successivo alla cifra meno significativa
q4	b q5 sx		a q4 dx	si posiziona sulla cifra meno significativa
q5

Esempio di computazione della stringa

b bbbbbbb