Halting Problem

Hi all,

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.

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?

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

Relevant Pages

  • Re: Halting Problem
    ... Suppose I write a function that solves the halting problem for all ... program that includes my "halts" function: ... the condition of undecidability can at least be detected? ... mandelbrot set computing. ...
    (comp.programming)
  • Re: Halting Problem
    ... If halts() returns true on line 7, then might_haltwould jump into the infinite loop on line 9. ... 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. ... would it be fair to say that the halting problem is only undecidable when recursion is allowed? ... 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? ...
    (comp.programming)
  • Re: Halting Problem
    ... If halts() returns true on line 7, ... large due to recursion. ... would it be fair to say that the halting problem is only undecidable ... the condition of undecidability can at least be detected? ...
    (comp.programming)
  • Re: Halting problem undecidable or semidecidable?
    ... > this is a semi-decidable problem? ... > run the program and wait until it halts. ... the complement of the halting problem cannot be recursive! ... languages and also recursively-enumerable sets with undecidability. ...
    (comp.theory)
  • Re: Partial recursive functions and minimization
    ... algorithm specific to T which can decide if T halts on x - but the ... Suppose that T is a Turing Machine. ... for which the halting problem is decidable) G is recursive. ... theorem of recursion theory that F partial recusive implies G (*as ...
    (sci.math)