The quintessential undecidable problem.
The Church-Turing Thesis tells us everything that can be done can be done by a computer. Cantor diagonalization suggests there are more problems than computer programs, which means there must be some problems we can’t solve. Today we look at one particular unsolvable problem, one of two known as the Halting Problem.
I give you a description of a process and an input to give that process. You answer back “yes” if the process will terminate in finite time given that input, or “no” if the process will run forever with that input. So, for example, if I gave you
and input “x = 1423452” you’d answer “yes”; but if I gave you the same process and “x = 13.3” you’d answer “no”.
That’s it. Simple problem: two inputs, one output. What I want is a description of a process, call it H(p, x), that solves this halting problem.
Let us suppose you have a candidate process H that you hope solves the halting problem. I’m going to demonstrate a particular set of inputs that shows it does not.
Here I’m assuming I have access to thisProgram via quining, as outlined in the previous post.
I now argue that the process H fails to solve the halting problem for inputs H(nasty, x) for any x. In particular, if H says nasty terminates in finite time on input x, then nasty runs forever on input x and vice versa.
Now you might argue, quite reasonably, that this is an idiotic little example and that no one actually cares about the behavior of programs that embed paradoxes like this. But that doesn’t get around the fact that, for any candidate H, the corresponding nasty program is well defined and, in fact, relatively easy to write. Which means that any program that solves the two-input halting problem can solve it for at most a subset of inputs.
The existence of nasty means that the two-input halting problem is undecidable, meaning there is no program anywhere that solves it in finite time for all inputs. When faced with an undecidable problem you must perforce pick a subproblem to solve instead of the whole thing. Undecidable problems are too big to be solved, ever, no matter what.
Now, a lot of people are uncomfortable with the idea of undecidable problems. All we’ve really shown is that we can write a paradox using the two-input halting problem. The program nasty is a weird case where we find out what you think we’ll do and then intentionally do the oposite just to spite you. Who cares what we think about paradoxes?
Couldn’t we make a program that is cleverer than H and instead of just saying “yes, it halts” or “no, it doesn’t halt” can also say “that’s a paradox”? The answer, it turns out, is that no, we can’t for any given functional definition of “paradox”. The reason hinges on something called “Rice’s Theorem” which demonstrates a huge class of undecidable problems which includes paradox-identification. I’ll go into that theorem in more detail in the next post.
In my experience, the same people who don’t buy the Cantor diagonalization argument also don’t buy the above proof that the halting problem is undecidable. Both proofs use the same general structure of saying “give me any solution and I’ll give you a pathological counter-example showing what you gave me wasn’t a solution after all.” As far as I know, neither the uncountability of the real numbers nor the undecidability of the halting problem has been proven except in classical logic where such proofs are valid.
Looking for comments…