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?

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.

• 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? – M Smith Mar 9 '18 at 18:43
• @MSmith I thought I wrote that. The text doesn't say that it would be the same number. – SK19 Mar 9 '18 at 18:49
• The text says that both would be $n$. Assuming $n$ is a constant, that means that they would have the same number of states? – M Smith Mar 9 '18 at 18:58
• @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. – SK19 Mar 9 '18 at 20:27
• @MSmith And so have I ;) – SK19 Mar 9 '18 at 22:22