Coarse-Graining of Elementary Cellular Automata

The following applet demonstrates the coarse-graining of elementary Cellular-Automata (CA). A coarse-grained version of a CA is another CA which is capable of emulating the large scale behavior of the original one without accounting for all the small scale details. Coarse-graining is very important in the modeling of complex systems because it allows an efficient modeling through a reduction in the number of degrees of freedom. For more information see Computational irreducibility and the predictability of complex physical systems, Navot Israeli and Nigel Goldenfeld, Phys. Rev. Lett. 92, 074105 (2004).

To operate the applet:

1. Choose an origin rule. The numbers in parentheses are the 0<->1, left<->right, and 0<->1 + left<->right symmetries of the rule.

2. Press "run" to explore the rule behavior.  You can control the correlations in the initial random state by using the "correlation" scrollbar.

3. Choose either coarse-grain to binary CA or multi colored CA, choose a supercell size and press "coarse-grain". The "to binary" option tries to find a coarse-grained CA within the elementary rule family. It checks all possible projections from the supercell to the binary alphabet. The "to multi colored" tries to find a multi colored coarse-grained version by repeatedly attempting to project a pair of supercell states onto one coarse-grained state.    

4. The possible coarse-grained CA and projection operators found by the program will be displayed in the "possible transitions" and "possible projections" menus on the right. Choose a CA rule in the transition menu and then a projection. Try a larger supercell size if there are no results. Elementary rules are denoted by their rule number. A projection to the binary alphabet is denoted by a single number - the value of the n'th bit in the binary representation of this number is the projection of the n'th-1 supercell value. In case of multi colored coarse-grained CA the only information that will be displayed is the number of states in the coarse-grained CA.

5. Press "run" again to see how the coarse-grained CA captures the coarse scale behavior of the original rule. The coarse-grained CA is run with the coarse-grained initial condition from the original rule.

6. Interesting rules to look at: 18,22,26,54,57,73,110,126,146,184. Rules 30,45,106,154 and their symmetries cannot be coarse-grained by this program.

7. The supercell size is limited to 4 in the "to binary" option and 7 in the "to multi colored" option in order to avoid excessive usage of memory and cpu time. With these limits, the program uses around 8Mb of memory and shuld finish within several seconds.