Re: Halting Problem

none <none@xxxxxxxxx> writes:
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?


It seems to me that you are confusing several levels, several
different problems.


In the physical universe, all the programs running on physical
computers will terminate. When the computer decays and breaks, or
eventually, when the universe dies, sometimes between 15e9 and 200e9
years. So: halts(x)=true, for any program x.



Now, even if you assume infinite time and wearless computers, our
computers are not Turing Machines: they don't have infinite memory.
Therefore the number of state in which one of our computer can be is
finite (it's big, but finite). In consequences, there is a trivial
algorithm for halt(x), since the only way for a program x not to
terminate within a finite memory is to have a cycle in its states, you
can execute the program x step by step, memorizing the program state
at each step, and checking for states already run by. Either the
program x terminates in which case halts(x) returns true, or it
produces a state it has already produced (meaning it loops, therefore
will never terminate), and halts(x) may then return false.

So for real programs running on real computers, without external
input, there is a trivial halts(x) algorithm that runs in O(2^M)
steps, M being the size of the state memory in bits, and with a space
complexity of O(2^(M+1)).

That said, 2^M is soon bigger than the estimated lifespan of the
universe, and 2^(M+1) is bigger than the number of particules in the
universe, so you really want to find a better algorithm for halts(x).

200e9 years are about 6.2E24 microseconds,
and M = ceiling(log2(6.2E24)) = 83

As soon as the state of your program is more than _83_ _bits_, in the
worst case, it takes more than the age of the universe to determine if
it terminates, if you can run one step each microsecond, in the worst
case.



But mathematicians and theorical computer scientists like to have even
stronger results, using an infinite memory size, and applying their
theorems to any program. In this case, the undecidably of the halting
problem is correct. In this context, we definitely want to apply
halts(halts), and unfortunately this leads to a dead end.


But let's come back to our concrete programs. You may indeed remove
the paradox by considering only the program written "so far" instead
of considering all the programs, when implementing your halts
algorithm. All programs without any loop, or with predefined finite
loops, terminate trivially (predefined finite loops can be unrolled,
so there's no actual loop). Recursion is equivalent to iteration.

What we can say, is that it is trivial to write a predicate unloopy(x)
indicating that a program x contains no indefinite loop or recursion.

unloopy(x) ==> halts(x).

This is basically what you are talking about.

Do you know a lot of interesting programs without a loop?

So the only interesting part of halts(x) is exactly when there are
indefinite loops/recursions. And the problems occur even before
applying halts to paradoxical programs. Take for example this simple
function:

hotpo(n) = if odd(n) then 3*n+1 else n/2 end

and consider this program:

hotpoto(n):
while n>1 do
n := hotpo(n)
done

halts(hotpoto) ?



So you have to determine from what point of view you want to work. As
a mathematician working with Turing Machines, you've got the
undecidability of the halting problem.

Working on concrete machines, there's a halts algorithm, unfortunately
it's too slow and greedy for the lifespan and resources of this
universe for anything but the most trivial programs.


Working on concrete machines, with a practical approach, you can
forget about algorithms, and try _heuristics_ instead. It is also
helpful to implement algorithms characterizing less strongly our
programs, such as unloopy. You may implement a program Halts__Maybe
that may indicate whether a program terminates or not, or that may
fail to give a response in a given time. This is not shameful, notice
that even the smartest mathematician cannot determine whether a
program will halt or not, in general. If your program can give better
answers than the better programmer or mathematician most of the time,
you win. Even if your program gave wrong answers, not too often,
you'd win! as long it it wouldn't give wrong answer more often than
the worse programmer.


--
__Pascal Bourguignon__
.

Relevant Pages

  • Re: StackOverflowException with attribute
    ... I figured that the recursion wasn't infinite. ... it would seem that the call to GetProperties on the ... You need to find some way to break this loop. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: while (1) vs. for ( ;; )
    ... >> Why not code it like you would read it in English: ... > glance that the loop is an infinite one; ... > represents a condition that will become true when the loop is meant to ... That program WILL terminate sometime. ...
    (comp.lang.c)
  • Re: A hairy loop
    ... Can you tell me why the loop below doesn't terminate? ... Yes, I know, this is procedural thinking, LISP already has a MOD, etc. ... There is merit in learning how recursion is powerful enough to ...
    (comp.lang.functional)
  • Re: A hairy loop
    ... Can you tell me why the loop below doesn't terminate? ... Yes, I know, this is procedural thinking, LISP already has a MOD, etc. ... There is merit in learning how recursion is powerful enough to ...
    (comp.lang.functional)
  • Re: interesting question
    ... infinite, and would run on existing PCs with 8 GBytes of RAM. ... Didn't Dykstra or Hoare prove that any recursion can be performed more ... efficiently with a loop? ... -- Charlie Springer ...
    (comp.lang.forth)