Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

Question

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization.

While the proof is convincing (I understand each step of it), it is not intuitive to me in the sense that I don't see how someone would derive it, starting from the problem alone.

In the book, the proof goes like this: "suppose $M_H$ solves the halting problem on an input $M;x$, that is, decides whether Turing machine $M$ halts for input $x$. Construct a Turing machine $D$ that takes a Turing machine $M$ as input, runs $M_H(M;M)$ and reverses the output." It then goes on to show that $D(D)$ cannot produce a satisfactory output.

It is the seemingly arbitrary construction of $D$, particularly the idea of feeding $M$ to itself, and then $D$ to itself, that I would like to have an intuition for. What led people to define those constructs and steps in the first place?

Does anyone have an explanation on how someone would reason their way into the diagonalization argument (or some other proof), if they did not know that type of argument to start with?

Addendum given the first round of answers:

So the first answers point out that proving the undecidability of the halting problem was something based on Cantor and Russell's previous work and development of the diagonalization problem, and that starting "from scratch" would simply mean having to rediscover that argument.

Fair enough. However, even if we accept the diagonalization argument as a well-understood given, I still find there is an "intuition gap" from it to the halting problem. Cantor's proof of the real numbers uncountability I actually find fairly intuitive; Russell's paradox even more so.

What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you define them.

P.S.

@babou summarized what was troubling me better than myself: "The problem with many versions of the proof is that the constructions seem to be pulled from a magic hat."

Answer 1

In your edit, you write:

What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you define them.

A common "popular" summarization of Turing's proof goes something like this:

"If we had a machine $M_H$ that could decide whether another Turing machine halts or not, we could use this to construct another machine $D$ that, given a Turing machine $M$, would halt if and only if $M$ did not halt. But then we could pass $D$ as input to itself, and thus obtain a paradox: this machine would halt if and only if it did not halt!"

Now, it's easy to see that the summarization above glosses over an important detail — the halting of the Turing machine $M$ also depends on its input, which we have not specified! But this issue can be fixed easily enough: we just need to have $D$ pick some suitable input $x_M$ for each input machine $M$, before passing them both to $M_H$.

What's a suitable choice for $x_M$, given that we ultimately want to derive a contradiction? Well, a natural choice is suggested directly by the "handwavy" proof above, where we ultimately obtain the contradiction by running the machine $D$ on itself.

Thus, for the behavior of $D$ to really be paradoxical in this case, i.e. when invoked as $D(D)$, what we want is for the halting of $D(M)$ to depend on the behavior of $M$ when invoked as $M(M)$. This way, we'll obtain the contradiction we want by setting $M = D$.

