Complex Cellular Automata Repository

 

The number of evolution rules grows exponentially according to: dimensions, number of states, and neighbourhood radius. The number of evolution rules with complex behaviour is related to the presence of gliders or signals (particles, waves, mobile self-localizations). Some general studies in two-dimensional CA were initialised with Norman Packard and Stephen Wolfram in [21]. Some investigations were made in semi-totalistic rules by Michael Magnier et. al. [19]. Another morphological analysis on all spectrum of semi-totalistic evolution rules of kind (xywz) was realized in [2]. Before we recommend amply:


  1. •Life-like data base glider-based, created by David Eppstein at: http://fano.ics.uci.edu/ca/.

  2. •Rule table repository, created by Tim Hutton, shows several complex CA, code implementation, algorithms, and details, available in: http://code.google.com/p/ruletablerepository/.


By the way, you can explore a diversity of complex rules from:


  1. •Primordial Soup Kitchen (by David Griffeath)

  2. •Super Animation-Reduction Cellular Automata Simulator, SARCASim (by George Maydwell)

  3. •Golly Game of Life, Golly (by Andrew Trevorrow and Tom Rokicki)

  4. •Mirek’s Cellebrations (by Mirek Wójtowicz)

  5. •Discrete Dynamics Lab, DDLab (by Andy Wuensche)

  6. •Ready (by Tim Hutton, Robert Munafo, Andrew Trevorrow and Tom Rokicki)

  7. •References to Life-like rules please go to the next LINK.


