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?

thanks in advance!

  • 1
    $\begingroup$ Only finite many outputs are possible because for a given number of states we only have finite many turing machines. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ The tape we write on is empty, so we don't have to check what the head is looking at, right? Or do we read n from the same tape? Sorry if this is a dumb question, I do not have lots of experience with turing machines. $\endgroup$ – John Doe Jan 9 '19 at 17:21
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 9 '19 at 17:24
  • $\begingroup$ I think I get it. So eg for decimal 5 I could just use one state for each of the three digits 101 of binary 5? $\endgroup$ – John Doe Jan 9 '19 at 17:59
  • $\begingroup$ Yes, that is right. $\endgroup$ – Ross Millikan Jan 9 '19 at 18:03
  • $\begingroup$ thanks, you helped me out a lot :) $\endgroup$ – John Doe Jan 9 '19 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.