# Minimum Number of states turing machine

I think my question is rather simple, but I can't wrap my head around it. In "The (new) Turing Omnibus" on page 266, the author writes:

[...], and let A be a [Turing-]machine that converts a blank tape to one with the number n written in binary on it.

and then, further down:

[...], ceil(log(n)) states are required by A [...]

I looked over the Internet, but I found no answer. Why this number of states? Wouldn't it be sufficient to have one state, which writes a 0 when given a 0, and 1 when given 1 and in any case shift left?

• Only finite many outputs are possible because for a given number of states we only have finite many turing machines. – Peter Jan 9 '19 at 17:04

Your proposed machine will not halt. If by $$0$$ you mean a blank cell, given a blank tape it will not write anything and forever shift left. That neither writes $$n$$ nor terminates. If you allow writing either $$0$$ or $$1$$ and you start it with one of those under the head it will just write an infinite sequence of that same digit without halting.
For this purpose it is easy to describe a Turing machine that does this. We will start writing from the right. We start at state $$0$$, write the rightmost bit of $$n$$, move the tape left, and go to state $$1$$. Each state writes the proper bit and moves the tape left. The final state halts instead of moving the tape. This machine does not need to consider what is on the tape. It justifies the claim that we can write $$n$$ with the claimed number of states, but does not show that there is not a smarter machine that can do it in less states.
Most Turing machines that I have seen actually work in base $$1$$, not base $$2$$. They represent $$n$$ by a series of $$n+1$$ marks, using a blank as the separator between numbers. That is not how this problem is defined.
• Some Turing machines move the head both directions, so even starting with a blank tape it may be able to find a $1$ later in the operation. – Ross Millikan Jan 9 '19 at 17:24