The halting problem has always bugged me. Recap: assume someone wrote a function halt(f) that returns true if f halts, and false if f runs forever. We write a function f that says:
f():
..if(halt(f)) then run forever
..else halt
That is, see what halt thinks we're going to do. Then do the opposite, forcing halt to be wrong about what we're going to do. Since we can contradict halt(), it must not be possible to write a halt() that's always right.
That always seemed to me like cheating: ask the fortune teller what word you're going to say next, then say something else.
Today I asked myself what I'd do if I had to answer whether a given function halts. I'd do the following:
halt(f):
..if we're being called by a program trying to make a liar of halt(), then:
....print("This program tries to make a liar of halt. I will lie to the program to ensure it halts.")
....return false
..else if f calls halt() and contradicts its output, then:
....print("Note: this program tries to contradict halt(), but that's okay because I always lie to such programs to ensure they halt.")
....print("Program halts.")
....return true
..else if f just plain halts, then:
....print("Program halts.")
....return true
..else:
....print("Program runs forever.")
....return false
Then if we call halt(f), we get:
Note: this program tries to contradict halt(), but that's okay because I always lie to such programs to ensure they halt.
Program halts.
But if we call f(), we get:
This program tries to make a liar of halt. I will lie to the program to ensure it halts.
halt() then returns false to f(), and f() indeed does halt as predicted. In each case, halt() provides me the most useful answer to the question at hand, and is always correct in a certain sense. That is, it does lie to f(), but it does it on purpose and lets you know that.
So, I've made a social argument about a useful definition for halt(). But I did have to give halt() a supernatural power to make it work, at least as far as normal functions are concerned. halt() has to be able to examine not only the function passed to it, but the function that *calls* it, in order to operate correctly. That is, halt() behaves differently when we simply called halt(f) than when we called halt(f) *from within f() itself*! Same call, different calling context, and that makes all the difference.
Of course, that's not allowed for proper functions: the rules say that your function's universe has to contain only itself and its arguments. So proper functions have no way of knowing that the function calling them is trying to make a liar out of them.
So here's a slightly less informative but altogether more conventional kind of function:
halt(f):
..if f tries to contradict the output of halt() then return -1
..if f halts then return 1
..if f runs forever then return 0
This one breaks the problem of "halting" into three pieces instead of two: programs either halt, run forever, or are smartasses that try to take advantage of halt(). The question then becomes how many functions fall into the "smartass" category, not whether there exists a function that can tell you how arbitrary programs behave. If it turns out that lots of interesting functions actually have that smartass nature by "accident" as it were (that is, that the "smartass" property is intrinsic to something important they're trying to tell us about the world but can't because they fall into the middle category), then I might actually be inclined to agree that the question of halting is a great mystery of the universe. But that seems doubtful to me, and I don't know of any functions of that sort.
So I guess what I'm saying is that sure, halting taken as a dichotomy is uncomputable in the rigorous mathematical sense, but that doesn't tell us anything at all useful about how hard it is to tell whether programs actually halt, because the answer isn't a dichotomy. (And also because halting is actually solvable for finite machines, but that's another rant).
Okay, so now having written that, I had to scratch my head: have I actually said anything new or interesting here? Well, it's almost certainly not new, but I think there are common perceptions that are totally wrong. Take this example from CS theory class slides, italics added:
Link to slides.
"Why should we care that HP is undecidable?
It’s not that people have tried for centuries to solve the Halting Problem and are now deeply disappointed to discover that no algorithm exists.
It is that we now know that decision problems exist that are unsolvable. There are things we can imagine wanting to do, but which cannot be done by following an algorithm.
Equivalently, we now know there are recursively enumerable languages that are not recursive. For such languages, we have no parsing algorithm that will terminate on all inputs.
Are there no practical applications of HP?
Sometimes, programs loop. So you may want to design a compiler that warns the programmer if asked to compile a program that will loop.
The undecidability of HP tells you that unless you limit the range of programs in some way, you will not be able to design such a compiler."
I claim that the first and last italicized statements are wrong. The second statement is interesting, but I'd have to ponder some more. (I italicized it because it might point to something interesting about the "smartass" class of problems.)
