Alternative conditions for deciding the halting problem

I have been trying to learn about the halting problem lately, in particular reviewing the proof that the halting problem is undecidable. I understand, abstractly, the idea of this proof, but it has always seemed to me like there is some sleight of hand involved – again, not that the proof isn't true, but that it strikes me as a bit of a technicality which doesn't capture the essence of determining computability/halting. As a result, it seems to me like there should be some alternative structure in which halting is decidable. Again, I am absolutely a novice and all of this could simply be my misunderstanding, but in that case it would still be nice to clear up my confusion.

As far as I understand, the proof goes as follows: assume program A(X, i) returns 1 if program X halts on input i, 0 otherwise. Then define program B(X): B returns 1 if A(X, int(X)) == 0, and loops otherwise, where int(X) returns the index that enumerates program X.

Considering B(B): A(B, int(B)) == 0 => B(B) does not halt, but in this case B(B) returns 1. Alternatively A(B, int(B)) == 1 => B(B) does halt, but in this case B(B) loops. This is a contradiction.

The part that trips me up is that in order to evaluate A(B, int(B)) in a programmatic manner would basically require invoking A once again, resulting in an infinite loop. I guess in this proof we are essentially thinking of the program A as a lookup table which has a 0 or 1 for each A(X, i). However, I feel like this goes against my understanding of computing in which I understand programs as things which operate upon inputs, with specific implementations, not predetermined lookup tables.

All of which is a long preamble to say: is there a way to redefine how we evaluate programs, or at least the class of programs that A() is taking as input, so as to able to decide the halting problem?

What bothers me about this proof is that it gives no insight into the structure of halting decidability – it only says that it is impossible to have one single program A that decides arbitrary programs B. Are there any results painting a clearer picture of what this structure could look like?

• I know a wondeful introduction into this topic (Joerg Resag : Die Grenzen der Berechenbarkeit) , where this problem is discussed quite intuitively. But it is in german language. – Peter Jun 26 at 19:39
• In practice, we do not have the equivalent of an infinite tape, but the problem occurs also in real programs. Suppose, you have run a complicated program for a day and it did not halt. You may try to prove it never halts. But you fail. The problem is that you cannot wait forever, whether the program will ever halt. It could run extremely long and then halt. Already for turing machines with $7$ states and $2$ symbols , the number of steps a turing machine can make before halting is larger than $10\uparrow \uparrow 5$ (that is a power tower of $5$ tens!) – Peter Jun 26 at 19:42

I'm going to answer this in two parts. First I'll try to demystify the argument above, and then I'll say a bit about what an algorithm actually is or isn't.

The issue you raise is a common one - that the way we "defeat" $$A$$ feels circular, or at the very least slippery:

The part that trips me up is that in order to evaluate $$A(B, int(B))$$ in a programmatic manner would basically require invoking A once again, resulting in an infinite loop.

The "loopiness" of $$A(B,int(B))$$ - namely that there isn't really any "coherent interpretation" of what that computation should be doing - is exactly what we're shooting for: the weirdness of $$A(B,int(B))$$ is a sign that our original $$A$$ is dubious.

I think the reason that this feels slippery is that our intuition frequently assigns fault incorrectly. The shape of the argument is basically: "given $$A$$, we build $$B$$, and then weird stuff happens." This can make it feel like the weirdness is $$B$$'s fault, that is, that $$B$$ is the source of the "loopiness." However, this isn't right. Rather, $$A$$ itself (were it to exist) has "loopiness," and our construction of $$B$$ is merely unveiling the weird (and indeed impossible) behavior of $$A$$.

It may help to rephrase the theorem as follows. Say that a machine $$A$$ is halting-correct iff for every machine $$C$$ and number $$n$$ we have $$A(C,n)=1\implies C(n)\downarrow\quad\mbox{and}\quad A(C,n)=0\implies C(n)\uparrow.$$ Basically, $$A$$ might not answer, but if $$A$$ answers then $$A$$ gets the question "Does $$C(n)$$ halt?" correct. There are lots of halting-correct programs, such as:

• On input $$(C,n)$$, run $$C(n)$$ for $$17$$ stages and output $$1$$ if the result halts, and don't output anything otherwise.

• Just don't do anything on any input whatsoever.

• Etc.

However, the argument above shows the following:

