On Mon, 24 Apr 2000, Kai Henningsen wrote:
> oxymoron@waste.org (Oliver Xymoron) wrote on 24.04.00 in <Pine.LNX.4.10.10004240820290.1607-100000@waste.org>:
>
> > Waiting for exit is a runtime check for halt by definition and is O(1).
>
> Sure, but it's *NOT* a solution to the halting problem.
>
> It doesn't prove that the program halts for any input other than the one
> given, and it cannot ever prove that the program does not halt. (Only that
> it does not halt in X time.)
Which is my point. Or did you not read the text you quoted?
> The situations it can prove, you can obviouysly also prove by simulation.
> But with simulation, you can actually (try to) prove it for whole classes
> of input, by following the decision paths "in parallel" (thus, exponential
> time). That's actually more powerful than real runtime checks.
Except simulation _very_ quickly becomes infeasible. But don't take my
word for it - try simulating the possible branches of an arbitrary
Turing machine with just 4 states. With binary input and a blank tape
even.
-- "Love the dolphins," she advised him. "Write by W.A.S.T.E.."- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sun Apr 30 2000 - 21:00:08 EST