More on the Diagonal
A different angle on the Halting Problem
Rudolf Carnap was a German-born philosopher who became a mainstay of the famous “Vienna Circle.” Kurt Gödel often visited their meetings, but was not a member. Perhaps, to quote Groucho Marx, Gödel did not want to belong to any club that would have him as a member. However, there was definitely a connection between him and Carnap. As attested by Warren Goldfarb, Carnap “introduced Gödel to logic, in the serious sense.” Further it was Carnap in 1934, not Gödel himself, who drew a strong connection between Georg Cantor’s diagonal argument and Gödel’s incompleteness theorems—see Goldfarb and these three essays by Haim Gaifman.
Today Ken and I want to talk about diagonalization and the Halting Problem.
We, Ken and I, have presented an uncountable number—okay a lot—of times the famous proof that the number-of-steps-to-halt function cannot be computed. This time I tried to give a slightly different proof than usual, and I thought I would share it with you. The proof is based on a simple non-closure theorem.
Carnap taught himself Esperanto as a teenager and actually employed it in travels. Here is the self-reference paradox at the heart of Gödel’s theorems in Esperanto:
Let’s take a look at the theorem.
An Abstract Version
Let be the natural numbers . Let be a set of functions so that for each number in ,
Then we are interested in properties of such sets of functions. Call the set closed under addition provided for any and there is an so that
Also define the set as non-trivial provided there is a function in the set so that for all . Then the following simple theorem is true:
Then is not in .
The function is sometimes called the diagonal function of .
The proof is quite simple. Suppose rather that is in the set . Then there is a so that
Let be a function in that is always non-zero. Now by closure under addition it follows that is in the set . Thus there is an such that is the function , and we have for all :
Set equal to . This yields , which is impossible over the natural numbers since .
Let be the functions that are polynomials in . They clearly satisfy the properties of the theorem. Hence their diagonal function cannot be in the set.
The Actual Halting Problem
Let be the set of functions that are computable by some Turing Machine . Then closure under addition and non-triviality are clear.
However, the set of Turing machines does not define an that we can apply the theorem to directly. The problem is that some machines on some inputs may not halt, and so the corresponding functions really are maps from to . If we try to apply the theorem we get that
for some . But this is not a contradiction.
Instead, given , let us define the modified function
The quick version is that if the Halting Problem is decidable, then the class which includes these functions becomes one for which the conditions of Theorem 1 apply. So its diagonal function is not in —which already implies that it is uncomputable. But if the Halting Problem were decidable, then it would be computable. This is a contradiction. So the Halting Problem is undecidable.
That’s how I ended this in my class. But one of the reasons we still get interested in our teaching after all these years is that you never know when things you didn’t know will pop up. Sometimes this comes from having a student re-do your lecture notes really carefully. Well in this case the “student” turned out to be Ken.
Delving Devilish Details
We want to justify that really has the properties we intuitively asserted. First, we may use the fact that there exists a universal Turing machine , and further, a machine that on any input simulates . Then define:
Our class hence includes the modified function which satisfies:
- If halts, i.e. halts, then .
- If does not halt, then . But also does not halt, so , so . Thus in this case too.
It follows that is the diagonal function for as we have defined it. This promises trouble. Indeed if the Halting Problem is decidable, then we get three conclusions:
- All the modified functions become computable, and hence the resulting class is the class of computable functions.
- Thus becomes closed under addition, as well as of course being non-trivial.
- Hence Theorem 1 applies, so the diagonal function is not in .
These add up to a contradiction. Q.E.D. Like I said in class. Why follow up the details? Sometimes there are devils in them. OK, devils are for Duke, whom Georgia Tech faces in football in two weeks. Our mascot is the Yellow Jacket, a common kind of bee, so we should say the idea is there can still be stingers in the details. In Buffalo, Ken says one can still be buffaloed by details.
Is There Still Trouble?
Suppose we don’t assume the Halting Problem is undecidable. Then what becomes of the above argument?
- We can still define to be the set of modified functions we obtain. Since whenever is computable, still includes all the computable functions.
- The diagonal function still belongs to . That part of the argument, with careful detail, didn’t need the assumption about the Halting Problem.
But this is troubling. By Theorem 1, is not supposed to belong to . Note that we are using the universal machine, and with we are implicitly using the S-m-n Theorem—so we are not doing any tricks with so-called inadmissible indexings in recursion theory. Indeed the closure under addition which we used is a kind of S-m-n property—taking since addition is a computable binary operation.
Do we have a contradiction, even without assuming anything about the Halting Problem? That mathematics might have a contradiction is another thing that sometimes makes us lose sleep at nights… After all, it happened to naive set theory with Bertrand Russell’s paradox and to Alonzo Church’s original lambda-based logic.
How It Adds Up
Atlanta is having fierce electrical storms and Ken is busy with complexity and chess research and much else, so we could have clicked send to leave this as a tease. Or we could have left this for our friend Neil L. But since there are classes next week, and it’s too early to pull a “fast one” on homework, we’ll give the answer.
The answer is that the subtle re-definition of here makes the addition property fail. To see why, consider adding to the function above, that is using the constant- function as . Then the resulting function is defined by:
We can in fact find a machine, which we can even arrange to be with the same index , which applies the add- operation to the original in cases where halts, thus giving:
However, this still is giving not in cases where doesn’t halt. This may seem a silly, technical, meaningless difference, but it’s enough to leave our intended closure function outside of the class as we defined it.
With our assumption that the Halting Problem is decidable, is still computable, and hence belongs to the way we defined it originally. That was a “semantic” definition as the class of computable functions. Without the assumption, we are left with a more “syntactic” definition as the set of ‘s, which isn’t large enough.
We can look for more trouble by supposing we have an oracle for the Halting Problem instead. Then take as the class of functions computable by machines with this oracle. We still have universality and S-m-n, and once again we have closure under addition. Do we get a contradiction? Or do we get some other interesting conclusion? This one we will leave for our readers to ponder.
All this is interesting because it shows another whisker that mathematics is saved by, and because it shows that the addition closure property has significance apart from Hartley Rogers’ universality and S-m-n axioms. Maybe not so fast on the latter—technically the bad by itself may not have an admissible indexing—but it’s certainly in the context of the standard indexing which does have these properties. Ken and I are interested because we are trying to think of closure properties of function classes that are more “organic” rather than dependent on the indexing, with possible application to complexity classes lower down.
How do you escape a diagonal contradiction when doing the above with the Halting Problem as an oracle? What does all this say about the delicacy of computational mathematics, even in the first two weeks of classes?