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

From: Oliver Xymoron (
Date: Mon Apr 24 2000 - 21:56:10 EST

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?

> 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

 "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 Please read the FAQ at

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