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

Solution 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.

Solution 2:

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."