Chaos in Cellular Automata

How does chaos show up in cellular automata? The onset of chaos in maps discovered by Lorentz can be explained taking in account the fact that mathematical real numbers that only would permit a perfect measurement don't exist:for this reason, in those phenomena that show a chaotic attractor, the only thing that we can predict is that the system at time t will be somewhere inside the attractor . The only way to know where this point will be is to wait and see what happens. No computer however big and powerful can predict where this point will be. Note that this seems to happen not only in the real world where time, space and measures are continuous and so represented by infinite real numbers, but also in maps where time is discrete.

What happens if we simplify everything to the bare minimum: let's say our universe is a linear string of cells. Time is discrete. The measurement of each cell can produce only two values: black and white or 1 and 0.Each cell can interact only with its left and right neighbor. To make things simple , the initial condition is that all cells are 0 but one in the "center" which is 1.

Let's now pose some questions: how many cellular automata like these we have? The value of cell i at time t can be computed by knowing the values of cells i-1,i and i+1 at time t-1. These values form a 3 digit binary number : so we have exactly 8 possible cases: 000,001,...,111.
For each of these combinations the result can be 0 or 1. So we have 256 possible Cellular Automata from CA 00000000, to CA 11111111 or using decimal notation from rule 0 to rule 255. We can study these one by one by doing a simulation . Right? Well, the things turn out to be more complex than we thought.

Apparently here there are no real numbers and so no infinities. But think again: we have a problem at the borders.If we want to do a simulation we have to use a string of cells of finite size (we don't have an infinite computer) and to decide what happens at the borders.

So,let's say we have n cells.We can assume that cell 0 and cell n+1 have always value 0 or viceversa that cell 0 coincides with cell n and cell n+1 with 0 (as if the cells are connected at the border forming a circle). If we do this simulation the result is very predictable:with n cells , at most after n steps, the string of cells will have again the same values and repeat the same loop.

In fact the interesting things come out if we assume that the number of cells is infinite.The result can be seen here. You must imagine each picture to continue at the bottom with the same pattern. Some pattern are pretty obvious:the value 1 will move on the right, the cells become all 1, etc. In all these cases we can easily give a formula that computes the configuration after n steps without knowing the intermediate pattern.

What is instead amazing , is what happens with some rules like rule 30: apparently there is no way to compute the configuration after n steps unless you know the configuration n-1.Another way to put it, is to say that the state of the central cell generates a random sequence of binary digits. We can consider rule 30 like a very simplified model of nature.It starts from a single point (the bing bang) with very simple rules and then chaos develops.

In this rule the state of a single cell after n steps, depends from the state of all the 2n cells nearby that can communicate with this single cell in this span of time.If nature is like this , there is no possible way to know the future not only because we are not able to measure each single state with infinite precision, but also because we need to know the state of all the parts of the universe.


BACK to Fractals,chaos,symmetry,physical laws and computer programs
Maintained by Giuseppe Zito:Giuseppe.Zito@cern.ch: last update