Problem 10

What is the correspondence between cellular automata and stochastic systems?

Cellular automata satisfy deterministic rules. But their initial states can have a random form. And the patterns they generate can have many of the properties of statistical randomness. As a consequence, the behaviour of cellular automata may have a close correspondence with the behaviour of systems usually described by basic rules that involve noise or probabilities. So for example domain walls in cellular automata execute essentially random walks, even though the evolution of the cellular automaton as a whole is entirely deterministic. Similarly, one can construct a cellular automaton that mimics say an Ising spin system with a fixed total energy (microcanonical ensemble) [32]. Apparently random behaviour occurs as a consequence of randomly-chosen initial conditions, just as in many systems governed by the deterministic laws of classical physics.

Even models that involve explicit randomness are in practice simulated in computer experiments using pseudorandom sequences generated by some definite algorithm. These sequences are not unlike the sequences of site values produced by many cellular automata. In fact, the linear feedback shift registers often used in practice to produce pseudorandom sequences are exactly equivalent to certain additive cellular automata (cf. [33]). Empirical evidence suggests that the properties of many supposedly stochastic models are quite insensitive to the detailed form of the randomness used in their simulation. It should be possible to find entirely deterministic forms for such models, based say on cellular automata. One expects in general that just as with algorithms say for primality testing the fundamental capabilities of stochastic and deterministic models should be equivalent.

previous  l  next