Elemental Cellular Automaton Rule 54

 

Rule 54, in Wolfram's notations, is one of elementary yet complexly behaving one-dimensional cellular automata. The automaton support gliders, glider guns and other non-trivial long transients, therefore possess a rich and complex dynamics.







Rule 54 belongs to a class of complex CA rules - Rule 54 is an example of Wolfram's class IV - which includes the Game of Life and related rules. These CA produce gliders in their evolution, and thus pose a fruitful subject of investigations not only in terms of complex systems and self-organization but also as novel substrate for dynamics non-classical computation.


Following, Wolfram notation - a one-dimensional elementary CA has two parameters (k,r), number of states k and cell neighborhood radius r - Rule 54 is a CA with parameters (2,1), i.e. two cell-states and three cell neighborhood (a central cell, its left and right neighbors). The local transition function f is determinate as follows: 111 -> 0, 110 -> 0, 101 -> 1, 100 -> 1, 011 -> 0, 010 -> 1, 001 -> 1 and 000 -> 0. Thus the binary sequence 00110110 in decimal notation represents the evolution rule 54.


Also remembering that elementary rules fall into 88 equivalence classes (see Wuensche’s equivalence classes [Wuensche & Lesser, 1992]). Rule 54 is one of 2 equivalent rules: 54 and 147 (reflection).



Figure 1. Equivalent rules with Rule 54. All snapshots start with the same random initial conditions with a density of 50%. (a) ECA rule 54 and (b) ECA Rule 147 respectively.


In their pioneer work Boccara, Nasser and Roger [Boccara et al., 1991] produce a list of gliders known at that time, and discuss existence of glider gun; they also applied some statistical analysis to analyzing stability of gliders. Later Hanson and Crutchfield [Hanson & Crutchfield, 1997] introduced a concept of “computational mechanics” - applied finite state machine language representation in studying defect dynamics in 1D CA, and in deriving motion equations of filtered gliders. More studies were undertaken by Wolfram [Wolfram, 1994 & 2002], who exhibit glider collisions with long period of after-development and several filters for detecting gliders and defects, and Martin [Martin, 2000], who designed an algebraic group of order four to represent collisions between basic gliders.


Our contribution takes some directions: design a single filter to detect all gliders, discover novel glider guns, demonstrate that all gliders in Rule 54 CA can be produced via collisions of gliders, and produce a catalog of all outcomes of all possible collisions between two and three gliders. We also apply these findings to construct  dynamical logical gates, where Boolean values are represented by the gliders [Martínez et al., 2006 & 2012].


Finally, we propose a representation for coding initial conditions by means of a finite subset of regular expressions [Martínez et al., 2014]. The sequences are extracted both from de Bruijn diagrams and tiles specifying a set of phases fi for each glider in Rule 54. The subset of regular expressions is explained and given in detail (see regular language in Rule 54 section).


Some researches lines in Rule 54.


  1. a)Gliders in Rule 54

  2. b)Regular language in Rule 54

  3. c)Tiles in Rule 54

  4. d)Solitons in Rule 54

  5. e)Collisions of gliders

  6. f)Logic gates in Rule 54


Figure OSXLCAU21 system coding gliders by regular expressions in Rule 54.


References related to CA Rule 54


  1. (1)N. Boccara, J. Nasser and M. Roger, Particle like structures and their interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules, Physical Review A 44(2), 866-875, 1991.

  2. (2)Junbiao Guan, Complex Dynamics of the Elementary Cellular Automaton Rule 54, International Journal of Modern Physcis C 23(7), 1250052, 2012.

  3. (3)James E. Hanson and James P. Crutchfield, Computacional Mechanics of Cellular Automata: An Example, Physics D 103(1-4), 169-189, 1997.

  4. (4)Genaro J. Martínez, Andrew Adamatzky, Fangyue Chen and Leon Chua, On soliton collisions between localizations in complex ECA: Rules 54 and 110 and beyond, Complex Systems 21(2), 117-142, 2012.

  5. (5)Genaro J. Martínez, Andrew Adamatzky and Harold V. McIntosh, Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates, Chaos, Fractals and Solitons 28, 100-111, 2006. (alternative version available from http://uncomp.uwe.ac.uk/genaro/Papers/Papers_on_CA.html)

  6. (6)Genaro J. Martínez, Andrew Adamatzky, and Harold V. McIntosh, Complete Characterization of Structure of Rule 54, Complex Systems 23(3), 259-293, 2014.

  7. (7)Genaro J. Martínez, Harold V. McIntosh and Andrew Adamatzky, On the representation of gliders in Rule 54 by de Bruijn and cycle diagrams, Lecture Notes in Computer Science 5191, 83-91, 2008.

  8. (8)Genaro J. Martínez, Juan C. Seck Tuoh Mora, Hector Zenil, Computation and Universality: Class IV versus Class III Cellular Automata, Journal of Cellular Automata 7(5-6), 393-430, 2013.

  9. (9)Bruno Martin, A Group Interpretation of Particles Generated by One-Dimensional Cellular Automaton, Wolfram's Rule 54, Int. J. of Modern Physics C 11(1), 101-123, 2000.

  10. (10)Markus Redeker, Gliders and ether in Rule 54, arXiv:1007.2920v1 [nlin.CG], http://arxiv.org/abs/1007.2920, 2010.

  11. (11)Stephen Wolfram, Cellular Automata and Complexity: collected papers, Addison-Wesley Publishing Company, 1994.

  12. (12)Stephen Wolfram, A New Kind of Science, Wolfram Media, Inc., Champaign, Illinois, 2002.

  13. (13)Andrew Wuensche and Mike Lesser, The Global Dynamics of Cellular Automata, Santa Fe Studies in the Complexity, Addison-Wesley, 1992.

  14. (14)Andrew Wuensche, Classifying Cellular Automata, Complexity 4, 47-66, 1999.

  15. (15)MathWorld - Rule 54, http://mathworld.wolfram.com/Rule54.html.

  16. (16)Wolfram Atlas - Rule 54, http://atlas.wolfram.com/01/01/54/.