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

From: Jamie Lokier (
Date: Mon Apr 24 2000 - 07:03:29 EST

Oliver Xymoron wrote:
> > > It's provably equivalent to the halting problem, assuming you even
> > > have enough info in the source to automatically identify things
> > > that need atomicity. Anything with recursion or coroutines is
> > > liable to make it very unhappy.
> > >
> > > That said, quite a bit can be done with runtime checks ala the spinlock
> > > debugging code that can't be done by static analysis.
> >
> > Everything that can be found using runtime tests can be found
> > statically in at most exponential time, except network protocols :-)
> Huh. So you can test for halt at runtime with atexit(), right?

Everything you can test at runtime, yes. By simulation, and considering
all possible digital inputs as you go. (Hence exponential time).

That's not a complete proof -- and so does not solve the halting
problem. Neither does any runtime check.

> So you can now solve the halting problem statically? Bzzt. It's more
> subtle than that.

It is.

> Considering that an n-state Turing machine can be coded in about n-squared
> lines of switch statement (or an n-squared array declaration), it becomes
> clear that even very simple programs can have incomprehensibly complex
> behavior.


I stand by my point that those aren't in the realm of runtime checks
though :-)

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