0
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ But would showing that $\Sigma (n) > f(n)$ not just prove that $\Sigma (n)$ is the fastest growing computable function? $\endgroup$ – M Smith Nov 29 '17 at 23:03
  • $\begingroup$ @JChapman No, because - if $\Sigma$ were computable - we would have to have $\Sigma(n)>\Sigma(n)$ (that is, we could take $\Sigma=f$). Alternatively, if you're not happy with that for some reason think about $f(x)=\Sigma(x)+1$ - this $f$ is computable if $\Sigma$ is, so if $\Sigma$ is computable we have $\Sigma(x)>f(x)$ ... $\endgroup$ – Noah Schweber Nov 29 '17 at 23:09
  • $\begingroup$ @JChapman I've edited my answer to be more explicit. $\endgroup$ – Noah Schweber Nov 29 '17 at 23:17
0
$\begingroup$

$\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 ?

$\endgroup$

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.