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

From: Jamie Lokier (
Date: Tue Apr 25 2000 - 14:06:01 EST

Oliver Xymoron wrote:
> > > 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.
> My point in the previous post was that it's much worse than exponential
> (which you might try to tackle for problems as large as 100 or 1000,
> given a small exponent). The complexity grows faster than any computable
> function of n.

Real computers can't run those programs. They require an amount of RAM
which grows as fast as any computable function of n...

This restriction of real computers bounds the time required to prove
things about them.

Until you add network protocols, at which point you may have the vast
memory again. Assuming you have nigh-on infinity computers in your cluster.

-- Jamie

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:10 EST