Rule 30 is an

elementary cellular automaton In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends o ...

introduced by

Stephen Wolfram Stephen Wolfram (; born 29 August 1959) is a British-American computer scientist, physicist, and businessman. He is known for his work in computer science, mathematics, and theoretical physics. In 2012, he was named a fellow of the American Ma ...

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

chaotic Chaotic was originally a Danish trading card game. It expanded to an online game in America which then became a television program based on the game. The program was able to be seen on 4Kids TV (Fox affiliates, nationwide), Jetix, The CW4Kid ...

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'', the textile cone or 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. Textile cone snails live mostly in the Indian Ocean, alon ...

''. Rule 30 has also been used as a

random number generator Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular out ...

Mathematica Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimizat ...

, and has also been proposed as a possible

stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...

for use in

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

. Rule 30 is so named because 30 is the smallest

Wolfram code Wolfram code is a widely used numbering system for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper and popularized in his book ''A New Kind of Science''. The code is based on the observation that a table spec ...

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: The corresponding formula is eft_cell XOR (central_cell OR right_cell) It is called Rule 30 because in

binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that t ...

, ''00011110₂'' = 30. 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. Cellular Automata running Wolfram-rule-30

Cellular Automata running Wolfram-rule-30

Structure and properties

The following pattern emerges from an initial state in which 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, ... and is approximately

n

Chaos

Wolfram based his classification of Rule 30 as chaotic based primarily on its visual appearance, and it was later shown to meet more rigorous definitions of chaos proposed by

Devaney Devaney, Devany, and O'Devaney, is a surname derived from the Irish ''Ó/Mac Duibheamhna'', meaning "descendants/son of Dubheamhna". They are cited by O'Dugan as being chiefs of Kinelawley in the over-kingdom of Ulaid, now known as Clanawley in p ...

and Knudson. In particular, according to Devaney's criteria, Rule 30 displays sensitive dependence on initial conditions (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 on the space of configurations (there is a periodic configuration with any finite pattern of cells), and it is mixing (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 .

Applications

Random number generation

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 A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...

(PRNG); it passes many standard tests for randomness, and Wolfram previously used this rule in the Mathematica product for creating random integers. Sipper and Tomassini have shown that as a random number generator Rule 30 exhibits poor behavior on a

chi squared test A chi-squared test (also chi-square or test) is a statistical hypothesis test used in the analysis of contingency tables when the sample sizes are large. In simpler terms, this test is primarily used to examine whether two categorical variables ...

when applied to all the rule columns as compared to other cellular automaton-based generators. The authors also expressed their concern that "The relatively low results obtained by the rule 30 CA may be due to the fact that we considered N random sequences generated in parallel, rather than the single one considered by Wolfram."

Decoration

The

Cambridge North railway station Cambridge North railway station is a railway station located in the Cambridge suburb of Chesterton, close to Cambridge Science Park. The station is on the Fen Line, which runs from Cambridge to King's Lynn. It connects to the Cambridgeshire ...

is decorated with architectural panels displaying the evolution of Rule 30 (or equivalently under black-white reversal, Rule 135). The design was described by its architect as inspired by

Conway's Game of Life The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further ...

, a different cellular automaton studied by Cambridge mathematician

John Horton Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...

, but is not actually based on Life.

Programming

The state update can be done quickly by

bitwise operation In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...

s, if the cell values are represented by the bits within one (or more) computer words. Here shown in

C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...

: #include #include int main() This program produces the following output:

................................O...............................
...............................OOO..............................
..............................OO..O.............................
.............................OO.OOOO............................
............................OO..O...O...........................
...........................OO.OOOO.OOO..........................
..........................OO..O....O..O.........................
.........................OO.OOOO..OOOOOO........................
........................OO..O...OOO.....O.......................
.......................OO.OOOO.OO..O...OOO......................
......................OO..O....O.OOOO.OO..O.....................
.....................OO.OOOO..OO.O....O.OOOO....................
....................OO..O...OOO..OO..OO.O...O...................
...................OO.OOOO.OO..OOO.OOO..OO.OOO..................
..................OO..O....O.OOO...O..OOO..O..O.................
.................OO.OOOO..OO.O..O.OOOOO..OOOOOOO................
................OO..O...OOO..OOOO.O....OOO......O...............
...............OO.OOOO.OO..OOO....OO..OO..O....OOO..............
..............OO..O....O.OOO..O..OO.OOO.OOOO..OO..O.............
.............OO.OOOO..OO.O..OOOOOO..O...O...OOO.OOOO............
............OO..O...OOO..OOOO.....OOOO.OOO.OO...O...O...........
...........OO.OOOO.OO..OOO...O...OO....O...O.O.OOO.OOO..........
..........OO..O....O.OOO..O.OOO.OO.O..OOO.OO.O.O...O..O.........
.........OO.OOOO..OO.O..OOO.O...O..OOOO...O..O.OO.OOOOOO........
........OO..O...OOO..OOOO...OO.OOOOO...O.OOOOO.O..O.....O.......
.......OO.OOOO.OO..OOO...O.OO..O....O.OO.O.....OOOOO...OOO......
......OO..O....O.OOO..O.OO.O.OOOO..OO.O..OO...OO....O.OO..O.....
.....OO.OOOO..OO.O..OOO.O..O.O...OOO..OOOO.O.OO.O..OO.O.OOOO....
....OO..O...OOO..OOOO...OOOO.OO.OO..OOO....O.O..OOOO..O.O...O...
...OO.OOOO.OO..OOO...O.OO....O..O.OOO..O..OO.OOOO...OOO.OO.OOO..
..OO..O....O.OOO..O.OO.O.O..OOOOO.O..OOOOOO..O...O.OO...O..O..O.
.OO.OOOO..OO.O..OOO.O..O.OOOO.....OOOO.....OOOO.OO.O.O.OOOOOOOOO

References

* Wolfram, Stephen, 1985,
Cryptography with Cellular Automata
', CRYPTO'85.

External links

* *
Rule 30 in Wolfram's atlas of cellular automata
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. Archived from th

on 2013-08-08

Basic introduction to the pattern of Rule 30 from the perspective of a LOGO software expert Olivier Schmidt-Chevalier.

Stephen Wolfram speaks about computing a theory of everything where he talks about rule 30 among other things. {{DEFAULTSORT:Rule 030 Cellular automaton rules 1983 introductions Wolfram code