Proving that the halting problem is undecidable without reductions or diagonalization?

Question

I'm currently teaching a class on computability and recently covered the proof that the halting problem is undecidable. I know of three major proof avenues that can be used here:

1. Diagonalization - show that if the halting problem were decidable, we could build a machine that, if run on itself, is forced to do the opposite of what it says it will do.
2. Recursion theorem - show that if the halting problem were decidable, then we could build a machine that obtains its own description, determines whether it halts on its input, then does the opposite.
3. Reduction - show that some other undecidable problem reduces to the halting problem.

While I completely understand these proofs and think that they're mathematically beautiful, many of my students are having trouble with them because none of the proofs directly address why you can't tell if a program will halt. Nothing in the above proceeds along the line of "computations can evolve in a way that is so complicated that we can't predict what will happen when we start them up" or "machines can't introspective on themselves at that level of detail." I often give these intuitions to my students when they ask why the result holds, but I'm not aware of any formal proofs of that form.

Are there any proofs of the undecidability of the halting problem that directly explore why it's impossible for a program to decide what another program will do?

Thanks!

Answer 1

This is not what you asked for, because it's not a proof. But it is an argument.

Consider some famous and unresolved problem of mathematics, such as the twin primes conjecture. (Or the Collatz conjecture, the Goldbach conjecture, or, until recently, the Fermat conjecture.) I am sure you recall that the conjecture is that there are arbitrarily large numbers $p$ and $p+2$ that are both prime. ("Twin primes")

It's easy to write a computer program which, given an input $N$, looks for a pair of twin primes larger than $N$, and which halts when it finds such a pair.

The twin primes conjecture is true if, and only if, this program halts on all inputs.

Therefore, if there were a reliable way to tell if a program halts on all inputs, the twin primes conjecture would be easy to resolve, and we could conclude from the fact that it is not resolved that mathematicians are all a bunch of dummies.

Now maybe your students don't care about the twin primes conjecture and perhaps they are not sure that mathematicians are not all a bunch of dummies. But they are familiar with problems and puzzles in general, and they are probably familiar with the idea that it is sometimes not only hard to find solutions, but it can even be hard to see ahead of time if if there is a solution. They can probably be persuaded that you can get a computer to search exhaustively for the solution to some problem, and halt and print it out if it finds one.

A solution to the halting problem would mean that a very large class of problems could be easily solved. You would write a program to search for a solution, and then, instead of running it, you would analyze the program to see if it would halt. If the answer was yes, you would know there was a solution, and all you had to do to find it was to run the program. On the other hand if the program would not halt, you wouldn't have to bother to run it because you would know there was no solution.

That would be a very different world from the one we actually live in, and it may be possible to persuade the students of that.

Answer 2

I realize this isn't exactly what you are asking for, because it still uses diagonalization, but I think it is a fresh approach to the halting problem.

I like to start with the paradoxical statement:

The smallest natural number that cannot be described uniquely in fourteen words or less.

This paradox is, obviously, not a precise statement, so it is not really a mathematical paradox. In particular, what does it mean to be "described?"

But in recursion theory, we can define what we mean by "described" and the size of a statement.

If we could solve the halting problem, we could write a program that computes, for any $N$ the smallest natural number that is not equal to $\phi_n(m)$ for $n,m\leq 2^{N}$. Essentially, we would, for each $n,m<2^N$, ask the halting program whether $\phi_n(m)$ halts, and, if so, compute the value and exclude it.

Say this program computes $\rho(N)$. Assuming the halting problem has a solution, then $\rho$ is recursive, so there is an $n_0$ such that $\rho=\phi_{n_0}$. But then $\rho(n_0)=\phi_{n_0}(n_0)$. This yields your contradiction. $\rho(n_0)$ cannot be the output of any $\phi_n(m)$ with $m,n<2^{n_0}$. But $\rho(n_0)=\phi_{n}(m)$ with $m=n=n_0<2^{n_0}$.

For some reason, I like starting with this informal paradox, and then working from there to try to formalize it, and seeing that, in formalizing it, we've gotten to showing that the halting problem has no solution.

As others have noted, I doubt you can avoid diagonalization at some point. In particular, you are talking about programs that analyze programs, so the "I am lying" paradox is always a risk in such a system.

You might, however, be able to talk about other unsolvable problems. Hilbert's 10th problem, seeking a program that takes a diophantine equation and returns whether it has a solution, would be easy to solve with a really limited subset of the halting problem.

You might also try to find limited subsets of the recursive functions for which you can solve the halting problem.

Answer 3

I agree that the usual proofs are not very "informative", in the sense that they don't usually satisfy a student's desire to know why this is the case. A "fully informative" proof would presumably construct the object in question -- but obviously you can't construct an object to show that it doesn't exist! I wouldn't exclude the possibility of finding a "somewhat informative" proof, but I think such a proof, if it exists, might be complicated enough that a persuasive but non-mathematical argument might be better.

Appealing to the idea you mentioned, that "computations can evolve in a way that is so complicated that we can't predict what will happen when we start them up", seems to be a good approach (possibly using the Collatz sequence as an example of a computation that, clearly, evolves in ways we don't yet understand very well.)

A complementary approach might be to ask the student to consider program analyzers. These are programs that take a program as input, and output "yes" if they can prove it has some property (like halting), "no" if they can prove it doesn't, and "don't know" if they can't prove either. There are real-world examples of these programs, and it can be shown some are more sophisticated than others, and tying the argument to real software may help some students get a better conceptual grip on it.

Now ask: what happens if we run one of these program analyzers on, say, the standard Python interpreter? The program analyzer can't truthfully say "yes" or "no", because it doesn't know what Python program the interpreter will be asked to run.

Even if we stipulate that the script that the Python interpreter will be running on be provided to the analyzer, the script itself could be an interpreter for some other programming language (ad infinitum).

Even if we stipulate that the program being analyzed take no input, it might be a Python interpreter with an arbitrary Python script hardcoded in it. (I believe there are actual tools available for Python to do just this.)

Now, this reasoning is not absolutely watertight, but the idea is to emphasize that you can make programs arbitrarily convoluted, and to try to get across, "oh, no matter how sophisticated my program analyzer is, there will always be some program that is so convoluted that it is out of its reach."