Computation with Competing Patterns in Life-Like Automaton | SpringerLink
Skip to main content
Springer Nature Link
Log in

Computation with Competing Patterns in Life-Like Automaton

  • Chapter
Game of Life Cellular Automata

Abstract

We study a Life-like cellular automaton rule B2/S2345 where a cell in state ‘0’ takes state ‘1’ if it has exactly two neighbors in state ‘1’ and the cell remains in the state ‘1’ if it has between two and five neighbors in state ‘1.’ This automaton is a discrete analog spatially extended chemical media, combining both properties of sub-excitable and precipitating chemical media. When started from random initial configuration B2/S2345 automaton exhibits chaotic behavior. Configurations with low density of state ‘1’ show emergence of localized propagating patterns and stationary localizations. We construct basic logical gates and elementary arithmetical circuits by simulating logical signals with mobile localizations reaction propagating geometrically restricted by stationary non-destructible localizations. Values of Boolean variables are encoded into two types of patterns — symmetric (False) and asymmetric (True) patterns — which compete for the ‘empty’ space when propagate in the channels. Implementations of logical gates and binary adders are illustrated explicitly.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 17159
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 21449
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
JPY 21449
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Adamatzky, A.: Computing in Nonlinear Media and Automata Collectives. Institute of Physics Publishing, Bristol and Philadelphia (2001)

    MATH  Google Scholar 

  2. Adamatzky, A. (ed.): Collision-Based Computing. Springer, Berlin (2002)

    MATH  Google Scholar 

  3. Adamatzky, A.: Physarum machines: encapsulating reaction–diffusion to compute spanning tree. Naturwisseschaften 94, 975–980 (2007)

    Article  Google Scholar 

  4. Adamatzky, A.: Hot ice computer. Phys. Lett. A 374(2), 264–271 (2009)

    Article  Google Scholar 

  5. Adamatzky, A., Costello, B.L., Asai, T.: Reaction–Diffusion Computers. Elsevier, Amsterdam (2005)

    Google Scholar 

  6. Adamatzky, A., Martínez, G.J., Seck-Tuoh-Mora, J.C.: Phenomenology of reaction–diffusion binary-state cellular automata. Int. J. Bifurc. Chaos 16 (10), 1–21 (2006)

    Google Scholar 

  7. Beato, V., Engel, H.: Pulse propagation in a model for the photosensitive Belousov–Zhabotinsky reaction with external noise. In: Schimansky-Geier, L., Abbott, D., Neiman, A., Van den Broeck, C. (eds.) Noise in Complex Systems and Stochastic Dynamics. Proc. SPIE, vol. 5114, pp. 353–362 (2003)

    Google Scholar 

  8. Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for Your Mathematical Plays, vol. 2, Chap. 25. Academic Press, San Diego (1982)

    Google Scholar 

  9. Chapman, P.: Life universal computer. http://www.igblan.free-online.co.uk/igblan/ca/ (2002)

  10. Chaté, H., Manneville, P.: Evidence of collective behavior in cellular automata. Europhys. Lett. 14, 409–413 (1991)

    Article  Google Scholar 

  11. Cook, M.: Still Life theory. In: Griffeath, D., Moore, C. (eds.) New Constructions in Cellular Automata, pp. 93–118. Oxford University Press, London (2003)

    Google Scholar 

  12. Costello, B.L., Toth, R., Stone, C., Adamatzky, A., Bull, L.: Implementation of glider guns in the light sensitive Belousov–Zhabotinsky medium. Phys. Rev. E 79, 026114 (2009)

    Article  Google Scholar 

  13. Dupont, C., Agladze, K., Krinsky, V.: Excitable medium with left–right symmetry breaking. Physica A 249, 47–52 (1998)

    Article  Google Scholar 

  14. Gardner, M.: Mathematical Games — The fantastic combinations of John H. Conway’s new solitaire game Life. Sci. Am. 223, 120–123 (1970)

    Article  Google Scholar 

  15. Gorecka, J., Gorecki, J.: T-shaped coincidence detector as a band filter of chemical signal frequency. Phys. Rev. E 67, 067203 (2003)

    Article  Google Scholar 

  16. Gorecki, J., Yoshikawa, K., Igarashi, Y.: On chemical reactors which can count. J. Phys. Chem. A 107, 1664–1669 (2003)

    Article  Google Scholar 

  17. Goucher, A.: Completed universal computer/constructor. http://pentadecathlon.com/lifeNews/2009/08/post.html (2009)

  18. Gravner, J.: Growth phenomena in cellular automata. In: Griffeath, D., Moore, C. (eds.) New Constructions in Cellular Automata, pp. 161–181. Oxford University Press, London (2003)

    Google Scholar 

  19. Griffeath, D., Moore, C.: Life Without Death is P-complete. Complex Syst. 10, 437–447 (1996)

    MATH  MathSciNet  Google Scholar 

  20. Guan, Z., Qin, X., Zhang, Y., Shi, Q.: Network structure cascade for reversible logic. In: Proceedings of the Third International Conference on Natural Computation, vol. 3, pp. 306–310 (2007)

    Google Scholar 

  21. Gutowitz, H.A., Victor, J.D.: Local structure theory in more that one dimension. Complex Syst. 1, 57–68 (1987)

    MATH  MathSciNet  Google Scholar 

  22. Imai, K., Morita, K.: A computation-universal two-dimensional 8-state triangular reversible cellular automaton. Theor. Comput. Sci. 231, 181–191 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  23. Krug, H.J., Pohlmann, L., Kuhnert, L.: Analysis of the modified complete Oregonator (MCO) accounting for oxygen- and photosensitivity of Belousov–Zhabotinsky systems. J. Phys. Chem. 94, 4862–4866 (1990)

    Article  Google Scholar 

  24. Kusumi, T., Yamaguchi, T., Aliev, R., Amemiya, T., Ohmori, T., Hashimoto, H., Yoshikawa, K.: Numerical study on time delay for chemical wave transmission via an inactive gap. Chem. Phys. Lett. 271, 355–60 (1997)

    Article  Google Scholar 

  25. Magnier, M., Lattaud, C., Heudin, J.-K.: Complexity classes in the two-dimensional life cellular automata subspace. Complex Syst. 11(6), 419–436 (1997)

    MATH  MathSciNet  Google Scholar 

  26. Martínez, G.J., Méndez, A.M., Zambrano, M.M.: Un subconjunto de autómata celular con comportamiento complejo en dos dimensiones. http://uncomp.uwe.ac.uk/genaro/papers.html (2005)

  27. Martínez, G.J., Adamatzky, A., Costello, B.L.: On logical gates in precipitating medium: cellular automaton model. Phys. Lett. A 1(48), 1–5 (2008)

    Google Scholar 

  28. Martínez, G.J., Adamatzky, A., McIntosh, H.V.: Localization dynamic in a binary two-dimensional cellular automaton: the Diffusion Rule. J. Cell. Autom. 5, 284–313 (2010)

    Google Scholar 

  29. Martínez, G.J., Adamatzky, A., Morita, K., Margenstern, M.: Majority adder implementation by competing patterns in Life-like rule B2/S2345. In: Calude, C.S., et al. (eds.) UC 2010. Lecture Notes in Computer Science, vol. 6079, pp. 93–104. Springer, Berlin (2010)

    Google Scholar 

  30. Martínez, G.J., Adamatzky, A., McIntosh, H.V., Costello, B.L.: Computation by competing patterns: Life rule B2/S2345678. In: Adamatzky, A., et al. (eds.) Automata 2008: Theory and Applications of Cellular Automata. Luniver Press, Beckington (2008)

    Chapter  Google Scholar 

  31. McIntosh, H.V.: Life’s Still Lifes. http://delta.cs.cinvestav.mx/~mcintosh (1988)

  32. McIntosh, H.V.: Wolfram’s Class IV and a Good Life. Physica D 45, 105–121 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  33. Minsky, M.: Computation: Finite and Infinite Machines. Prentice Hall, New York (1967)

    MATH  Google Scholar 

  34. Mitchell, M.: Life and evolution in computers. Hist. Philos. Life Sci. 23, 361–383 (2001)

    Google Scholar 

  35. Morita, K., Margenstern, M., Imai, K.: Universality of reversible hexagonal cellular automata. Theor. Inform. Appl. 33, 535–550 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  36. Motoike, I.N., Yoshikawa, K., Iguchi, Y., Nakata, S.: Real-time memory on an excitable field. Phys. Rev. E 63, 036220 (2001)

    Article  Google Scholar 

  37. Packard, N., Wolfram, S.: Two-dimensional cellular automata. J. Stat. Phys. 38, 901–946 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  38. Porod, W., Lent, C.S., Bernstein, G.H., Orlov, A.O., Amlani, I., Snider, G.L., Merz, J.L.: Quantum-dot cellular automata: computing with coupled quantum dots. Int. J. Electron. 86(5), 549–590 (1999)

    Article  Google Scholar 

  39. Rendell, P.: Turing universality of the game of life. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 513–540. Springer, Berlin (2002)

    Google Scholar 

  40. Rennard, J.P.: Implementation of logical functions in the Game of Life. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 491–512. Springer, Berlin (2002)

    Google Scholar 

  41. Sielewiesiuk, J., Gorecki, J.: Logical functions of a cross junction of excitable chemical media. J. Phys. Chem. A 105, 8189–8195 (2001)

    Article  Google Scholar 

  42. Toffoli, T.: Non-conventional computers. In: Webster, J. (ed.) Encyclopedia of Electrical and Electronics Engineering, vol. 14, pp. 455–471. Wiley, New York (1998)

    Google Scholar 

  43. Tóth, A., Showalter, K.: Logic gates in excitable media. J. Chem. Phys. 103, 2058–2066 (1995)

    Article  Google Scholar 

  44. von Neumann, J.: Theory of Self-reproducing Automata. Edited and completed by Burks, A.W. University of Illinois, Urbana and London (1966)

    Google Scholar 

  45. Wainwright, R. (ed.): Lifeline – A Quarterly Newsletter for Enthusiasts of John Conway’s Game of Life, Issues 1 to 11, March 1971 to September 1973

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Instituto de Ciencias Nucleares, Universidad Nacional Autónoma de México, Mexico, Mexico

    Genaro J. Martínez

  2. Department of Computer Science, University of the West of England, Bristol, BS16 1QY, UK

    Genaro J. Martínez

Authors
  1. Genaro J. Martínez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew Adamatzky
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kenichi Morita
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Maurice Margenstern
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Genaro J. Martínez .

Editor information

Editors and Affiliations

  1. Fac. of Computing, Engineering and, Mathematical Sciences (CEMS), University of the West of England, Coldharbour Lane, Bristol, BS16 1QY, United Kingdom

    Andrew Adamatzky

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag London Limited

About this chapter

Cite this chapter

Martínez, G.J., Adamatzky, A., Morita, K., Margenstern, M. (2010). Computation with Competing Patterns in Life-Like Automaton. In: Adamatzky, A. (eds) Game of Life Cellular Automata. Springer, London. https://doi.org/10.1007/978-1-84996-217-9_27

Download citation

  • DOI: https://doi.org/10.1007/978-1-84996-217-9_27

  • Publisher Name: Springer, London

  • Print ISBN: 978-1-84996-216-2

  • Online ISBN: 978-1-84996-217-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation