Re: Halting Problem
- From: Ben Bacarisse <ben.usenet@xxxxxxxxx>
- Date: Wed, 01 Apr 2009 13:43:34 +0100
none <none@xxxxxxxxx> writes:
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.
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.
To be a little more precise, the existence of a terminating "halts"
function leads to a contradiction. This matters to logicians -- a
paradox is an amusing curiosity, whereas Turing's theorem says that a
system that can compute "enough" will be inherently incomplete.
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."
No, indeed, there is not. This argument just shows that the poor
soul's plan failed to produce a terminating "halts" function for this
case. He or she could try again with a more subtle plan, but the
halting theorem say that that plan will fail too.
There is, in a very formal sense, two collections of ever better
versions of "halts". There is a collection that always terminates,
the two simplest being the function that returns 0 and the one that
return 1 (for all inputs). A better function is one that gets the
right answer for more functions. There is another collection that
always gets the right answer but might not terminate. The simplest
being "while(1);". One way to look at Turing's theorem is that
neither of these collections ("chains" would be a better term) have a
least upper bound. The limit of both is the desired "halts" function,
but neither can be written using the formalism of a Turing machine (or
anything that is essentially the same).
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.
Yes, but that is not the claim! The claims is simply that the
function can't be written (as a Turning machine or in pseudo-C or
whatever).
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?
No. Turing machines are not recursive and there is no halting test
for these either. There are lots of non-recursive formalisms for what
it means "to compute" and for all of them that are really useful (i.e.
which can compute everything that the others can) Turing's theorem
holds.
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.
Yes, "many" programs could be handled. In fact, there is no upper
bound on the number of programs that can be handled. No matter how
good a "halts" function you write, I can write a better one (and so
on).
Could we then further conclude that the halting problem is only
undecidable for SOME recursive programs,
Yes.
and even for these programs,
the condition of undecidability can at least be detected?
Well, in some sense yes, but not in a very useful way. The program
would have to simply say "this program is not one of the ones I can
decide".
--
Ben.
.
- References:
- Halting Problem
- From: none
- Halting Problem
- Prev by Date: Re: Parsing a config file
- Next by Date: Re: Halting Problem
- Previous by thread: Re: Halting Problem
- Next by thread: Re: Halting Problem
- Index(es):
Relevant Pages
|
