How do we show that Rado's function (for the Busy Beaver Algorithm) is non-computable?

Question

Rado's function $\Sigma (n)$ gives us the maximum number of 1's that a Turing machine may write on an initially blank tape. It is widely known that this function is non-computable by a Turing machine, but I am struggling to find a proof of this.

I have found one proof (here), but I'm not entirely sure that I understand the idea behind it, which states that

We can show that Rado's function $\Sigma (n)$ is non-computable by showing that if $f(n)$ is any computable function, then there exists $n_0$ such that $\Sigma (n) > f(n)$ for all $n \geq n_0$.

Why does showing this (which I assume is equivalent to showing that Rado's function grows more quickly than any other computable function) prove that Rado's function is non-computable?

Alternatively, how else might we prove the non-computability of Rado's function?

Answer 1

Rado's function grows more quickly than any computable function. This means Rado's function must be non-computable, since otherwise it would grow faster than itself.

---

In detail: we know that for all computable $f$, there is some $n$ such that $\Sigma(n)>f(n)$ (we actually know much more than this, but this is all I need here).

Now suppose $\Sigma$ were computable. Then we could take $f=\Sigma$ in the above (since the only restriction on $f$ is "$f$ is computable"), which would mean that there is some $n$ with $\Sigma(n)>f(n)=\Sigma(n)$. And this is clearly impossible.

---

I think the confusion creeps in when you write:

I assume is equivalent to showing that Rado's function grows more quickly than any other computable function

(emphasis mine). What we know is that $\Sigma$ grows faster than all computable functions, period, not just all computable functions except possibly $\Sigma$ itself. That's why we get a contradiction. Similarly, we know that the Ackermann function isn't primitive recursive since it grows faster than any primitive recursive function, and so on.

---

It's worth noting,by the way, that there is no fastest growing computable function: if $f$ is computable, so is e.g. $x\mapsto f(x)^2$.

Answer 2

$\Sigma(n)$ gives the maximum number of ones a Turing machine of length $n$ (with no arguments) may write before it halts.

If $\Sigma$ is computable then we can see it as a TM. Modify it to take the input as an integer encoded in base $2$, and to output the result $m$ by writing $m+1$ ones on the tape.

What do you get for $\Sigma(n)$ for $n > L+\log_2(n)$ where $L$ is the length of $\Sigma$'s source code ?