Re: Halting Problem
- From: "Alf P. Steinbach" <alfps@xxxxxxxx>
- Date: Wed, 01 Apr 2009 12:29:04 +0200
* none:
I really struggle with Turing's proof that the halting problem is undecidable. My understanding is basically this:
Suppose I write a function that solves the halting problem for all programs and all inputs:
1: bool halts(void *program, void *input)
2: {
3: // returns true if "program(input)" halts
4: }
At a point in time AFTER I've written my program, someone writes another program that includes my "halts" function:
5: void might_halt()
6: {
7: if (halts(might_halt, might_halt))
8: {
9: while (1);
10: }
11: }
And the proof says that this presents a paradox, because:
- If halts() returns true on line 7, then might_halt() would jump into the infinite loop on line 9 (and never halt).
- If halts() returns false on line 7, then might_halt() proceeds to line 11 and halts.
OK.
So the conclusion is that the halts() funtion would always be wrong in this case, and the magic required to make "halts" work (line 3) cannot be written. The existance of such a function would be a logical paradox.
Suppose that some poor soul who had never heard of Turing attempted to fill in the halts() function. He or she would probably write some sort of tree-building algorithm. Every conditional branching statement (if, for, while, etc.) would be represented as a parent node with two children -- one for "branch taken" and one for "branch not taken." Simple enough. Once you've built the whole tree, just collapse it and see whether (for this particular given input) you come to a "leaf" in the tree or end up in a cycle that never reaches a leaf. There is nothing impossible about writing such code, and it has probably been done many times.
It appears to me that the reason that "might_halt()" causes this approach to fail is, simply, that the generated tree would be infinitely large due to recursion. The real-world result being that the "halts()" function itself would actually never halt. The branch tree would go on forever, like so:
root -> might_halt() -> halts() -> might_halt() -> halts() -> ...
I don't see that there's any need to call this a "paradox." I could write you such a function, and you could run it with your clever "might_halt()" function as the input, and the fabric of space-time would not be torn apart. The program would just crash when it ran out of memory building the branch tree. In fact, it would fail in this way for ANY input program that includes recursion, because recursion (without a terminating condition) is just an infinitely long chain of function calls.
So, would it be fair to say that the halting problem is only undecidable when recursion is allowed? Is it theoretically possible to write a "halts()" function that works on all non-recursive programs?
There are two possible reasonable meanings of "recursive" here.
One is the programmer's notion of recursive where a routine calls itself directly or indirectly. For that the answer is "no", because such recursion can always be replaced by loops and some more explicit representation of the call stack one would have had with recursive calls. Consider that all recursive routines are executed by very non-recursive hardware, and consider that most loops can be easily rewritten as recursion.
The other meaning is the the logical self-reference, in that might_halt() gives as argument to halts() a copy of its own code, which includes halts() (or a call to it). I'm not sure what the theoretical situation is when this recursion is forbidden. But, still regarding the theoretical, it is difficult to forbid recursion, for in order to determine whether an argument to halts() is forbidden or not one would need to prove whether it is /equivalent/ to recursive code.
On the more practical side, consider a program to solve, by exhaustive search, some great so far unsolved mathematical problem, that is, the program is to prove whether the answer to some very hard question is "yes" or "no".
Proving whether that program halts amounts to solving the mathematical problem, which might be impossible, and at any rate not something one should expect even in a lifetime of computation.
Going a little further out on a limb, it seems that even most recursive programs could be handled. The halts() function could just detect the case where the same function is a parent of itself (even though there might be many nodes between the two occurrences of itself). I'm not sure what it would do to resolve the situation, but often, somewhere in that chain, there is a condition for the recursion to terminate.
Could we then further conclude that the halting problem is only undecidable for SOME recursive programs, and even for these programs, the condition of undecidability can at least be detected?
Most of these impossibility arguments depend on a restriction on the kinds of answers the entity can give.
For example:
"This sentence is one the poster called 'none' never says."
If 'none' proceeds to say that sentence, then it's a lie, and so 'none' has uttered a lie, he's produced an untrue sentence. But if he does not ever say it, then it's true. So if 'none' is restricted to only utter true sentences then we have just proved that there is at least one true sentence that he/she cannot ever produce -- and one must therefore assume, cannot even grok the truth of, while we in the audience can trivially see that it's true. Hence, 'none' must, at the very least, be incomplete. :-)
But in reality, what's proven is just that with a restriction on what he/she can say, 'none' is restricted in what he/she can say. That's sort of a tautology. The practical significance is just that restrictions can restrict a little more than one intuitively expects, for example, inability to utter sentence above.
And what Turing proved that way was that with a restriction to truthful yes/no, does it halt or not, the halts() routine is restricted so much that it cannot truthfully answer all questions put to it, and so must refuse to answer at all. For example, it cannot say "dunno", or "meaningless". And what that means in practice is that it's not a good idea to design halts() with all those restrictions in place, that the perfect so restricted halts() does not exist.
Cheers & hth.,
- Alf
--
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! :-) Just going there is good. Linking
to it is even better! Thanks in advance!
.
- References:
- Halting Problem
- From: none
- Halting Problem
- Prev by Date: Re: Halting Problem
- Next by Date: Re: Halting Problem
- Previous by thread: Re: Halting Problem
- Next by thread: Re: Halting Problem
- Index(es):
Relevant Pages
|
