Cellular automaton: Encyclopedia II - Cellular automaton - The simplest cellular automata

Cellular automaton - The simplest cellular automata

The simplest nontrivial CA would be one-dimensional, with two possible states per cell, and a cell's neighbors defined to be the adjacent cells on either side of it. A cell and its two neighbors form a neighborhood of 3 cells, so there are 2³=8 possible patterns for a neighborhood. There are then 2⁸=256 possible rules. These 256 CAs are generally referred to using a standard naming convention invented by Wolfram. The name of a CA is the decimal number which, in binary, gives the rule table, with the eight possible neighborhoods listed in reverse counting order. For example, below are tables defining the "rule 30 CA" and the "rule 110 CA" (in binary, 30 and 110 are written 11110 and 1101110, respectively) and graphical representations of them starting from a 1 in the center of each image:

Rule 110 cellular automaton

A table completely defines a CA rule. For example, the rule 30 table says that if three adjacent cells in the CA currently have the pattern 100 (left cell is on, middle and right cells are off), then the middle cell will become 1 (on) on the next time step. The rule 110 CA says the opposite for that particular case.

A number of papers have analyzed and compared these 256 CAs. The rule 30 and rule 110 CAs are particularly interesting.

Rule 30 generates apparent randomness despite the lack of anything that could reasonably be considered random input. Wolfram proposed using its center column as a pseudorandom number generator (PRNG); despite occasional claims to the contrary, it passes every standard test for randomness, and Wolfram uses this rule in the Mathematica product for creating random integers. (In particular, in the 1990s a cryptography survey book claimed that rule 30 was equivalent to a linear feedback shift register (LFSR), but in fact the claim was about rule 90.) Although Rule 30 produces randomness on many input patterns, there are also an infinite number of input patterns that result in repeating patterns. The trivial example of such a pattern is the input pattern only consisting of zeros. A less trivial example, found by Matthew Cook, is any input pattern consisting of infinite repetitions of the pattern '00001000111000', with repetitions optionally being separated by six ones.

Rule 110, like the Game of Life, exhibits what Wolfram calls class 4 behavior, which is neither completely random nor completely repetitive. Localized structures appear and interact in various complicated-looking ways. In the course of the development of A New Kind of Science, Cook proved in 1994 that these structures were rich enough to support universality. This result is interesting because rule 110 is an extremely simple one-dimensional system, and one which is difficult to engineer to perform specific behavior. This result therefore provides significant support for Wolfram's view that class 4 systems are inherently likely to be universal. Cook presented his proof at a Santa Fe Institute conference on Cellular Automata in 1998, but Wolfram blocked the proof from being included in the conference proceedings, as Wolfram did not want the proof to be published before the publication of A New Kind of Science. In 2004, Cook's proof was finally published in Wolfram's journal Complex Systems (Vol. 15, No. 1), over ten years after Cook came up with it.

Adapted from the Wikipedia article "The simplest cellular automata", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki