Machine de Turing qui recherche un nombre sur bande sans limites

L'état les commence : le testina de la lecture et de l'écriture peut être posizionata sur une cellule laquelle de la bande.

Finale d'état : le testina de la lecture et de l'écriture est posizionata sur la figure moins signicative du n°.

Algorithme de description : puisque la bande est sans limites, la recherche du pu² de n° à ne pas se produire seulement dans un dos dans combien si c'est erroné, jamais ne rattrape le n° mêmes. La recherche se produit alternant les 2 étapes :

a) recherche du n° au sx avec le riscrittura du présent de X et l'écriture d'un X au lieu du blanc 1° qui suit le X.

b) recherche du n° au dx avec le riscrittura du présent de X et l'écriture d'un X au lieu du blanc 1° qui suit le X.

Quand le n° il vient caractérisé, vient décommandé tout le X inséré sur la bande et nous posiziona sur la figure moins signicative du n°.

Matrix les fonctionne

	b	X	" à ? À	description
qo	Sx X q1	Dx X q0	au sx q2	insertion d'un X au dx au lieu du blanc 1°
q1	Dx X q0	Sx X q1	au dx q3	insertion d'un X au sx au lieu du blanc 1°
q2	dx de b q2	sx de b q2	au dx q4	il décommande le X au sx et au posiziona sur la figure plus signicative
q3	sx de b q3	dx de b q3	au dx q4	il décommande le X au dx et au posiziona sur le blanc successif à la figure moins signicative
q4	sx de b q5		au dx q4	posiziona sur la figure moins signicative
q5

L'exemple du computazione de serre

bbbbbbb de b