2010-09-20

Determinism != Predictability

Many people assumed that if a system is deterministic, it should be predictable. Chaos and complexity each show different situations where this fails to hold.

In deterministic chaos, even when you know precisely the "laws" of a system, its extreme sensitivity to initial conditions (formally described with positive Lyapunov exponents) implies that sooner or later, very similar initial states will tend to very different states, since trajectories diverge exponentially. OK, some people may argue that if we had infinite precision, then we could predict precisely the future, so it is just a practical nuisance that in theory should work (I have no idea how, but anyway... people are stubborn (not me! I am just self-confident!)).

But you cannot get away with lack of predictability that is inherent of complexity. Within a complex system, yes even with deterministic rules, interactions between components generate novel information that determines the future of the system. This information is not included in the initial nor boundary conditions. Since you do not know how the system will interact, the only way to know the future state of a system is by "running it". Of course, a posteriori you can make predictions. This is known as "computational irreducibility": you know the "laws" of a system, but you need to compute the trajectory of an initial state before you can know what will be a future state. This is also related to the halting problem. Just an example:
ECA rule 110 is very simple to describe. However, you cannot deduce a priori all the different dynamic structures (aka gliders) that emerge from the interactions. Moreover, you cannot infer from the rules of the ECA the result of the glider interactions. You need to compute them and see. Even more, there is no chance you could prove from the rules of the ECA that it is capable of universal computation. Same arguments apply for the Game of Life.


Post a Comment