Skip to content

More on the Diagonal

September 1, 2013
tags: , , , , ,


A different angle on the Halting Problem

carnap03
src

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:

esp

Let’s take a look at the theorem.

An Abstract Version

Let {\mathbb{N}} be the natural numbers {\{0,1,2,3,\dots\}}. Let {\cal F} be a set of functions {\{f_{1}(x),f_{2}(x),\dots \}} so that for each number {k} in {\mathbb{N}},

\displaystyle f_{k}: \mathbb{N} \rightarrow \mathbb{N}.

Then we are interested in properties of such sets of functions. Call the set {\cal F} closed under addition provided for any {k} and {l} there is an {m} so that

\displaystyle f_{k}(x) + f_{l}(x) = f_{m}(x).

Also define the set {\cal F} as non-trivial provided there is a function {f_{p}(x)} in the set so that {f_{p}(x) \neq 0} for all {x}. Then the following simple theorem is true:

Theorem 1 Define {D(x)} by

\displaystyle D(x) = f_{x}(x).

Then {D(x)} is not in {\cal F}.

The function {D(x)} is sometimes called the diagonal function of {\cal F}.

The proof is quite simple. Suppose rather that {D(x)} is in the set {\cal F}. Then there is a {k} so that

\displaystyle D(x) = f_{k}(x).

Let {f_{p}(x)} be a function in {\cal F} that is always non-zero. Now by closure under addition it follows that {g(x) = f_{p}(x) + D(x)} is in the set {\cal F}. Thus there is an {m} such that {f_m} is the function {g}, and we have for all {x}:

\displaystyle f_{m}(x) = f_{p}(x) + f_{x}(x).

Set {x} equal to {m}. This yields {f_{m}(m) = f_{p}(m) + f_{m}(m)}, which is impossible over the natural numbers since {f_{p}(m) \neq 0}.

An Example

Let {\cal F} be the functions that are polynomials in {x}. They clearly satisfy the properties of the theorem. Hence their diagonal function cannot be in the set.

The Actual Halting Problem

Let {\cal F} be the set of functions {f} that are computable by some Turing Machine {M}. Then closure under addition and non-triviality are clear.

However, the set of Turing machines does not define an {\cal F} that we can apply the theorem to directly. The problem is that some machines {M_k} on some inputs may not halt, and so the corresponding functions {f_k} really are maps from {\mathbb{N}} to {\mathbb{N}^+ \cup \{\infty\}}. If we try to apply the theorem we get that

\displaystyle c + \infty = \infty,

for some {c}. But this is not a contradiction.

Instead, given {M_k}, let us define the modified function

\displaystyle f'_k(x) = 0 \text{ if } M_k(x) \text{ does not halt; } f'_k(x) = f_k(x) = M_k(x) \text{ otherwise.}

The quick version is that if the Halting Problem is decidable, then the class {\cal F'} which includes these functions becomes one for which the conditions of Theorem 1 apply. So its diagonal function is not in {\cal F'}—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 {\cal F'} really has the properties we intuitively asserted. First, we may use the fact that there exists a universal Turing machine {M_u}, and further, a machine {M_s} that on any input {x} simulates {M_u(x,x)}. Then define:

\displaystyle f_s(y) = M_s(x) \text{ if } M_s(x) \text{ halts; } = \infty \text{ otherwise.}

Our class {\cal F'} hence includes the modified function {f'_s} which satisfies:

  • If {M_s(x)} halts, i.e. {M_u(x,x)} halts, then {f'_s(x) = f_s(x) = f_x(x) = f'_x(x)}.

  • If {M_s(x)} does not halt, then {f'_s(x) = 0}. But also {M_u(x,x)} does not halt, so {f_x(x) = \infty}, so {f'_x(x) = 0}. Thus {f'_s(x) = f'_x(x)} in this case too.

It follows that {f'_s} is the diagonal function {D'} for {\cal F'} as we have defined it. This promises trouble. Indeed if the Halting Problem is decidable, then we get three conclusions:

  1. All the modified functions {f'_k} become computable, and hence the resulting class {\cal F'} is the class of computable functions.

  2. Thus {\cal F'} becomes closed under addition, as well as of course being non-trivial.

  3. Hence Theorem 1 applies, so the diagonal function is not in {\cal F'}.

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 {\cal F'} to be the set of modified functions {f'_k} we obtain. Since {f'_k = f_k} whenever {f_k} is computable, {\cal F'} still includes all the computable functions.

  • The diagonal function {D'} still belongs to {\cal F'}. That part of the argument, with careful detail, didn’t need the assumption about the Halting Problem.

But this is troubling. By Theorem 1, {D'} is not supposed to belong to {\cal F'}. Note that we are using the universal machine, and with {M_s} 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 {m = 2} 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 {\cal F'} here makes the addition property fail. To see why, consider adding {1} to the function {f'_k} above, that is using the constant-{1} function as {f_p}. Then the resulting function {f_l} is defined by:

\displaystyle f'_l(x) = 1 \text{ if } M_k(x) \text{ does not halt; } f'_l(x) = f_k(x) + 1 = M_k(x) + 1 \text{ otherwise.}

We can in fact find a machine, which we can even arrange to be {M_l} with the same index {l}, which applies the add-{1} operation to the original {M_k} in cases where {M_k(x)} halts, thus giving:

\displaystyle f'_l(x) = 1 \text{ if } M_l(x) \text{ does not halt; } f'_l(x) = f_l(x) = M_l(x) \text{ otherwise.}

However, this {f'_l} still is giving {1} not {0} in cases where {M_k} doesn’t halt. This may seem a silly, technical, meaningless difference, but it’s enough to leave our intended closure function {f'_l} outside of the class {\cal F'} as we defined it.

With our assumption that the Halting Problem is decidable, {f'_l} is still computable, and hence belongs to {\cal F'} 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 {f'_k}‘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 {\cal F'} as the class of functions computable by machines {M_k} 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.

Why Care?

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 {\cal F'} 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 {\cal F} that are more “organic” rather than dependent on the indexing, with possible application to complexity classes lower down.

Open Problems

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?

from → All Posts, History, Ideas, Oldies, Proofs
One Comment leave one →
  1. Héctor Corvalán permalink
    December 29, 2019 4:39 am

    I think Carnap made Gödel very doubtful about his own work. He never published his essay on Carnap and, apparently, when he visited the IAS in 1952-54, they avoided themselves.

    Reply

Leave a Reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading