So,
here is a quiz for you
to get your feet wet
in designing Turing machines.
Suppose I have an alphabet
which is just zero, one,
and a special symbol,
a dot,
which we can think of as a decimal point,
or I guess whatever you call you call
decimal points in binary,
a binary point.
Suppose the machine starts there,
I would like you to write a little machine
which computes
the successor function.
I want it to start at that binary point
and then move to the left,
reading those zeroes and ones,
doing something to them,
and then returning to its starting point,
and I want it to update
whatever binary integer is written there
to the left of the binary point,
from x to x+1, add one to it.
And, maybe this is too big of a hint,
but I suggest that you give it
three states, called carry,
return, and halt.
All right. So figure out what the
transitions for this little
Turing machine should be.