Rule 30


Rule 30

Rule 30 is a one-dimensional binary cellular automaton rule introduced by Stephen Wolfram in 1983. [cite journal|author = Wolfram, S.|title = Statistical mechanics of cellular automata|journal = Rev. Mod. Phys.|volume = 55|pages = 601–644|year = 1983|doi = 10.1103/RevModPhys.55.601] Wolfram describes it as being his "all-time favourite rule" [ [http://www.stephenwolfram.com/publications/talks/ycombinatorschool/ On Starting a Long-Term Company] , S. Wolfram, 2005.] 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, 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". Rule 30 has also been used as a random number generator in Wolfram's program Mathematica, [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: cite journal|author=Sipper, Moshe; Tomassini, Marco|title=Generating parallel random number generators by cellular programming|journal=International Journal of Modern Physics C|volume=7|issue=2|pages=181–190|year=1996|doi=10.1142/S012918319600017X] and has also been proposed as a possible stream cipher for use in cryptography. [cite conference|author=Wolfram, S.|title=Cryptography with cellular automata|date=1985|booktitle=Proceedings of Advances in Cryptology - CRYPTO '85|pages=429|publisher=Lecture Notes in Computer Science 218, Springer-Verlag|url=http://www.springerlink.com/content/6lc1m67ec2ek0nk3/ See also cite conference|author=Meier, Willi; Staffelbach, Othmar|title=Analysis of pseudo random sequences generated by cellular automata|booktitle=Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91|date=1991|pages=186|publisher=Lecture Notes in Computer Science 547, Springer-Verlag|url=http://www.springerlink.com/content/8cwan65384nphd0u/]

Rule 30 is so named because 30 is the smallest Wolfram code 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 automata is:

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".

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 n is given by the sequence:1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... OEIS|id=A070952and is approximately n.

Additional images of Rule 30 are available: .

External links

* [http://psoup.math.wisc.edu/archive/recipe32.html Rule 30: Wolfram's Pseudo-random Bit Generator] . Recipe 32 at David Griffeath's Primordial Soup Kitchen.
*MathWorld | title = Rule 30 | urlname = Rule30
* [http://www.iwriteiam.nl/Rule30.html 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.
* [http://olivier.sc.free.fr/logosc/cubisme/pavages.html Paving Mosaic Fractal] . Basic introduction to the pattern of Rule 30 from the perspective of a LOGO software expert Olivier Schmidt-Chevalier.

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • rule — 1 n 1 a: a prescribed guide for conduct or action b: a regulating principle or precept 2 a: an order or directive issued by a court in a particular proceeding esp. upon petition of a party to the proceeding that commands an officer or party to… …   Law dictionary

  • Rule — Rule, n. [OE. reule, riule, OF. riule, reule, F. r[ e]gle, fr. L. regula a ruler, rule, model, fr. regere, rectum, to lead straight, to direct. See {Right}, a., and cf. {Regular}.] 1. That which is prescribed or laid down as a guide for conduct… …   The Collaborative International Dictionary of English

  • rule — ► NOUN 1) a regulation or principle governing conduct or procedure within a particular sphere. 2) control or government: British rule. 3) a code of practice and discipline for a religious community. 4) (the rule) the normal or customary state of… …   English terms dictionary

  • Rule — Rule, n. [Webster 1913 Suppl.] Syn: regulation; law; precept; maxim; guide; canon; order; method; direction; control; government; sway; empire. [1913 Webster] Rule Rule, v. t. [imp. & p. p. {Ruled}; p. pr. & vb. n. {Ruling}.] [Cf. OF. riuler,… …   The Collaborative International Dictionary of English

  • Rule 55 — was an operating rule adopted by railway companies in the British Isles in the late 19th century. It was introduced following a spate of accidents caused by signalmen forgetting that trains were standing on the line, sometimes within sight of… …   Wikipedia

  • Rule 3:36 — Saltar a navegación, búsqueda Rule 3:36 Álbum de Ja Rule Lanzado el 10 de octubre de 2000 Grabado: 2000 Género Rap Duración: 57 mi …   Wikipedia Español

  • rule — [ro͞ol] n. [ME reule < OFr rieule < L regula, ruler, straightedge < regere, to lead straight, rule: see RIGHT] 1. a) an authoritative regulation for action, conduct, method, procedure, arrangement, etc. [the rules of the school] b) an… …   English World dictionary

  • Rule — Rule, v. i. 1. To have power or command; to exercise supreme authority; often followed by over. [1913 Webster] By me princes rule, and nobles. Prov. viii. 16. [1913 Webster] We subdue and rule over all other creatures. Ray. [1913 Webster] 2.… …   The Collaborative International Dictionary of English

  • Rule — bezeichnet folgende Personen: Ja Rule (* 1976), US amerikanischer Rapper Jane Rule (1931–2007), kanadische Autorin Orte: Rule (Arkansas), Ort im Carroll County, Arkansas, USA Rule (Texas), Ort im Haskell County, Texas, USA Begriffe: Der englische …   Deutsch Wikipedia

  • Rule 6 — was the most infamous and well known of a set of behavior rules imposed on participants at the 1991 San Jose, California Timecon science fiction convention by the hosting hotel (then a Red Lion Inn [ [http://redlion.rdln.com/ Red Lion Inns] ] ).… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.