Mind you, this is not the only choice; we could also have derived the same contradiction by, say, constructing a machine $D'$ such that $D'(M)$ halts if and only if $M(D')$ (rather than $M(M)$) does not halt. But, whereas it's clear that the machine $D$ can easily duplicate its input before passing it to $M_H$, it's not quite so immediately obvious how to construct a machine $D'$ that would invoke $M_H$ with its own code as the input. Thus, using this $D'$ instead of $D$ would needlessly complicate the proof, and make it less intuitive.

Answer 2

It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context.

Remember that Turing knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (which uses a diagonalisation argument) and Gödel's first incompleteness theorem (which uses a diagonalisation argument). In fact, Gödel's result is deeply related to the proof of undecidability of the Halting Problem (and hence the negative answer to Hilbert's Entscheidungsproblem).

So my contention is that your question is in a sense badly founded and that you can't reach the Halting Problem without going past the rest (or something remarkably similar) first. While we show these things to students without going through the history, if you were a working mathematician it seems unlikely that you go from nothing to Turing Machines without anything in between - the whole point of them was to formalise computation, a problem many people had been working on for decades at that point.

Cantor didn't even use diagonalisation in his first proof of the uncountability of the reals, if we take publication dates as an approximation of when he thought of the idea (not always a reliable thing), it took him about 17 years from already knowing that the reals were uncountable, to working out the diagonalisation argument.

In reference to the "self-application" in the proof that you mention, this is also an integral part of Russell's paradox (which entirely depends upon self-reference), and Gödel's first incompleteness theorem is like the high-powered version of Russell's paradox. The proof of the undecidability of the Halting Problem is so heavily informed by Gödel's work that it's hard to imagine getting there without it, hence the idea of "self-application" is already part of the background knowledge you need to get to the Halting Problem. Similarly, Gödel's work is a reworking of Russell's paradox, so you don't get there without the other (note that Russell was not the first to observe a paradox like this, so prototypes of the diagonalisation argument has been around in formal logic since about 600BCE). Both Turing and Gödel's work (the bits we're talking about here that is) can be viewed as increasingly powerful demonstrations of the problems with self-reference, and how it is embedding in mathematics. So once again, it's very difficult to suggest that these ideas at the level Turing was dealing with them came a priori, they were the culmination of millennia's work in parts of philosophy, mathematics and logic.

This self-reference is also part of Cantor's argument, it just isn't presented in such an unnatural language as Turing's more fundamentally logical work. Cantor's diagonalisation can be rephrased as a selection of elements from the power set of a set (essentially part of Cantor's Theorem). If we consider the set of (positive) reals as subsets of the naturals (note we don't really need the digits to be ordered for this to work, it just makes a simpler presentation) and claim there is a surjection from the naturals to the reals, then we can produce an element of the power set (i.e. a real) that is not in the image of the surjection (and hence derive a contradiction) by take this element to be the set of naturals who are not in their own image under the surjection. Once we phrase it this way, it's much easier to see that Russell's paradox is really the naïve set theory version of the same idea.

Answer 3

Self application is not a necessary ingredient of the proof

In a nutshell

If there is a Turing machine $H$ that solves the halting problem, then from that machine we can build another Turing machine $L$ with a halting behavior (halting characteristic function) that cannot be the halting behavior of any Turing machine.

The paradox built on the self applied function $D$ (called $L$ in this answer - sorry about notation inconsistencies) is not a necessary ingredient of the proof, but a device usable with the construction of one specific contradiction, hiding what seems to be the "real purpose" of the construction. That is probably why it is not intuitive.

It seems more direct to show that there is only a denumerable number of halting behaviors (no more than Turing machines), that can be defined as characteristic halting functions associated with each Turing machine. One can define constructively a characteristic halting function not in the list, and build from it, and from a machine $H$ that solves the halting problem, a machine $L$ that has that new characteristic halting function. But since, by construction, it is not the characteristic halting function of a Turing machine, $L$ cannot be one. Since $L$ is built from $H$ using Turing machine building techniques, $H$ cannot be a Turing machine.

The self-application of $L$ to itself, used in many proofs, is a way to show the contradiction. But it works only when the impossible characteristic halting function is built from the diagonal of the list of Turing permitted characteristic halting functions, by flipping this diagonal (exchanging $0$ and $1$). But there are infinitely many other ways of building a new characteristic halting function. Then non-Turing-ness can no longer be evidenced with a liar paradox (at least not simply). The self-application construction is not intuitive because it is not essential, but it looks slick when pulled out of the magic hat.

Basically, $L$ is not a Turing machine because it is designed from the start to have a halting behavior that is not that of a Turing machine, and that can be shown more directly, hence more intuitively.

Note: It may be that, for any constructive choice of the impossible characteristic halting function, there is a computable reordering of the Turing machine enumeration such that it becomes the diagonal ( I do not know). But, imho, this does not change the fact that self-application is an indirect proof technique that is hiding a more intuitive and interesting fact.

Detailed analysis of the proofs

I am not going to be historical (but thanks to those who are, I enjoy it), but I am only trying to work the intuitive side.

I think that the presentation given @vzn, which I did encounter a long time ago (I had forgotten), is actually rather intuitive, and even explains the name diagonalization. I am repeating it in details only because I feel @vzn did not emphasize enough its simplicity.

My purpose is to have an intuitive way to retrieve the proof, knowing that of Cantor. The problem with many versions of the proof is that the constructions seem to be pulled from a magic hat.

The proof that I give is not exactly the same as in the question, but it is correct, as far as I can see. If I did not make a mistake, it is intuitive enough since I could retrieve it after more years than I care to count, working on very different issues.

The case of the subsets of $\mathbb N$ (Cantor)

The proof of Cantor assumes (it is only an hypothesis) that there is an enumeration of the subsets of the integers, so that all such subset $S_j$ can be described by its characteristic function $C_j(i)$ which is $1$ if $i\in S_j$ and is $0$ otherwise.

This may be seen as a table $T$, such that $T[i,j]=C_j(i)$

Then, considering the diagonal, we build a characteristic function $D$ such that $D(i)=\overline{T[i,i]}$, i.e. it is identical to the diagonal of the table with every bit flipped to the other value.

There is nothing special about the diagonal, except that it is an easy way to get a characteristic function $D$ that is different from all others, and that is all we need.

Hence, the subset characterized by $D$ cannot be in the enumeration. Since that would be true of any enumeration, there cannot be an enumeration that enumerates all the subsets of $\mathbb N$.

This is admittedly, according to the initial question, fairly intuitive. Can we make the proof of the halting problem as intuitive?

The case of the halting problem (Turing)

We assume we have an enumeration of Turing machines (which we know is possible). The halting behavior of a Turing machine $M_j$ can be described by its characteristic halting function $H_j(i)$ which is $1$ if $M_j$ halts on input $i$ and is $0$ otherwise.

This may be seen as a table $T$, such that $T[i,j]=H_j(i)$

Then, considering the diagonal, we build a characteristic halting function $D$ such that $D(i)=\overline{T[i,i]}$, i.e. it is identical to the diagonal of the table with every bit flipped to the other value.

There is nothing special about the diagonal, except that it is an easy way to get a characteristic halting function $D$ that is different from all others, and that is all we need (see note at the bottom).

Hence, the halting behavior characterized by $D$ cannot be that of a Turing machine in the enumeration. Since we enumerated them all, we conclude that there is no Turing machine with that behavior.

No halting oracle so far, and no computability hypothesis: We know nothing of the computability of $T$ and of the functions $H_j$.

Now suppose we have a Turing machine $H$ that can solve the halting problem, such that $H(i,j)$ always halts with $H_j(i)$ as result.

We want to prove that, given $H$, we can build a machine $L$ that has the characteristic halting function $D$. The machine $L$ is nearly identical to $H$, so that $L(i)$ mimics $H(i,i)$, except that whenever $H(i,i)$ is about to terminate with value $1$, $L(i)$ goes into an infinite loop and does not terminate.

It is quite clear that we can build such a machine $L$ if $H$ exists. Hence this machine should be in our initial enumeration of all machines (which we know is possible). But it cannot be since its halting behavior $D$ corresponds to none of the machines enumerated. Machine $L$ cannot exist, which implies that $H$ cannot exist.

_{I deliberately mimicked the first proof and went into tiny details}

My feeling is that the steps come naturally in this way, especially when one considers Cantor's proof as reasonably intuitive.

One first enumerates the litigious constructs. Then one takes and modifies the diagonal as a convenient way of touching all of them to get an unaccounted for behaviour, then gets a contradiction by exhibiting an object that has the unaccounted for behaviour ... if some hypothesis were to be true: existence of the enumeration for Cantor, and existence of a computable halting oracle for Turing.

Note: To define the function $D$, we could replace the flipped diagonal by any other characteristic halting function, different from all the ones listed in $T$, that is computable (from the ones listed in $T$, for example) provided a halting oracle is available. Then the machine $L$ would have to be constructed accordingly, to have $D$ as characteristic halting function, and $L(i)$ would make use of the machine $H$, but not mimic so directly $H(i,i)$. The choice of the diagonal makes it much simpler.

Comparison with the "other" proof

The function $L$ defined here is apparently the analog of the function $D$ in the proof described in the question.

We only build it in such a way that it has a characteristic halting function that corresponds to no Turing machine, and get directly a contradiction from that. This gives us the freedom of not using the diagonal (for what it is worth).

The idea of the "usual" proof seems to try to kill what I see as a dead fish. It says: let's assume that $L$ is one of the machines that were listed (i.e., all of them). Then it has an index $j_L$ in that enumeration: $L=M_{j_L}$. Then if $L(j_L)$ halts, we have $T[j_L,j_L]=H(j_L,j_L)=1$, so that $L(j_L)$ will loop by construction. Conversely, if $L(j_L)$ does not halt, then $T[j_L,j_L]=H(j_L,j_L)=0$ so that $L(j_L)$ will halt by construction. Thus we have a contradiction. But the contradiction results from the way the characteristic halting function of $L$ was constructed, and it seems a lot simpler just to say that $L$ cannot be a Turing machine because it is constructed to have a characteristic halting function that is not that of a Turing machine.

A side-point is that this usual proof would be a lot more painful if we did not choose the diagonal, while the direct approach used above has no problem with it. Whether that can be useful, I do not know.

Answer 4

There is also a proof of this fact that uses a different paradox, Berry's paradox, which I heard from Ran Raz.

Suppose that the halting problem were computable. Let $B(n)$ be the smallest natural number that cannot be computed by a C program of length $n$. That is, if $S(n)$ is the set of natural numbers computed by C programs of length $n$, then $B(n)$ is the smallest natural number not in $S(n)$.

Consider the following program:

1. Go over all C programs of length at most $n$.

2. For each such program, check if it halts; if it does, add it to a list $L$.

3. Output the first natural number not in $L$.

This is a program for computing $B(n)$. How large is this program? Encoding $n$ takes $O(\log n)$ characters, and the rest of the program doesn't depend on $n$, so in total the length is $O(\log n)$, say at most $C\log n$. Choose $N$ so that $C\log N \leq N$. Then our program, whose length is at most $N$, computes $B(N)$, contradicting the definition of $B(N)$.

The same idea can be used to prove Gödel's incompleteness theorems, as shown by Kritchman and Raz.

Answer 5

There's a more general idea involved here called the "recursion theorem" that may be more intuitive: Turing machines can use their own description (and thus run themselves). More precisely, there is a theorem:

For any Turing machine T, there is a Turing machine R that computes R(x) = T(R;x).

If we had a Turing machine that could solve the halting problem, then using the idea described above, we can easily construct a variety of "liar" turing machines: e.g. in python-like notation,

def liar():
    if halts(liar):
        return not liar()
        # or we could do an infinite loop
    else:
        return True

The more complicated argument is essentially just trying to do this directly without appealing to the recursion theorem. That is, it's repeating a recipe for constructing "self-referential" functions. e.g. given a Turing machine T, here is one such recipe for constructing an R satisfying

R(x) = T(R; x)

First, define

S(M; x) = T(M(M; -); x)

where by M(M; -), what I really mean is that we compute (using the description of M) and plug in a description of a Turing machine that, on input y, evaluates M(M; y).

Now, we observe that if we plug S into itself

S(S; x) = T(S(S; -); x)

we get the duplication we want. So if we set

R = S(S; -)

then we have

R(x) = T(R; x)

as desired.

Answer 6

the Turing proof is quite similar to Cantors proof that the cardinality of reals ("uncountable") is larger than the cardinality of the rationals ("countable") because they cannot be put into 1-1 correspondence but this is not noted/ emphasized in very many references (does anyone know any?). (iirc) a CS prof once showed this years ago in class (not sure where he got it himself). in Cantors proof one can imagine a grid with horizontal dimension the n^th digit of the number and the vertical dimension the n^th number of the set.

the Turing halting proof construction is quite similar except that the contents of the table are Halt/ Nonhalt for 1/ 0 instead, and the horizontal axis is n^th input, and the vertical axis is n^th computer program. in other words the combination of computer programs and inputs are countable but the infinite table/ array is uncountable based on a universal machine simulator construction that can "flip" a halting to a nonhalting case assuming a halting detector machine exists (hence reductio ad absurdam).

some evidence that Turing had Cantors construction partly in mind is that his same paper with the halting proof talks about computable numbers as (along the lines of) real numbers with computable digits.

Answer 7

At this point it is worth noting the work by Emil Post who is (justly) credited with being a co-discoverer of the basic results of computability, though sadly was published too late to be considered a co-discoverer of the solution to the Entscheidungsproblem. He certainly participated in the elaboration of the so-called Church-Turing thesis.

Post was motivated by very philosophical considerations, namely the theoretical limitations of the human ability to compute, or even get precise answers in a consistent manner. He devised a system, now called Post canonical systems, the details of which are unimportant, which he claimed could be used to solve any problem which can be solved soely by manipulation of symbols. Interestingly, he explicitly considered mental states to be part of the "memory" explicitly, so it is likely that he at least considered his model of computation to be a model of human thought in it's entirety.

The Entscheidungsproblem considers the possibility of using such a means of computation to say, determine the theoremhood of any proposition expressible in the system of the Principia Mathematica. But the PM was a system explicitly designed to be able to represent all of mathematical reasoning, and, by extension (at least at the time, when Logicism was still in vogue) all of human reasoning!

It's therefore very unsurprising then, to turn the attention of such a system to the Post canonical systems themselves, just as the human mind, via the works of Frege, Russel and logicians of the turn of the century had turned their attention to the reasoning faculty of the human mind itself.

So it is clear at this point, that self-reference, or the ability of systems to describe themselves, was a rather natural subject in the early 1930s. In fact, David Hilbert was hoping to "bootstrap" mathematical reasoning itself, by providing a formal description of all of human mathematics, which then could be mathematically proven to be consistent itself!

Once the step of using a formal system to reason about itself is obtained, it's a hop and a skip away from the usual self-referential paradoxes (which have a pretty old history).

Since all the statements in Principia are presumed to be "true" in some metaphysical sense, and the Principia can express

program p returns result true on input n

if a program exists to decide all theorems in that system, it is quite simple to directly express the liar's paradox:

this program always lies.

can be expressed by

The program p always returns the opposite of what the principia mathematica say p will return.

The difficulty is building the program p. But at this point, it's rather natural to consider the more general sentence

The program p always returns the opposite of what the PM say q will return.

for some arbitrary q. But it's easy to build p(q) for any given q! Just compute what PM predicts it will output, and return the opposite answer. We can't just replace q by p at this point though, since p takes q as input, and q does not (it takes no input). Let's change our sentence so that p does take input:

The program p returns the opposite of what PM says q(r) will return.

Arg! But now p takes 2 pieces of input: q and r, whereas q only takes 1. But wait: we want p in both places anyways, so r is not a new piece of information, but just the same piece of data again, namely q! This is the critical observation.

So we finally get

The program p returns the opposite of what PM says q(q) will return.

Let's forget about this silly "PM says" business, and we get

The program p(q) returns the opposite of what q(q) will return.

This is a legitimate program provided we have a program that always tells us what q(q) returns. But now that we have our program p(q), we can replace q by p and get our liar's paradox.