Is there a simple explanation which says why this is? I'm not looking for a proof or anything that contains too many technical terms.

I've come across the example of the Halting problem but I don't fully understand it.

The definitions I'm using of recursive and recursively enumerable are:

Recursive - a Turing machine will decide if $n \in S$ in a finite amount of time.

Recursively enumerable - a Turing machine will halt if $n \in S$ but won't if $n \notin S$.


My favorite way to start this is with the language paradox:

The smallest positive integer that cannot be uniquely described in fourteen words or less.

You didn't ask for a proof, but I'll show you how this paradox could be "formalized" if you had that every r.e. set was recursive.

Let $H=\{(e,f)\mid \text{ Turing machine $e$ halts with input $f$}\}$. It might take some work to see that $H$ is recursively enumerable. (You need to understand the existence of the Universal Turing Machine, really.)

If $H$ is recursive, we can formalize the above.

Namely, if $H$ is recursive, we can write a program that takes a pair $e,f$ and answers, in a finite amount of time, "Does $\phi_e(f)$ halt?" where $\phi_e$ is the function computed by the $e$th Turing machine.

This lets us write a machine $K$ that computes, for input $n$:

The smallest $k$ such that there exists $e,f\leq k$ with $\phi_e(f)=n$.

We do so by iterating over $k$ and check all $e,f$ with $\max(e,f)=k$ and asking:

Does $\phi_e(f)$ halt? And if it does, is its value $n$?

This program always halts - every positive integer is the output of some Turing machine with some input.

Finally, we use this program to write another program which takes $n$ as input, and returns $M(n)$:

The smallest $m$ which is not the output of some $\phi_e(f)$ where $e,f\leq 2^n$.

We do this by iterating over $m$, compute if $K(m)>2^n$, and return $m$ if it is.

So, if $T$ is recursive, we see that this function $M$ can be written as a Turing machine - that is, this function is $\phi_q$ for some $q$. And it halts for all inputs.

But then what is $\phi_q(q)$?

That last question is essentially the logical equivalent of the original paradox. If $m=\phi_q(q)$ then $m$ cannot be the output of $\phi_e(f)$ for any $e,f\leq 2^q$. But $q<2^q$. Contradiction.

The Universal Machine is the heart of it. The fact that all computation can be done by one finite machine means that we can make programs which answer questions about programs, and that is when paradox starts to arise in math.

Gödel's Incompleteness theorem is an example of this, by the way. The set of statements that are provably true is r.e. So is the set of statements that are provably false. If we had completeness - every statement either provably true or provably false - then the provably true statements would be recursive. Gödel showed, essentially, a self-referential paradox if that were the case.


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.