Rule 30

The snail shells of the Weber cone have the pattern of rule 30.

Rule 30 ( English Rule 30 ) is a one-dimensional cellular automaton , which was discovered in 1983 by Stephen Wolfram . The rule defines how the state of a particular cell changes in a one-dimensional grid (black or white). If many versions of the rule are drawn below one another, a typical two-dimensional pattern is created for the rule (see figure below) . According to Wolfram's classification scheme , this cellular automaton belongs to "class 3", which means that it shows non-periodic, chaotic behavior.

description

Rule 30 is of particular interest because it creates complex, seemingly random structures that have clear local regularities. It is precisely these structures that the snail shells of the Weber cone , a species of sea snail, have. With the rule, a random number generator was also developed for Mathematica and a stream cipher was proposed for encrypting information . However, it has been shown that other cellular automata are better suited for encryption.

definition

The elementary cellular automata, primarily examined by Stephen Wolfram, consist of an infinitely long, one-dimensional grid of cells. These cells can assume state 0 (white) or 1 (black). At the beginning the configuration of the cells is determined, e.g. B. a single black cell. In each subsequent time step, a rule is applied to the individual cells that determines whether the cell is black or white in the next step. The next state in each case depends on the cell itself and on its left and right neighboring cells. A rule must therefore define possible cell combinations, e.g. B. 010 (the cell is black, left and right neighbors are white): ${\ displaystyle 2 ^ {3} = 8}$

Current status of the left neighbor, cell and right neighbor	111	110	101	100	011	010	001	000
New state of the cell under consideration	0	0	0	1	1	1	1	0

Any state 0 or 1 can be assigned to each of the eight options (000 to 111). Overall, therefore, there are elementary cellular automata. They are named according to the scheme established by Wolfram by reading the eight states written next to one another as a binary number, e.g. B. 00011110, the corresponding decimal number gives the name of the elementary automaton (in this case 30). ${\ displaystyle 2 ^ {8} = 256}$

Their mirror image, complement and complementary mirror image are rules 86 (01010110), 135 (10000111) and 149 (10010101).

The following diagram shows the sequential execution of the rule, with only one cell initially colored black and all others colored white. The vertical axis describes the time and each horizontal line shows the state of the cells at a certain time step.

Execution of rule 30 one after the other, the time steps run vertically.

Properties of the pattern

After calculating a large number of steps, the typical pattern results.

Two structures in particular can be seen: the frequent occurrence of white triangles and the regular striped pattern on the left. The number of black cells at a certain point in time describes the sequence ${\ displaystyle n}$

{\ displaystyle 1,3,3,6,4,9,5,12,7,12,11,14,12,19,13,22,15,19}

(Sequence sequence A070952 in OEIS )

and is about the same . ${\ displaystyle n}$

chaos

Rule 30 not only seems chaotic for optical reasons, it also fulfills the mathematical conditions for chaos :

It is highly sensitive to the initial values. This means that two slightly different initial configurations develop (diverge) apart very quickly.
All periodic configurations together are a dense subset of the set of all configurations.
It is topologically transitive on the set of all configurations (it mixes up the configurations).

Web links

Commons : Rule 30 - Collection of Pictures, Videos and Audio Files

Eric W. Weisstein : Rule 30 . In: MathWorld (English).
Rule 30 in Wolfram's Atlas of Cellular Automata (English)

Individual evidence

↑ Stephen Coombes: The Geometry and Pigmentation of Seashells (PDF; 3.3 MB) In: maths.nottingham.ac.uk . University of Nottingham . February 2009. Retrieved April 10, 2013.
↑ Stephen Wolfram: Statistical mechanics of cellular automata . In: Rev. Mod. Phys. . 55, No. 3, 1983, pp. 601-644. bibcode : 1983RvMP ... 55..601W . doi : 10.1103 / RevModPhys.55.601 .
↑ Random Number Generation . In: Wolfram Mathematica 8 Documentation . Retrieved December 31, 2011.
↑ Stephen Wolfram: Cryptography with cellular automata . In: Proceedings of Advances in Cryptology - CRYPTO '85 . Lecture Notes in Computer Science 218, Springer-Verlag, p. 429. doi : 10.1007 / 3-540-39799-X_32
^ Willi Meier, Othmar Staffelbach: Analysis of pseudo random sequences generated by cellular automata . In: Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91 . Lecture Notes in Computer Science 547, Springer-Verlag, p. 186. doi : 10.1007 / 3-540-46416-6_17

[1] Stephen Coombes: The Geometry and Pigmentation of Seashells (PDF; 3.3 MB) In: maths.nottingham.ac.uk . University of Nottingham . February 2009. Retrieved April 10, 2013.

[2] Stephen Wolfram: Statistical mechanics of cellular automata . In: Rev. Mod. Phys. . 55, No. 3, 1983, pp. 601-644. bibcode : 1983RvMP ... 55..601W . doi : 10.1103 / RevModPhys.55.601 .

[3] Random Number Generation . In: Wolfram Mathematica 8 Documentation . Retrieved December 31, 2011.

[4] Stephen Wolfram: Cryptography with cellular automata . In: Proceedings of Advances in Cryptology - CRYPTO '85 . Lecture Notes in Computer Science 218, Springer-Verlag, p. 429. doi : 10.1007 / 3-540-39799-X_32

[5] Willi Meier, Othmar Staffelbach: Analysis of pseudo random sequences generated by cellular automata . In: Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91 . Lecture Notes in Computer Science 547, Springer-Verlag, p. 186. doi : 10.1007 / 3-540-46416-6_17