On Fri, 15 Dec 2000, John K Clark wrote:
> James Rogers <jamesr@best.com> Wrote:
>
> > More precisely, you can calculate the limits of predictability for finite
> > state machines, given any certain amount of memory to work with. All
> > finite state machines are predictable,
>
> No. If I start a finite Turing machine with a tape of X boxes running the
> program I mentioned before nobody knows of a shortcut to predict if it
> will stop before it reaches X or not, and it's possible nobody ever will know
> because such a shortcut (a proof) does not exist for this problem and never will.
> You can't even assign probabilities as to what the likely outcome will be, we're
> totally clueless as to its behavior. The only way to know what this Turing machine
> will do is to set it in motion and watch, sort of like people.
You mostly missed the point. What I was talking about is irrelevant to
the final state of the Turing machine. What I was stating was that for
any finite state machine, even very complex ones, it is possible to both
predict the next operation of the machine and be able to calculate the
error rate for such a prediction in a relatively small amount of memory.
So while I may not know how a finite-state machine will terminate, I can
always give a relatively precise answer as to what it will do *next*. And
for many classes of problems, this is good enough.
In fact, this is arguably more useful in many ways. Outside of idle
curiousity, I am more concerned with what happens in the universe (or
stock market) next than I am with how the universe will finally end. Given
that this is provably possible for any finite state machine (and relatively
trivial to implement in practice), I prefer this approach to the provable
difficulty of what you are talking about above. :^)
As an interesting aside, the same areas of mathematics would also suggest
that an accurate predictor of the universe itself could be developed with
realistically accessible levels of computer technology i.e. almost
certainly possible within the next hundred years. At this point
we are more missing the data than the computational ability, though
non-trivial in either case.
-James Rogers
jamesr@best.com
This archive was generated by hypermail 2b30 : Mon May 28 2001 - 09:50:37 MDT