Notes

Chapter 7: Mechanisms in Programs and Nature

Section 7: Origins of Discreteness


1D [discrete] transitions [in cellular automata]

There are no examples of the phenomenon shown here among the 256 rules with two possible colors and depending only on nearest neighbors. Among the 4,294,967,296 rules that depend on next-nearest neighbors, there are a handful of examples, including rules with numbers 4196304428, 4262364716, 4268278316 and 4266296876. The behavior obtained with the first of these rules is shown below. An example that depends on three neighbors on each side was discovered by Peter Gacs, Georgii Kurdyumov and Leonid Levin in 1978, following work on how reliable electronic circuits can be built from unreliable components by Andrei Toom:

{a1_, a2_, a3_, a4_, a5_, a6_, a7_} -> If[ If[a4 == 1, a1 + a3 + a4, a4 + a5 + a7] >= 2, 1, 0]

The 4-color rule shown in the text is probably the clearest example available in one dimension. It has rule number 294869764523995749814890097794812493824.


From Stephen Wolfram: A New Kind of Science [citation]