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