Elemental Cellular Automaton Rule 110

 

The existence of several periodic structures (known as gliders) in the evolution space of the one-dimensional cellular automaton Rule 110, has important lines of investigation in cellular automata theory such as: complex behaviour, universal computation and self-reproduction. The one-dimensional binary cellular automaton numbered Rule 110 in Stephen Wolfram’s system of identification has been an object of special attention due to the structures or gliders which have been observed in evolution samples from random initial conditions. It has even been suggested that Rule 110 belongs to the exceptional class IV of automata whose chaotic aspects are mixed with regular behaviours; but in this case the background where the chaotic behaviour occurs is textured rather than quiescent, a tacit assumption in the original classification.







Whatever the merits of this classification, Rule 110 was awarded its own appendix (Table 15) in reference [Wolfram 94]. It contains specimens of evolution including a list of thirteen gliders compiled by Doug Lind and also presents the conjecture that the rule could be universal.


There is little published literature about Rule 110; an example is a statistical study [Li & Nordahl 92] done by Wentian Li and Mats Nordahl around 1992. This paper studies the transitional role of Rule 110 and its relation with class IV rules sitting between Wolfram’s classes II and III. This study would seem to be reflected in an approach to equilibrium statistics, via a power law rather than exponentially.


Matthew Cook wrote an eight page introduction [Cook 99] listing gliders from A through H and a glider gun. The list of Cook shows new gliders which do not appear in the list of Lind, gliders with rare extensions and a pair of gliders of complicated construction. In that document Cook makes a comparison between Rule 110 and Life, finding some similarities and suggesting that Rule 110 may be called LeftLife.


Harold V. McIntosh raises the question where Rule 110 is a problem to cover the evolution space with triangles of different sizes [McIntosh 99 & 00]. The appearance of these triangles suggests the analysis of the plane generated by the evolution of Rule 110 as a two dimensional shift of finite type.


The most important result both in the study of Rule 110 and in cellular automata theory in the last twenty years, is well represented by the demonstration made by Cook that Rule 110 is universal. The demonstration is realized simulating a novel cyclic tag system (CTS) [Cook 04] and [Wolfram 02]; with well-defined blocks of gliders by means of collisions. The simulation in the evolution space of Rule 110 is really complicated and several details must be taken into account to have a good construction as can be seen in [Martínez et. al 11] and [McIntosh 02] (also see here universality in Rule 110 section).


Gliders in the CTS are useful to represent process collision-based computing. In the model of Conway, universality is demonstrated simulating a register machine through logic gates, constructing the system with gliders and glider guns. At the present time Paul Rendell has implemented a complicated universal Turing machine in Life.


The relevance of the demonstration realized by Cook is to reduce the neighbourhood, state set and dimensionality to the possible minimum. Then we can say that Cook has the last reduction with the simplest cellular automaton able to produce universal computation.


Rule 110 is a one-dimensional cellular automaton with two states and a linear three cells neighbourhood. The transition function simultaneously evaluates a central cell with regard to its left and right neighbours.


Thus number 110 talks about the decimal notation of the evolution rule which is the binary sequence 01110110. The automaton is defined by a finite one-dimensional array where each one of its elements takes the value 0 or 1 from the state set, this array represents the initial configuration of the system. A neighbourhood is formed by three cells, a central element,a neighbour to the right and another into the left. Depending on the values in cells of the neighbourhood, a new value is defined for the central cell in the next generation.


The transition function evaluates synchronously each neighbourhood to calculate the new configuration. Thus the transition function transforms the neighbourhoods 001, 010, 011, 101 and 011 into state 1 and the neighbourhoods 000, 100 and 111 into state 0.


Also remembering that elementary rules fall into 88 equivalence classes (see Wuensche’s equivalence classes [Wuensche & Lesser 92]). Rule 110 is one of 4 equivalent rules: 193 (complement), 124 (comp. negative), 137 (comp. reflection) and 110 (comp. negative reflection).


Figure 1. Equivalent rules with Rule 110. All snapshots start with equivalent random initial conditions. (a) ECA rule 193, (b) ECA Rule 124, (c) ECA Rule 137, and (d) ECA Rule 110 respectively. (Figures courtesy from Andy Wuensche, DDLab, July 2010, [32]).