There is a "computable function from programs to programs," $$\mathfrak{B}$$, such that for every halting-correct $$A$$ we have $$A(\mathfrak{B}(A),int(\mathfrak{B}(A)))\uparrow$$.

(Compare this with the constructive version of Cantor's theorem: that there is a functional $$\mathfrak{F}$$ which takes in any map $$f:\mathbb{N}\rightarrow\mathbb{R}$$ and spits out a real $$\mathfrak{F}(f)$$ with $$\mathfrak{F}(f)\not\in ran(f)$$.)

Specifically, given a program $$C$$ the program $$\mathfrak{B}(C)$$ does the following: on input $$X$$, it runs $$C(X, int(X))$$. If that "subcomputation" never halts, then $$\mathfrak{B}(C)(X)$$ doesn't halt either. Otherwise, if that "subcomputation" halts and outputs $$0$$, $$\mathfrak{B}(C)(X)$$ halts and outputs $$1$$, and if that subcomputation halts and outputs $$1$$ then $$\mathfrak{B}(C)(X)$$ goes into an endless loop. Note that there's nothing hypothetical here: $$\mathfrak{B}$$ really does make sense, and for every program $$C$$ the program $$\mathfrak{B}(C)$$ really does exist and behave as described. And in the particular case that $$C$$ is halting-correct, $$\mathfrak{B}(C)$$ happens to have the additional nice property that $$C(\mathfrak{B}(C), int(\mathfrak{B}(C)))$$ does not halt - which tells us in particular that there is no total halting-correct program, or to put it another way that the halting problem is incomputable.

OK, now on to the other issue: how do we think about what a program actually is?

You get at this when you write:

I guess in this proof we are essentially thinking of the program $$A$$ as a lookup table which has a $$0$$ or $$1$$ for each $$A(X, i)$$. However, I feel like this goes against my understanding of computing in which I understand programs as things which operate upon inputs, with specific implementations, not predetermined lookup tables.

First of all, let me make a slight quibble. Actually $$A$$ is a "delayed lookup" table, or a lookup table with three variables: cell $$(X,i,s)$$ has either $$0$$, $$1$$, or $$\Box$$, depending on whether $$A(X,i)$$ has halted and output $$0$$ by stage $$s$$, has halted and output $$1$$ by stage $$s$$, or has not yet halted by stage $$s$$. (Without this delay we'd be able to tell ahead of time what a program is going to do!)

This is extremely important, but it's not relevant to what I think is your actual concern here: that lookup tables, no matter how many "dimensions" they have, are structureless or arbitrary in a way that real algorithms aren't. And the answer, unfortunately, is that this is just the way it is. Genuinely arbitrary programs really are morally equivalent to tables with values. Of course they'll often be presented as dynamical phenomena, like Turing machines, but that additional structure is really superficial once we look at the whole class of computable functions.

The disconnect between computable functions in full generality and the specific concrete algorithms we play around with in everyday life is a genuine intuitive hurdle. I think my take on it is the following. When I describe (say) the Euclidean algorithm to you, I'm not just describing an algorithm; I'm also describing its semantics, namely that the running of the program is paralleled by the transformation of some better-understood mathematical object (a pair of integers in this case). That semantic behavior is what I really care about, and it's what I have in mind when I prove that the Euclidean algorithm always halts.

The point is that this semantic interpretation is useful because it's more natural than the program itself. However, an arbitrary "Turing machine in the wild" need not have any obvious "natural semantics" describing its behavior; of course for any reasonable definition of "semantics" we can artificially produce one, but this will in general amount to just rephrasing the original machine itself. (For that matter, the Turing machine model is itself a semantics in some sense!)

So yes, we do in general have to adopt a more "austere" notion of what a program is or is doing. This will however become much more intuitive and comfortable over time. (Incidentally, a natural reaction at this point is "Well why don't we study 'meaningful algorithms' instead of arbitrary computations instead?" Well, it turns out that there are some issues there.)

• It is Ok answer, just too many letters. – JCAA Jun 27 at 1:51
• @JCAA Some questions require longer answers than others; this is the approach I found appropriate for this question. You can of course write a shorter one if you like. – Noah Schweber Jun 27 at 1:53
• The display immediately before "Basically $A$ might not answer" has two occurrences of $\iff$ that you apparently intended to be $\implies$. – Andreas Blass Jun 27 at 3:14
• @AndreasBlass Oh wow that's bad - fixed, thanks! – Noah Schweber Jun 27 at 3:15
• "If that "subcomputation" never halts, then B(X) doesn't halt either." --> I guess what you are trying to say is that the "loopiness" of A is precisely part of the problem since the halting-deciding program A() must by definition always halt. And in a way you are exploiting that very stringent criteria on A(). I was getting caught up on the exploitation, when I should have gotten caught up on the stringency of the original criteria. Is this a good way to think about it? – swedishfished Jun 27 at 3:29

I think it's best to think of this argument as constructively proving the following:

For any program $$A$$ that takes as arguments some program $$X$$ and some input $$i$$, there is a pair $$(X,i)$$ where either:

• $$X$$ halts on input $$i$$ and $$A(X,i)=0$$
• $$X$$ does not halt on input $$i$$ and $$A(X,i)\neq 0$$.
• $$A$$ does not halt when given inputs $$(X,i)$$.

One would have to fix a representation of "programs" to make this totally formal (e.g. using Turing machines or lambda calculus or something of that nature), but it turns out not to really matter - they can all represent the kind of functional reasoning happening here. The usual way to interpret this theorem is that "there is no Turing machine that can decide the halting problem."

This is just the usual "for all blah there exists blah" sort of proof where you fix $$A$$ from the universal quantifier, then, in terms of $$A$$, write a counterexample $$(X,i)$$ to satisfy the existential quantifier. In this particular case, we are defining $$X$$ to be the program described as:

• Compute $$A(i, i)$$.
• If this computation was $$0$$, halt immediately.
• If this computation was not $$0$$, loop forever.

Which is completely valid - $$A$$ is just some fixed program that we already chose, so we can embed it into a new program and call it. However, one realizes that the pair $$(X,X)$$ must fall into one of the three cases we wished to show - depending on whether $$A(X,X)$$ halts and what it returns.

The nice thing here is that this is shows that we have a constructive proof, so you can work out examples to demystify it. For instance, if $$A$$ were the program that always returned $$0$$, then $$X$$ would end up being a program that queries $$A(X,X)$$ - which immediately returns $$0$$ since it's a constant function - and then halts due to the if statement. There's nothing inherently suspicious here - we wrote a program $$A$$, then invoked it once from another program, then used its results. Completely normal functional programming - not even anything hard like loops or recursion.

Obviously, you could apply this to more interesting functions, such as if you defined $$A(X,i)$$ to be something like "run the program $$X$$ on the input $$i$$. Return $$1$$ if it halted" where there really is recursion - the program $$X(X)$$ would call $$A(X,X)$$ which calls $$X(X)$$ which calls $$A(X,X)$$ ad infinitum - and this witnesses that $$A$$ fails to halt on the input $$(X,X)$$. Similarly, if $$A(X,i)$$ were "run the program $$X$$ on input $$i$$ for an hour. Return whether it halted" you would get this same recursion - but it would cut off after an hour (or a more suitable unit of computation - but let's not be too particular) and return $$1$$, after which $$X(X)$$ would loop forever, witnessing that $$A$$ failed to correctly decide if $$X(X)$$ halts.

There are certainly other models of computation that somewhat avoid this issue - for instance, this says nothing about what happens if $$A$$ is not a program and cannot be embedded into $$X$$, so nothing stops you from talking about an oracle which, given an input $$A(X,i)$$ always correctly answers the halting problem - but which is not itself computable, since we aren't allowed to call $$A$$ from $$X$$. However, then you run into the issue that, even with access to this oracle, a program cannot decide whether another program with access to the oracle halts, since then we would be allowed to query $$A$$ from $$X$$, and our proof goes through again.

You can also go down the constructivist route, especially in fields such as type theory, where you can create a lot of interesting "programs" without introducing the possibility that a program might not halt - usually, you would do this by replacing ideas like recursion and loops with a notion of induction instead that cannot be used to create infinite loops. However, this limits what qualifies as a "program" - you're not talking about Turing machines or programs in their usual sense if you go down this route. This way also tends to look a lot like cheating because it essentially limits the discussion of functions to computable functions that provably halt for all inputs - so you wouldn't be talking about the halting problem anyways since halting is baked into the system.