Machine of Turing that searches a number on a limitless tape

State begins them: the testina of reading and writing can be posizionata on one cell whichever of the tape.

State finale : the testina of reading and writing is posizionata on the less meaningful figure of the n°.

Description algorithm: since the tape is limitless, the search of the n° pu² not to only happen in a back in how much if this is wrong, never does not catch up the n° same. The search happens alternating the 2 steps:

a) search of the n° to sx with riscrittura of X present and writing of one X in place of 1° blank the that follows the X.

b) search of the n° to dx with riscrittura of X present and writing of one X in place of 1° blank the that follows the X.

When the n° it comes characterized, comes cancelled all the X inserted on the tape and us posiziona on the less meaningful figure of the n°.

Matrix works them

	b	X	" to ? To	description
qo	X q1 sx	X q0 dx	to q2 sx	insertion of one X to dx in place of the 1° blank
q1	X q0 dx	X q1 sx	to q3 dx	insertion of one X to sx in place of the 1° blank
q2	b q2 dx	b q2 sx	to q4 dx	it cancels the X to sx and posiziona on the more meaningful figure
q3	b q3 sx	b q3 dx	to q4 dx	it cancels the X to dx and posiziona on the blank successive to the less meaningful figure
q4	b q5 sx		to q4 dx	posiziona on the less meaningful figure
q5

Example of computazione of tightens

b bbbbbbb