I am currently following the proof, found here, that Rado's function $$ \Sigma (n) = \max \{ \text{# of 1's that may be written to a tape by an n-state turing machine} \} $$ is non-computable. Within this proof, they say that there exists a Turing machine $M_F$, which we say has $n$-states, that writes $F(x)$ 1's to the tape.

However, they then go on to imply that there exists a Turing machine with $n$ states which writes $F(F(x))$ 1's to the tape! Surely, since $F(x) > x$ this should require more than $n$ states - since more states $\iff$ more 1's?

EDIT: For added clarity, I will now explain why I have interpreted this to mean that both $F(x)$ and $F(F(x))$ have $n$ states.

This proof first defines a Turning machine $M_F$ which has $n$ states and writes $F(x)$ 1's to the tape before halting. It then goes on to describe a (trivial) $x$-state Turing machine $M$ which "on input $\Lambda$" writes $x$ 1's to the machine's tape.

The proof then goes on to claim that $$ \Sigma (x + 2n) \geq x + F(x) + F(F(x)) $$ which means that there exists a $x + 2n$ state Turing machine which prints $x + F(x) + F(F(x))$ 1's to the machines tape.

I am assuming that these $x + F(x) + F(F(x))$ 1's are written as follows:

  1. The $x$ state Turing machine $M$ prints $x$ 1's to the tape.
  2. Next, $F(x)$ 1's are written to the tape by the $n$ state Turing machine $M_F$
  3. So far, we have written $x + F(x)$ 1's and $x+n$ states have been used to do so. Comparing this to the fact that $x + F(x) + F(F(x))$ 1's may be written using $x + 2n$ states, they are implying that there must exist a Turing machine which writes $F(F(x))$ 1's using $n$ states

I am probably interpreting this incorrectly, but I don't know why?


1 Answer 1


Thanks for the clarification! I really misinterpreted your question.

Okay, so we have the computable function $f$, the also computable function $F$ that is based on $f$, and the Turing machine $M_F$ with the following behavior:

when started with a tape with $y$ $1$'s, writes a block of $F(y)$ $1$'s to the right, separated by at least one blank

Note that I used $y$ instead of $x$. So when our TM starts with a tape like

$$\Delta\underbrace{1\ldots1}_{\times y}\Delta$$

the resulting tape will be

$$\Delta\underbrace{1\ldots1}_{\times y}\Delta\underbrace{1\ldots 1}_{\times F(y)}\Delta$$

and we say that $M_F$ uses $n$ states. Note that $n$ is independent of $y$. The number of states doesn't depend on the input of the TM.

Now the machine $M$ does the following:

  1. Start with blank tape: $\Delta$
  2. Write $x$ $1$'s on tape: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta$$
  3. Now mimic $M_F$ with these $x$ $1$'s as a start, i.e. $y=x$: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta\underbrace{1\ldots 1}_{\times F(x)}\Delta$$
  4. Now we mimic $M_F$ again, but this time with the $F(x)$ $1$'s as a start, i.e. $y=F(x)$: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta\underbrace{1\ldots 1}_{\times F(x)}\Delta\underbrace{1\ldots 1}_{\times F(F(x))}\Delta$$

So when we mimic $M_F$ a second time, we simply ignore the $x$ $1$'s at the leftmost of the tape and pretend they are not there. I think the text is implying that executing $M_F$ doesn't moves it too much left and that is understandable, since this behavior can be simulated by using a one-side bounded TM which is equivalent to our usual TM. So by mimicking $M_F$ two times, we would need about $2n$ states for that.

  • $\begingroup$ Yes, why would a Turing machine that writes $F(F(x))$ 1's to the tape have the same number of states as a Turing machine which writes only $F(x)$ 1's to the tape? $\endgroup$
    – M Smith
    Mar 9, 2018 at 18:43
  • $\begingroup$ @MSmith I thought I wrote that. The text doesn't say that it would be the same number. $\endgroup$
    – SK19
    Mar 9, 2018 at 18:49
  • $\begingroup$ The text says that both would be $n$. Assuming $n$ is a constant, that means that they would have the same number of states? $\endgroup$
    – M Smith
    Mar 9, 2018 at 18:58
  • $\begingroup$ @MSmith It doesn't. I've edited direct quotes into my answer. Please quote exactly which passage makes you think that both would be $n$. Or even better, edit it into your question. $\endgroup$
    – SK19
    Mar 9, 2018 at 20:27
  • $\begingroup$ @MSmith And so have I ;) $\endgroup$
    – SK19
    Mar 9, 2018 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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