Rule 30

This article is about the cellular automaton. For the United States federal court rule, see Federal Rules of Civil Procedure and deposition (law).
A Conus textile shell similar in appearance to Rule 30.[1]

Rule 30 is an elementary cellular automaton introduced by Stephen Wolfram in 1983.[2] 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 Mathematica,[3] and has also been proposed as a possible stream cipher for use in cryptography.[4][5]

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.

  1. ^ Stephen Coombes (February 2009). "The Geometry and Pigmentation of Seashells" (PDF). www.maths.nottingham.ac.uk. University of Nottingham. Retrieved 2013-04-10.
  2. ^ 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.
  3. ^ "Random Number Generation". Wolfram Mathematica 8 Documentation. Retrieved 31 December 2011.
  4. ^ 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.
  5. ^ 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.