We enumerate some of the evolution rules, or sets of rules, with complex behaviour that has been discovered through of history.


  1. 1.Automaton John von Neumann (29 states, 2D, von Neumann's neighbourhood, [24]), 1966.

  2. 2.Automaton Edward F. Cood (8 states, 2D, Moore's neighbourhood, [9]), 1968.

  3. 3.The Game of Life, John Horton Conway (2 states, 2D, Moore's neighbourhood, [13]), 1970.

  4. 4.Sidorov’s rule, I. Sidorov (3 states, 2D, Moore's neighbourhood, [39]), 1975.

  5. 5.Self-reproduction in Cellular Automata, Christopher G. Langton, ([18]), 1983.

  6. 6.Rule 110, Stephen Wolfram (2 states, 1D, three neighbours, [25]), 1986.

  7. 7.Parity-rule automata, Kenneth Steiglitz (2 states, 1D, [35]), 1986.

  8. 8.Critters rule, Norman Margolus (2 states, 2D, partitioned CA, [23]), 1987.

  9. 9.Brian's brain, Brian Silverman (3 states, 2D, Moore's neighbours, [23]), 1987.

  10. 10.Life 3D - R(5766) and R(4555), Carter Bays (2 states, 3D, Moore's neighbourhood, [3]), 1987.

  11. 11.Rule 54, Nino Boccara, J. Nasser, and M. Roger (2 states, 1D, three neighbours, [4]), 1991.

  12. 12.High Life, David I. Bell (2 states, 2D, Moore's neighbourhood, [7]), May 7, 1994.

  13. 13.Life Without Death, David Griffeath and Cristopher Moore (2 states, 2D, Moore's neighbourhood, [14]), February 13, 1995.

  14. 14.Life 1133, Jean-Claude Heudin (2 states, 2D, Moore's neighbourhood, [15]), 1996.

  15. 15.Large than Life, Kellie M. Evans (2D, [20]), 1996.

  16. 16.B35/S236, Dean Hickerson and David Eppstein (2 states, 2D, Moore's neighbourhood, [12]), year ?.

  17. 17.Day & Night - An Interesting Variant of Life, David I. Bell, (2 states, 2D, Moore's neighbourhood, [7]) November 30, 1997.

  18. 18.ØGA cellular automaton, James P. Crutchfield, Melanie Mitchell, and Rajarshi Das (2 states, 1D, seven neighbours, [11]), 1998.

  19. 19.Self-reproduction in 3D RCA, Rules SR, Katsunobu Imai, Takahiro Hori, and Kenichi Morita, (9 states, 3D and 2D, von Neumann's neighbourhood, [17]), 2002.

  20. 20.Beehive Rule, Andrew Wuensche (3 states, 2D and 3D, hexagonal neighbourhood, [27]), 2004.

  21. 21.Diffusion Rule, Genaro J. Martínez, Andrew Adamatzky, and Harold V. McIntosh (2 states, 2D, Moore's neighbourhood, [16]), April 2005.

  22. 22.Spiral Rule, Andrew Wuensche and Andrew Adamatzky (3 states, 2D, hexagonal neighborhood, [26]), 2006.

  23. 23.R Rule, E. Sapin, O. Bailleux, J. Chabrier, and P. Collet (2 states, 2D, Moore's neighborhood, [28]), 2007.

  24. 24.Hexagonal Life Like Rules, George Maydwell (2 states, 2D, hexagonal neighborhood), February 2007.

  25. 25.ØR126maj:4, Genaro J. Martínez, Andy Adamatzky, Juan C. Seck-Tuoh-Mora, and Ramon Alonso-Sanz (2 states, 1D with memory, three neighbourhoods, memory = 4, [36]), June 2008.

  26. 26.B2/S2345, Genaro J. Martínez, Andy Adamatzky, Kenichi Morita, and Maurice Margenstern, (2 states, 2D, Moore neighbourhood, [25]), June 2010.

  27. 27.Steppers rule cellular automaton, Sergei Milkhin (3 states, 2D, Moore neighbourhood, [31]), July 2012.


Some interesting implementations and proofs.


  1. 1.Universality in the Game of Life, Elwyn Berlekamp, John Conway and Richard Guy, 1982. [6]

  2. 2.An implementation of von Neumann's self-reproducing machine, Umberto Pesavento, 1995. [22]

  3. 3.A Turing Machine In Conway's Game Life, Paul Rendell, 2000. [1]

  4. 4.A Simple Universal Logic Element and Cellular Automata for Reversible Computing, Kenichi Morita, 2001. [37]

  5. 5.Life Universal Computer, Paul Chapman, 2002. [8]

  6. 6.Universality in Elementary Cellular Automata, Matthew Cook, 1998-2004. [10]

  7. 7.Two-state reversible, universal cellular automata in three dimensions, Daniel B. Miller and Edward Fredkin, 2005. [34]

  8. 8.Constructibility of Signal-Crossing Solutions in von Neumann 29-State Cellular Automata, William Buckley and Amar Mukherjee, 2005. [5]

  9. 9.Codd's self-replicating computer, Tim J. Hutton, 2009. [30]

  10. 10.Spartan Universal Computer-Constructor, Adam P. Goucher, 2009. [32]

  11. 11.Computer Scientists Build Cellular Automaton Supercollider, 2011. [38]

  12. 12.Gliders in Cellular Automata on Penrose Tilings, Adam P. Goucher, 2012. [33]

  13. 13.Small Universal Cellular Automata in Hyperbolic Spaces, Maurice Margenstern, 2013. [40]

  14. 14.ETPCA T0347, Kenichi Morita, 2016. [41]


References

(If some reference or evolution rule by my ignorance is not including, I will be very happy to receive them)


  1. (1)Andrew Adamatzky (Ed.), Collision-Based Computing, Springer Verlag, 2001.

  2. (2)Andrew Adamatzky, Genaro J. Martínez and Juan C. S. T. Mora, "Phenomenology of reaction-diffusion binary-state cellular automata," International Journal of Bifurcation and Chaos 16, No. 10, 1-21, 2006.

  3. (3)Carter Bays, "Candidates for the Game of Life in Three Dimensions," Complex Systems 1, 373-400, 1987.

  4. (4)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, No. 2, 866-875, July 1991.

  5. (5)William R. Buckley and Amar Mukherjee, "Constructibility of Signal-Crossing Solutions in von Neumann 29-State Cellular Automata," Lecture Notes in Computer Science 3515, 395-403, 2005.

  6. (6)Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, Winning Ways for your Mathematical Plays, Academic Press, vol. 2, chapter 2, 1982.

  7. (7)David I. Bell, "HighLife - An Interesting Variant of Life," http://www.tip.net.au/~dbell/, 1994.

  8. (8)Paul Chapman, "Life Universal Computer," http://www.igblan.free-online.co.uk/igblan/ca/, November 2002.

  9. (9)E. F. Codd, Cellular Automata, Academic Press, Inc. New York and London 1968.

  10. (10)Matthew Cook, "Universality in Elementary Cellular Automata," Complex Systems 15, Number 1, 1-40, 2004.

  11. (11)James P. Crutchfield, Melanie Mitchell and Rajarshi Das, "The evolutionary design of collective computation in cellular automata," Evolutionary Dynamics-Exploring the Interplay of Selection, Neutrality, Accident, and Function, In Crutchfield, P. and Schuster, P. (Eds.), 361-411, Oxford University Press, 2003.

  12. (12)David Eppstein, "Life variant B35/S236," http://fano.ics.uci.edu/ca/rules/b2s7/, year ?.

  13. (13)Martin Gardner, "Mathematical Games - The fantastic combinations of John H. Conway's new solitaire game Life," Scientific American 223, 120-123, 1970.

  14. (14)David Griffeath and Cristopher Moore, "Life Without Death is P-complete," Complex Systems 10, 437-447, 1996.

  15. (15)Jean-Claude Heudin, "A New Candidate Rule for the Game of Two-dimensional Life," Complex Systems 10, 367-381, 1996.

  16. (16)Genaro J. Martínez, Andrew Adamatzky and Harold V. McIntosh, "Localization dynamic in a binary two-dimensional cellular automaton: the Diffusion Rule," Journal of Cellular Automata 5(4-5), 289-313, 2010.

  17. (17)Katsunobu Imai, Takahiro Hori and Kenichi Morita, "Self-reproduction in three-dimensional reversible cellular space," Artificial Life Vol. 8, Issue 2, 155-174, The MIT Press, 2002.

  18. (18)J. Doyne Farmer, Tommaso Toffoli and Stephen Wolfram (Editors), Cellular Automata: Proceedings of an Interdisciplinary Workshop, Los Alamos, March 7-11, 1983.

  19. (19)Michael Magnier, Claude Lattaud and Jean-Claude Heudin, "Complexity Classes in the Two-dimensional Life Cellular Automata Subspace," Complex Systems 11, no. 6, 419-436, 1997.

  20. (20)Kellie M. Evans, "Larger than Life; it's so nonlinear," Thesis dissertation, University of Wisconsin, Madison, 1996.

  21. (21)Norman Packard and Stephen Wolfram, "Two-Dimensional Cellular Automata," Journal of Statistical Physics 38, 901-946, March 1985.

  22. (22)Umberto Pesavento, "An implementation of von Neumann's self-reproducing machine," Artificial Life 2, 337-354, 1995.

  23. (23)Tommaso Toffoli and Norman Margolus, Cellular Automata Machines The MIT Press, Cambridge, Massachusetts, 1987.

  24. (24)John von Neumann, Theory of Self-reproducing Automata (edited and completed by A. W. Burks), University of Illinois Press, Urbana and London 1966.

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

  26. (26)Andrew Wuensche and Andrew Adamatzky, "On spiral glider-guns in hexagonal cellular automata: activator-inhibitor paradigm," International Journal of Modern Physics C, in press, 2006.

  27. (27)Andrew Wuensche, "Self-reproduction by glider collisions; the beehive rule," Alife9 Proceedings, 286-291, The MIT Press, 2004.

  28. (28)E. Sapin, O. Bailleux, J. Chabrier, and P. Collet, "Demonstration of the Universality of a New Cellular Automaton," International Journal of Unconventional Computing 3, 79-103, 2007.

  29. (29)Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita, and Maurice Margenstern, "Computation with competing patterns in Life-like automaton," In: Game of Life Automata, A. Adamatzky (Ed.), Springer, chapter 27, 547-572, 2010.

  30. (30)Tim J. Hutton, "Codd’s self-replicating computer," Artificial Life, 16(2), 99-117, 2010.

  31. (31)Sergei Milkhin, "Steppers rule cellular automaton," by publish, 2012.

  32. (32)Adam P. Goucher, "Universal Computation and Construction in GoL Cellular Automaton," In: Game of Life Cellular Automata, A. Adamatzky (Ed.), Springer, chapter 25, 505-518, 2010.

  33. (33)Adam P. Goucher, "Gliders in Cellular Automata on Penrose Tilings," Journal of Cellular Automata 7(5-6), 385-392, 2013.

  34. (34)Daniel B. Miller and Edward Fredkin, “Two-state, Reversible, Universal Cellular Automata in Three Dimensions,” Proceedings of the Second Conference on Computing Frontiers, ACM, 45-51, 2005.

  35. (35)James K. Park, Kenneth Steiglitz, and William P. Thurston, “Soliton-Like Behavior in Automata,” Physica D 19D, 423-432, 1986. Reprinted in Theory and Applications of Cellular Automata, (S. Wolfram, Ed.), World Scientific Publishing Co., Hong Kong (distributed by Taylor and Francis, Philadelphia), 333-342, 1986.

  36. (36)Genaro J. Martínez, Andrew Adamatzky, Juan C. Seck-Tuoh-Mora, and Ramon Alonso-Sanz, "How to make dull cellular automata complex by adding memory: Rule 126 case study," Complexity 15(6), 34-49, 2010.

  37. (37)Kenichi Morita, A Simple Universal Logic Element and Cellular Automata for Reversible Computing, Lecture Notes in Computer Science 2055, 102-113, 2001.

  38. (38)Genaro J. Martínez, Andrew Adamatzky, and Christopher R. Stephens, “Cellular automaton supercolliders,” International Journal of Modern Physics C 22(4), 419-439, 2011.

  39. (39)Сидоров И. Эволюция игры "Эволюция", Наука и Жизнь. No 3 Март 1975 стр. 116-121.        I. Sidorov, Evolution of game "Evolution", Nauka i Zhizn' (Science and Life), No 3, pp. 116-121, March 1975.

  40. (40)Maurice Margenstern, "Small Universal Cellular Automata in Hyperbolic Spaces," Series: Emergence, Complexity and Computation, Vol. 4, Springer, 2013.

  41. (41)Kenichi Morita (2016) An 8-state simple reversible triangular cellular automaton that exhibits complex behavior, Lecture Notes of Computer Science (9664) 170-184.