Question about proving that Rado's function is non-computable 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) &gt; 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:


The $x$ state Turing machine $M$ prints $x$ 1's to the tape.
Next, $F(x)$ 1's are written to the tape by the $n$ state Turing machine $M_F$
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:


Start with blank tape: $\Delta$
Write $x$ $1$'s on tape: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta$$
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$$
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.