Registered: Oct 2008
Posts: 4

How do I prove that the Class 3 of cellular automata of one dimension is chaotic?

__________________
Gledson Melotti

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

There are different understandings of the term "chaotic", but one version is sensitive to perturbations in the initial conditions. Strictly speaking, the mathematical definition of continuous-function chaos refers to exponentially divergent paths in phase space. Just sticking with the simpler "sensitive to initials" idea, one can explore the sensitivity of a class 3 rule to its initials by comparing the evolution from 2 different initial conditions that differ only at a single cell.

An easy way to explore that is to look at difference patterns. A difference pattern tracks the changes between 2 CA evolutions. In the simplest case of 2 color CAs run for the same length of time from the same size initial condition, you can get those by subtracting one array from the other element by element, and then adding 1, and then showing the result with ArrayPlot. This will leave gray any cell that is the same in the two evolutions, while cells that are different will show up as white (if a previous black becomes white after the change) or black (if a previous white becomes black).

Here is an example. First we make two initial conditions that differ only at a single cell -
init = RandomInteger[1, 49];
init2 = ReplacePart[init, {24} -> Mod[init[[25]] + 1, 2]];

then this will plot the difference pattern -
ArrayPlot[
 1 + CellularAutomaton[146, init, 20] - 
  CellularAutomaton[146, init2, 20]]


It is characteristic of class 3 rules that the effect of a single bit-flip in the initial condition tends to spread across the entire pattern. Occasionally you may get no change at all - you've hit a "don't care" bit in the initial condition, we say. But usually, a pattern of disturbance is created that grows with time, that can look as random and irregular as any original evolution. We say, the impact of a perturbation of the initial condition is unbounded and apparently unpredictable (even though it is a deterministic process) - which is one of the characteristics of classical chaos.

I hope this helps.

Report this post to a moderator | IP: Logged