oxymoron@waste.org (Oliver Xymoron) wrote on 24.04.00 in <Pine.LNX.4.10.10004242148010.12350-100000@waste.org>:
> 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?
If that was your point, you nicely managed to completely obscure it: you
actually seemed to say the opposite.
> > 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.
Umm, "exponential time" *is* equivalent to "quickly becomes infeasible" in
my book. There's stuff which becomes infeasible quicker, but not all that
much. Hey, we're bitching over algorithms with cubic or even quadratic
time!
MfG Kai
-
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:09 EST