Re: "movb" for spin-unlock (was Re: namei() query)

From: Kai Henningsen (
Date: Tue Apr 25 2000 - 02:39:00 EST (Oliver Xymoron) wrote on 24.04.00 in <>:

> On Mon, 24 Apr 2000, Kai Henningsen wrote:
> > (Oliver Xymoron) wrote on 24.04.00 in
> > <>:
> >
> > > 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

MfG Kai

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

This archive was generated by hypermail 2b29 : Sun Apr 30 2000 - 21:00:09 EST