The Halting Problem is whether or not a given Turing machine halts on a given input. This is the classic example of an undecidable problem, one that no Turing machine can accurately and completely solve.

The conventional proof, going all the way back to Turing, involves steps like "feed machine X its own description" which are sort of weird and hard to intuit. Why would we do that? Does the proof still apply if we forbid that somehow? Is this weird self-referential crap really necessary, or is it obscuring what's actually going on?

Here are two proofs that don't require us to feed any Turing machines their own descriptions.

Proof Based on Halting Signatures

The first argument shows how to avoid explicitly naming a particular function as part of the proof. The original version of this proof can be bound here.

Suppose we enumerate the halting state for every machine i with input j. We can think of this as a table T[i,j] containing 1 when the machine halts, and 0 when it does not. Each row is a "halting signature" for the machine i.

(If there is a convincing philosophical argument that this is “unknowable” even in theory, we can immediately conclude that the halting problem is undecidable as well— the Turing machine is certainly not any more capable than humans are, given enough time and scratch paper.)

The impossible halting signature D

The diagonal argument shows the function D(i) = 1 - T[i,i] does not appear as any row (or column!) of this table. D(i) differs from T[m,i] for every machine m, and D(i) differs from T[i,p] for every input p. Therefore, D(i)cannot describe the halting behavior of any Turing machine. It is by no means unique in this respect; but the diagonal argument is an easy one.

Now we’ll launch into our proof by contradiction, constructing a Turing machine with halting signature D.

Constructing a Turing Machine

Suppose a Turing machine to solve the halting problem exists, call it H, which uses the same enumeration of programs and inputs as our table. Then H has a finite set of terminating states. Using the definition of H, we can construct a new Turing machine K.

• Introduce a prologue which takes the input i and produces the input (i,i) consisting of two copies.
• Copy the states of H that operate on the input (i,j=i).
• For each halting state in H, add additional states which check whether the output would be 0 or 1. (They can be read back off the tape, if necessary.) If it is 1, loop forever. If it is 0, halt.

K is a perfectly good Turing machine. The construction does not require us to use a description of H or K as an input to anything. We build K using the provided H in an explicit and non-recursive way, so if H exists, then K exists too. We didn’t require knowing K’s index or H’s index in our table T[i,j].

Contradiction

K’s halting behavior on input i is described by the function D(i). But we agreed that D(i) doesn’t correspond to the halting behavior of any Turing machine m. Therefore, K cannot be a Turing machine, and so H cannot be either.

Proof Based on Elegant Programs

Gregory Chaitin didn’t like Turing’s proof either. He came up with the second argument presented here, based on what he calls Borel’s paradox instead. (See pp 125–127 of “Meta Math! The Search for Omega".) Note that he is not referring, as far as I can tell, to the Borel-Kolmogorov paradox which is its own mind-bending mess about conditional probabilities of measure zero.

Define an “elegant” program for U as a shortest program that produces a given output U. Now, using a formal axiomatic system, we will be able to prove that some programs are elegant.

But, a formal axiomatic system can be implemented by a computer program that enumerates its theorems (in some order.) Pick the smallest such program for your formal axiomatic system. (As a side node, this tells you how much information your system contains!)

A Paradoxial Program

Define program P_n, for an integer parametern, as:

1. Enumerate all theorems of the FAS, using the smallest-possible program that does so.
2. When you find a theorem proving that a program Q is elegant for some U and has length greater than n, run Q and use its output U as P_n’s output.

Now, P_n has a length. The length does not increase linearly with n, because we can represent lengths very compactly in binary notation (or better). So for some n, |P_n| < n.

Note: Chaitin asks for |P_n| = n, but I scrupulously avoided even this indirect hint of P referring to itself, even though there are presumably lots of other programs of the same length. n is just some sufficiently large number— probably no more than a few billion, because we have automatic provers less than that size today!

What does P_n output?

Can P_n emit any output U? No, because P_n would be shorter than Q. We have set things up so that |Q| > n > |P_n|, and the output of the two programs is identical. So in fact Q cannot be elegant for U, because P_n is shorter and would produce the same output.

That means our formal axiomatic system must not be able to prove the elegance of any program longer than n. P_n will never be able to find its |Q| > n, once n is large enough.

Back to Halting

If we could solve the Halting problem, we could use it to find all elegant programs too:

1. Enumerate all programs Q in order of increasing length
2. Test each Q for halting
3. Run the ones that halt; if we haven’t seen that output U before, the program Q is elegant for U.

Because we can’t prove elegance for unboundedly large n, we can’t prove halting on unboundedly large programs either.

Conclusion

Both these proofs try to illustrate something that the self-referential proof does not.

The first proof closely parallels Cantor's proof of the uncountability of real numbers. We don't need to feed a function its own description--- the property we want isn't that special that it only crops up in self-reference. There are uncountably many D(i)'s we could construct using a Halting oracle, and all of them are impossible. The diagonal one is just a particularly clear and concise example.

The second proof argues that information theory is truly fundamental--- Halting isn't a particularly special problem. Given any finitely described system of reasoning, there are severe limits on what we can expect to prove. We can't get more bits of information out than we put in. And that means we can't expect to get information about infinitely many Turing machines from a finite program.

There's nothing wrong with self-reference, and geeks will happily go on writing programs that print themselves. But different proofs can illustrate different aspects of the truth.

Sources and Further Reading

Originally answered at: https://www.quora.com/What-is-a-proof-of-the-undecidability-of-the-halting-problem-that-does-not-rely-on-any-function-directly-or-indirectly-calling-itself-or-referencing-itself

babou. Answer to Is there a more intuitive proof of the halting problem's undecidability than diagonalization?, CS StackExchange, May 2015.

Chaitin, Gregory. "Meta Math!: The Quest for Omega". Vintage Books, 2006. An online preprint can be found here: https://arxiv.org/abs/math/0404335

Lipton, R.J., and Regan, K.W. A Proof Of The Halting Theorem, Gödel’s Lost Letter and P=NP (blog), September 19, 2016

Noll, Landon Curt and Bassel, Larry. Worst Abuse of the Rules, Obfuscated C Contest, 1994. The all-time winner for smallest self-printing program.

Wikipedia, Halting Problem. The "Proof concept" section shows a typical self-reference based approach.