Rule 30 is a one-dimensional binary cellular automaton

Cellular automaton

A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...

 rule introduced by Stephen Wolfram

Stephen Wolfram

Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...

 in 1983. Wolfram describes it as being his "all-time favourite rule" and details it in his book, A New Kind of Science

A New Kind of Science

A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...

. Using Wolfram's classification scheme, Rule 30 is a Class III rule, displaying aperiodic, chaotic

Chaos theory

Chaos theory is a field of study in mathematics, with applications in several disciplines including physics, economics, biology, and philosophy. Chaos theory studies the behavior of dynamical systems that are highly sensitive to initial conditions, an effect which is popularly referred to as the...

 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

Conus textile

Conus textile, common name the cloth of gold cone is a venomous species of sea snail, a marine gastropod mollusk in the family Conidae, the cone snails, cone shells or cones. The species is extremely dangerous to humans.-Distribution:C...

. Rule 30 has also been used as a random number generator in Wolfram's program Mathematica

Mathematica

Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...

, and has also been proposed as a possible stream cipher

Stream cipher

In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...

 for use in cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

. However, Sipper and Tomassini have shown that as a random number generator rule 30 exhibits poor behavior on a chi squared test compared to other cellular automaton based generators.

Rule 30 is so named because 30 is the smallest Wolfram code

Wolfram code

Wolfram code is a naming system often used for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper and used in his book A New Kind of Science....

 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.

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 automaton is:

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

The following diagram shows the pattern created, with cells colored based on the previous state of their neighborhood. Darker colors represent "1" and lighter colors represent "0". Time increases down the vertical axis.

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 is given by the sequence

1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ...

and is approximately .

As is apparent from the image above, rule 30 generates seeming randomness despite the lack of anything that could reasonably be considered random input. Stephen Wolfram proposed using its center column as a pseudorandom number generator

Pseudorandom number generator

A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...

 (PRNG); it passes many standard tests for randomness, and Wolfram uses this rule in the Mathematica product for creating random integers. 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

Matthew Cook

Matthew Cook is a mathematician and computer scientist who proved Stephen Wolfram's conjecture that the Rule 110 cellular automaton is Turing-complete. Rule 110 is arguably the simplest Turing-complete system currently known....

, is any input pattern consisting of infinite repetitions of the pattern '00001000111000', with repetitions optionally being separated by six ones. Many more such patterns were found by Frans Faase. See Repeating Rule 30 patterns.

Chaos

Wolfram based his classification of Rule 30 as chaotic based primarily on its visual appearance, but it was later shown to meet more rigorous definitions of chaos proposed by Devaney and Knudson. In particular, according to Devaney's criteria, Rule 30 displays sensitive dependence on initial conditions

Butterfly effect

In chaos theory, the butterfly effect is the sensitive dependence on initial conditions; where a small change at one place in a nonlinear system can result in large differences to a later state...

 (two initial configurations that differ only in a small number of cells rapidly diverge), its periodic configurations are dense in the space of all configurations, according to the Cantor topology

Cantor space

In mathematics, a Cantor space, named for Georg Cantor, is a topological abstraction of the classical Cantor set: a topological space is a Cantor space if it is homeomorphic to the Cantor set. In set theory, the topological space 2ω is called "the" Cantor space...

 on the space of configurations (there is a periodic configuration with any finite pattern of cells), and it is mixing

Mixing (mathematics)

In mathematics, mixing is an abstract concept originating from physics: the attempt to describe the irreversible thermodynamic process of mixing in the everyday world: mixing paint, mixing drinks, etc....

 (for any two finite patterns of cells, there is a configuration containing one pattern that eventually leads to a configuration containing the other pattern). According to Knudson's criteria, it displays sensitive dependence and there is a dense orbit (an initial configuration that eventually displays any finite pattern of cells). Both of these characterizations of the rule's chaotic behavior follow from a simpler and easy to verify property of Rule 30: it is left permutative, meaning that if two configurations and differ in the state of a single cell at position , then after a single step the new configurations will differ at cell .

External links

• Rule 30: Wolfram's Pseudo-random Bit Generator. Recipe 32 at David Griffeath's Primordial Soup Kitchen.
• 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.
• TED Talk from February 2010. Stephen Wolfram speaks about computing a theory of everything where he talks about rule 30 among other things.