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 behavior, 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 behaviors; but in this case the background where the chaotic behavior occurs is textured rather than quiescent, a tacit assumption in the original classification.

Elemental Cellular Automaton Rule 110

Whatever the merits of this classification, Rule 110 was awarded its own appendix (Table 15) in reference [19]. 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 [11] 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 [1] 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 [12,13]. 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 cyclic tag system (CTS) [2] and [20]; 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 [10] and [14] (also see 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 neighborhood, 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 neighborhood. The transition function simultaneously evaluates a central cell with regard to its left and right neighbors.


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 neighborhood is formed by three cells, a central element,a neighbor to the right and another into the left. Depending on the values in cells of the neighborhood, a new value is defined for the central cell in the next generation.


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


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 [18] show that Cook’s machine can run in polynomial time. Morita in [15] 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 [9]. 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 of our lines of investigation in 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

References related to CA Rule 110

If some reference is not including, I will be very happy to receive you email.


  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.

  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 available from arXiv http://arxiv.org/abs/0906.3248)

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

  5. (5)Genaro J. Martínez, Introduction to Rule 110, Conference Presented in Rule 110 Winter Workshop, http://uncomp.uwe.ac.uk/genaro/papers.html, Bielefeld, Germany, March 2004.

  6. (6)Genaro J. Martínez and Harold V. McIntosh, ATLAS: Collisions of gliders like phases of ether in Rule 110, http://uncomp.uwe.ac.uk/genaro/papers.html, August 2001.

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

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

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

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

  11. (11)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, in press. http://uncomp.uwe.ac.uk/genaro/papers.html

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

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

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

  15. (15)Harold V. McIntosh, Rule 110 Is Universal!, http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html, June 30, 2002.

  16. (16)Kenichi Morita, Simplifying Universal One-Dimensional Reversible Cellular Automaton on Infinite Configurations, Automata 2006, Hiroshima University, 2006.

  17. (17)Shigeru Ninagawa, 1/f Noise in Universal Cellular Automaton Rule 110, The 20th Annual Conference of the Japanese Society for Artificial Intelligence, 2006.

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

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

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

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

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

Fig. 1 OSXLCAU21 system coding gliders by regular expressions in Rule 110.