Rule 30
From Wikipedia, the free encyclopedia
Rule 30 is an elementary cellular automaton rule introduced by Stephen Wolfram in 1983. Wolfram describes it as being his "all-time favourite rule"[1] 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, seemly 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, such as pigmentation on seashells[2]. Rule 30 is named due to its binary representation, 00011110, which describes its rule set (as described below).
Contents |
[edit] Rule Set
In all of Wolfram's elementary cellular automata, an infinite array of cellular automata with only two states is considered, with each automata in some initial state. At discrete time intervals, every automata spontaneously changes state based on the 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 |
Rule 30 is the mirror image, complement, and mirror complement of rules 86, 135, and 149, respectively.
[edit] Structure and Properties
For the initial state of one black cell, the following pattern emerges:
Rule 30 cellular automaton
Here, the vertical axis represents time and the horizontal axis represents a cross-section of the array of automata. Several motifs are present in this structure, such as the frequent appearance of white triangles and a well-defined pattern on the left side; however the structure as a whole has no discernable pattern. The number of black cells at generation n is given by the sequence A070952 in the OEIS and is approximately n.[3]
Below is a scaled-down version of Rule 30 with the initial condition of a single black cell over 2000 generations.
Rule 30, 2000 generations (scaled down)
Below is Rule 30 for a random initial condition over 500 generations.
Rule 30, random initial condition
[edit] Implications and Applications
Due to the simplicity of their rules and the complexity of their results, Wolfram believes that cellular automata contain the key to unraveling the mysteries of the universe. He advocates the use of algorithms and computation, rather than mathematical equations in attempting to explain natural phenomena and sciences ranging from quantum physics to evolution, although this idea has been criticized by some as being over-reaching and an act of hubris.[4]
One example of this can be seen in the patterns of certain seashells, such as the ones in Conus and Cymbiola genus. Each pigment cell residing along the shell's lip receives certain activating and inhibiting pigments from its neighbours, and in turn may secrete certain pigments to its neighbors. In this way, every cell acts as a cellular automata. A pattern resembling Rule 30 appears on the shell of the widespread species Conus textile.
In terms of direct applicability, Wolfram asserts that the center column of Rule 30 has an application as a random number generator. Despite occasional claims to the contrary, this has passed every test of randomness and indeed is used as a pseudorandom number generator in Wolfram's flagship program, Mathematica. Rule 30 has also been proposed as a possible stream cipher for use in cryptography.[5]
WolframTones uses cellular automata, including Rule 30, to create unique sounds which can be used as alerts or ringtones.
[edit] See Also
[edit] External Links
Repeating Rule 30 patterns A page detailing repeating sequences when the initial condition is a single black cell.
