Rule 30

From Wikipedia, the free encyclopedia

Rule 30 is a one-dimensional binary cellular automaton rule introduced by Stephen Wolfram in 1983.^[1] Wolfram describes it as being his "all-time favourite rule"^[2] and details it in his book, A New Kind of Science. Using Wolfram's classification scheme, Rule 30 is a Class III rule, displaying aperiodic, chaotic behaviour.

This rule is of particular interest because it produces complex, seemingly-random patterns from simple, well-defined rules. Because of this, Wolfram believes that rule 30, and cellular automata in general, are the key to understanding how simple rules produce complex structures and behaviour in nature. For instance, a pattern resembling Rule 30 appears on the shell of the widespread cone snail species conus textile. Rule 30 has also been used as a random number generator in Wolfram's program Mathematica,^[3] and has also been proposed as a possible stream cipher for use in cryptography.^[4]

Rule 30 is so named because 30 is the smallest Wolfram code which describes its rule set (as described below). The mirror image, complement, and mirror complement of Rule 30 have Wolfram codes 86, 135, and 149, respectively.

Contents 1 Rule Set 2 Structure and Properties 3 External links 4 References

[edit] Rule Set

In all of Wolfram's elementary cellular automata, an infinite one-dimensional array of cellular automaton cells with only two states is considered, with each cell in some initial state. At discrete time intervals, every cell spontaneously changes state based on its current state and the state of its two neighbors. For Rule 30, the rule set which governs the next state of the automata is:

current pattern	111	110	101	100	011	010	001	000
new state for center cell	0	0	0	1	1	1	1	0

[edit] Structure and Properties

The following pattern emerges from an initial state in a single cell with state 1 (shown as black) is surrounded by cells with state 0 (white).

Rule 30 cellular automaton

Here, the vertical axis represents time and any horizontal cross-section of the image represents the state of all the cells in the array at a specific point in the pattern's evolution. Several motifs are present in this structure, such as the frequent appearance of white triangles and a well-defined striped pattern on the left side; however the structure as a whole has no discernible pattern. The number of black cells at generation n is given by the sequence

1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... (sequence A070952 in OEIS)

and is approximately n.

Additional images of Rule 30 are available: the same initial state over 2000 generations and 500 generations of a random initial configuration.

[edit] External links

• Rule 30: Wolfram's Pseudo-random Bit Generator. Recipe 32 at David Griffeath's Primordial Soup Kitchen.
• Eric W. Weisstein, Rule 30 at MathWorld.
• Repeating Rule 30 patterns. A list of patterns that, when repeated to fill the cells of a Rule 30 automaton, repeat themselves after finitely many time steps. Frans Faase, 2003.
• Paving Mosaic Fractal. Basic introduction to the pattern of Rule 30 from the perspective of a LOGO software expert Olivier Schmidt-Chevalier.

[edit] References