In this time, some researches have finished important and related works around of the universality in Rule 110. In the case of CTS there are some solved problems like a Fibonnaci sequence done by Chapman (January 2003). On the other hand, Neary and Woods in [Neary & Woods 06] shown that Cook’s machine can run in polynomial time. Morita in [Morita 06] proofs how implement an explicit halt condition in CTS and how a partitioned CA may simulate any CTS.


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


Some researches lines about Rule 110.


  1. a)Gliders in Rule 110

  2. b)Regular language in Rule 110

  3. c)Tiles in Rule 110

  4. d)Universality in Rule 110 and CTS (caution size pictures is 1.2MB approximately everyone)

  5. e)Solitons in Rule 110

  6. f)Collisions of gliders


Figure 2. OSXLCAU21 system coding gliders by regular expressions in Rule 110.


References related to CA Rule 110


  1. (1)Matthew Cook, Introduction to the activity of rule 110 (copyright 1994-1998 Matthew Cook), http://w3.datanet.hu/~cook/Workshop/CellAut/Elementary/Rule110/110pics.html, January 1999.

  2. (2)Matthew Cook, Universality in Elementary Cellular Automata, Complex Systems 15(1), 1-40, 2004. PDF from http://www.complex-systems.com/abstracts/v15_i01_a01.html.

  3. (3)Matthew Cook, A Concrete View of Rule 110 Computation, In The Complexity of Simple Programs, T. Neary, D.Woods, A.K. Seda and N. Murphy (Eds.), 31-55, 2008. (alternative version from arXiv at http://arxiv.org/abs/0906.3248)

  4. (4)Creative Commons, A Bunch of Rocks, http://xkcd.com/505/

  5. (5)Fangyue Chen, Weifeng Jin, Guanrong Chen and Lin Chen, Chaos emerged on the `edge of chaos,’ International Journal of Computer Mathematics 89(12), 1584-1595, 2012.

  6. (6)Wim Hordijk, Cosma R. Shalizi and James P. Crutchfield, Upper Bound on the Products of Particle Interactions in Cellular Automata, Physica D 154, 240-258, 2001.

  7. (7)Takahiro Ito, Abstract collision systems on G-sets, Journal of Math-for-Industry 2 (A-6), 57-73, 2010. (PDF avalibale from http://gcoe-mi.jp/english/publish_list/pub_inner/id:4/cid:14)

  8. (8)Genaro J. Martínez, Solitones en el autómata celular unidimensional regla 110, https://www.comunidad.escom.ipn.mx/genaro/Papers/Papers_on_CA_files/solitones-110.html, 2002.

  9. (9)Genaro J. Martínez, Introduction to Rule 110, Conference Presented in Rule 110 Winter Workshop, https://www.comunidad.escom.ipn.mx/genaro/Papers/Papers_on_CA.html, Bielefeld, Germany, March 2004.

  10. (10)Genaro J. Martínez, Andrew Adamatzky, Christopher R. Stephens and Alejandro F. Hoeflich, Cellular automaton supercolliders, International Journal of Modern Physics C 22(4), 419-439, 2011. Alternative version from http://eprints.uwe.ac.uk/14487/

  11. (11)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.

  12. (12)Genaro J. Martínez and Harold V. McIntosh, ATLAS: Collisions of gliders like phases of ether in Rule 110, https://www.comunidad.escom.ipn.mx/genaro/Papers/Papers_on_CA.html, August 2001.

  13. (13)Genaro J. Martínez, Harold V. McIntosh and Juan C. Seck-Tuoh-Mora, Production of gliders by collisions in Rule 110, Lecture Notes in Computer Science 2801, 175-182, 2003.

  14. (14)Genaro J. Martínez, Harold V. McIntosh and Juan C. Seck-Tuoh-Mora, Gliders in Rule 110, International Journal of Unconventional Computing 2(1), 1-49, January 2006.

  15. (15)Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck Tuoh Mora and Sergio V. Chapa Vergara, Rule 110 objects and other constructions based-collisions, Journal of Cellular Automata 2(3), 219-242, 2007.

  16. (16)Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora and Sergio V. Chapa Vergara, Determining a regular language by glider-based structures called phases fi_1 in Rule 110, Journal of Cellular Automata 3(3), 231-270, 2008. (alternative version from arXiv at http://arxiv.org/abs/0706.3348)

  17. (17)Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora and Sergio V. Chapa Vergara, A note about the regular language of Rule 110 and its general machine: the scalar subset diagram, Japan Society for Artificial Intelligence C3004, 39-49, Yokohama, Japan, 2008. (alternative version from https://www.comunidad.escom.ipn.mx/genaro/Papers/Papers_on_CA.html)

  18. (18)Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora and Sergio V. Chapa Vergara, Reproducing the cyclic tag systems developed by Matthew Cook with Rule 110 using the phases fi_1, Journal of Cellular Automata 6(2-3), 121-161, 2011, (alternative available from https://www.comunidad.escom.ipn.mx/genaro/Papers/Papers_on_CA.html)

  19. (19)Wentian Li and Mats G. Nordahl, Transient behavior of cellular automaton rule 110, Physics Letters A 166, 335-339, 1992.

  20. (20)Harold V. McIntosh, Rule 110 as it relates to the presence of gliders, http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html, January 1999.

  21. (21)Harold V. McIntosh, A Concordance for Rule 110, http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html, 2000.

  22. (22)Harold V. McIntosh, Rule 110 Is Universal! A Gamin's Guide To Goldbergean Gadgeteering, http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html, June 30, 2002.

  23. (23)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.

  24. (24)Kenichi Morita, Simple Universal One-Dimensional Reversible Cellular Automata, Journal of Cellular Automata 2, 159-166, 2006.

  25. (25)蜷川繁, 万能セルオートマトンルール 110 における 1/f ゆらぎ, 金沢工業大学工学部情報工学科, The 20th Annual Conference of the Japanese Society for Artificial Intelligence, 2006.

  26. Shigeru Ninagawa, 1/f Noise in Universal Cellular Automaton Rule 110, Lecture Notes in Computer Science 4135, 207-218, 2006.

  27. (26)Shigeru Ninagawaa and Genaro J. Martínez, Compression-Based Analysis of Cyclic Tag System Emulated by Rule 110, Journal of Cellular Automata 9(1), 23-35, 2014.

  28. (27)西尾, 英之助; ヴォルシュ, トーマス, セルオートマトンの近傍系関数 : 近傍系を変える(代数、形式言語、計算システム理論とその応用), 数理解析研究所講究録 1562, 46-55, 2007.

  29. Hidenosuke Nishio and Thomas Worsch, Changing the Neighborhood of CA, 数理解析研究所講究録 1562, 46-55, 2007.

  30. (28)Turlough Neary and Damien Woods, P-completeness of cellular automaton Rule 110, Lecture Notes in Computer Science 4051, 132-143, July 2006. (alternative version from http://www.bcri.ucc.ie/BCRI_52.pdf)

  31. (29)Mirko Rahn, Universalität in Regel 110, http://www.stud.uni-karlsruhe.de/~uyp0/uni110.foil.ps.gz, 18 März, 2003.

  32. (30)Markus Redeker, Flexible time and the evolution of one-dimensional cellular automata, Journal of Cellular Automata 5(4-5), 273-287, 2010. (alternative version from arXiv at http://arxiv.org/abs/0812.4242)

  33. (31)Gaétan Richard, Rule 110: Universality and Catenations, Journées Automates Cellulaires, 141-160, 2008. (alternative version from http://hal.archives-ouvertes.fr/hal-00273995/en/)

  34. (32)José M. Sausedo-Solorio, Conservation features in binary collisions for rule 110 cellular automaton, Int. J. Modern Physics 21(7), 931-942, 2010.

  35. (33)Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Norberto Hernández-Romero, and Joselito Medina-Marín, Elementary cellular automaton Rule 110 explained as a block substitution, Computing 88, 193-205, 2010.

  36. (34)Jason Summers, “Rule 110” Unit Cell, http://pentadecathlon.com/lifenews/2005/12/rule_110_unit_cell.html, December 21, 2005.

  37. (35)Klaus Sutner, Computational Equivalence and Classical Recursion Theory, In: Irreducibility and Computational Equivalence, H. Zenil (Ed.), Series: Emergence, Complexity and Computation, Vol. 2, chapter 19, 297-310, 2013.

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

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

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

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

  42. (40)Andrew Wuensche, Exploring Discrete Dynamics, Luniver Press, 2011. PDF version is available from www.ddlab.org.

  43. (41)Wikipedia - Rule 110, http://en.wikipedia.org/wiki/Rule_110.

  44. (42)MathWorld - Rule 110, http://mathworld.wolfram.com/Rule110.html.

  45. (43)Wolfram Atlas - Rule 110, http://atlas.wolfram.com/01/01/110/.