Rule 30
Rule 30is anelementary cellular automatonintroduced byStephen Wolframin 1983.[2]UsingWolfram's classification scheme,Rule 30 is a Class III rule, displaying aperiodic,chaoticbehaviour.
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 speciesConus textile.Rule 30 has also been used as arandom number generatorinMathematica,[3]and has also been proposed as a possiblestream cipherfor use incryptography.[4][5]
Rule 30 is so named because 30 is the smallestWolfram codewhich 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
[edit]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 |
If the left, center, and right cells are denoted(p,q,r)then the corresponding formula for the next state of the center cell can be expressed asp xor (q or r).It is called Rule 30 because inbinary,000111102= 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.
Structure and properties
[edit]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 generationis given by the sequence
and is approximately.[citation needed]
Chaos
[edit]Rule 30 meets rigorous definitions of chaos proposed byDevaneyand Knudson. In particular, according to Devaney's criteria, Rule 30 displayssensitive 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 theCantor topologyon the space of configurations (there is a periodic configuration with any finite pattern of cells), and it ismixing(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 isleft permutative,meaning that if two configurationsCandDdiffer in the state of a single cell at positioni,then after a single step the new configurations will differ at celli+ 1.[6]
Applications
[edit]Random number generation
[edit]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 apseudorandom number generator(PRNG); it passes many standard tests for randomness, and Wolfram previously used this rule in the Mathematica product for creating random integers.[7]
Sipper and Tomassini have shown that as a random number generator Rule 30 exhibits poor behavior on achi squared testwhen applied to all the rule columns as compared to other cellular automaton-based generators.[8]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."[9]
Decoration
[edit]
TheCambridge North railway stationis decorated with architectural panels displaying the evolution of Rule 30 (or equivalently under black-white reversal, Rule 135).[10]The design was described by its architect as inspired byConway's Game of Life,a different cellular automaton studied by Cambridge mathematicianJohn Horton Conway,but is not actually based on Life.[11][12]
Programming
[edit]The state update can be done quickly bybitwise operations,if the cell values are represented by the bits within one (or more) computer words. Here shown inC++:
#include<stdint.h>
#include<iostream>
intmain(){
uint64_tstate=1u<<31;
for(inti=0;i<32;++i){
for(intj=64;j--;){
std::cout<<char(state>>j&1?'O':'.');
}
std::cout<<'\n';
state=(state>>1)^(state|state<<1);
}
}
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
See also
[edit]References
[edit]- ^Stephen Coombes (February 2009)."The Geometry and Pigmentation of Seashells"(PDF).www.maths.nottingham.ac.uk.University of Nottingham.Retrieved2013-04-10.
- ^Wolfram, S. (1983). "Statistical mechanics of cellular automata".Rev. Mod. Phys.55(3): 601–644.Bibcode:1983RvMP...55..601W.doi:10.1103/RevModPhys.55.601.
- ^"Random Number Generation".Wolfram Mathematica 8 Documentation.Retrieved31 December2011.
- ^Wolfram, S. (1985). "Cryptography with cellular automata".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.
- ^Meier, Willi; Staffelbach, Othmar (1991). "Analysis of pseudo random sequences generated by cellular automata".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.
- ^Cattaneo, Gianpiero; Finelli, Michele; Margara, Luciano (2000). "Investigating topological chaos by elementary cellular automata dynamics".Theoretical Computer Science.244(1–2): 219–241.doi:10.1016/S0304-3975(98)00345-4.MR1774395.
- ^Lex Fridman (2018-03-02),MIT AGI: Computational Universe (Stephen Wolfram),archivedfrom the original on 2021-12-19,retrieved2018-03-07
- ^Sipper, Moshe; Tomassini, Marco (1996). "Generating parallel random number generators by cellular programming".International Journal of Modern Physics C.7(2): 181–190.Bibcode:1996IJMPC...7..181S.doi:10.1142/S012918319600017X.
- ^Page 6 ofSipper, Moshe; Tomassini, Marco (1996). "Generating parallel random number generators by cellular programming".International Journal of Modern Physics C.7(2): 181–190.Bibcode:1996IJMPC...7..181S.doi:10.1142/S012918319600017X.
- ^Wolfram, Stephen (June 1, 2017),"Oh My Gosh, It's Covered in Rule 30s!",Stephen Wolfram's blog
- ^Lawson-Perfect, Christian (May 23, 2017),"Right answer for the wrong reason: cellular automaton on the new Cambridge North station",The Aperiodical
- ^Purtill, Corinne."A UK train station's tribute to a famous mathematician got everything right except his math".Quartz.Retrieved2017-06-12.
- Wolfram, Stephen, 1985,Cryptography with Cellular Automata,CRYPTO'85.
External links
[edit]
- Weisstein, Eric W."Rule 30".MathWorld.
- "Announcing the Rule 30 Prizes".Stephen Wolfram Writings.1 October 2019.
- Rule 30 in Wolfram's atlas of cellular automata
- Rule 30: Wolfram's Pseudo-random Bit Generator.Recipe 32 atDavid 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 theOriginalon 2013-08-08
- 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.