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.
>
> http://cis.csuohio.edu/~somos/beaver.ps
Nice.
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 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:07 EST