On the Dynamics of Cellular Automata with Memory

• Autorzy: Martínez G. J. , Adamatzky A. , Alonso-Sanz R.

Identyfikatory

DOI

10.3233/FI-2015-1194

• Języki publikacji: EN

Abstrakty

EN

Elementary cellular automata (ECA) are linear arrays of finite-state machines (cells) which take binary states, and update their states simultaneously depending on states of their closest neighbours. We design and study ECA with memory (ECAM), where every cell remembers its states during some fixed period of evolution. We characterize complexity of ECAM in a case study of rule 126, and then provide detailed behavioural classification of ECAM. We show that by enriching ECA with memory we can achieve transitions between the classes of behavioural complexity. We also show that memory helps to 'discover' hidden information and behaviour on trivial (uniform, periodic), and non-trivial (chaotic, complex) dynamical systems.

Słowa kluczowe

EN

elementary cellular automata; ECA; classification; memory; computability; gliders; collisions; complex systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 1--16
• Opis fizyczny: Bibliogr. 42 poz., rys.

Twórcy

autor

Martínez G. J.

• Escuela Superior de Cómputo, Instituto Politécnico Nacional, México D.F., México International Centre of Unconventional Computing, University of the West of England BS16 1QY Bristol, United Kingdom

autor

Adamatzky A.

• International Centre of Unconventional Computing, University of the West of England BS16 1QY Bristol, United Kingdom

autor

Alonso-Sanz R.

• Universidad Politecnica de Madrid. ETSIA (Estadistica,GSC) Madrid, Spain

Bibliografia

• [1] Amoroso, S. and Cooper, G. [1970] “The Garden-of-Eden theorem for finite configurations,” Proc. Amer. Math. Soc. 26(1), 158–164.
• [2] Adamatzky, A. and Bull, L. [2009] “Are complex systems hard to evolve?” Complexity 14(6), 15–20.
• [3] Alonso-Sanz, R. [2006] “Elementary cellular automata with elementary memory rules in cells: the case of linear rules,” J. Cellular Automata 1(1), 71–87.
• [4] Alonso-Sanz, R. [2009] Cellular Automata with Memory (Old City Publishing).
• [5] Alonso-Sanz, R. [2009] “Cellular automata with memory,” Encyclopedia of Complexity and Systems Science, ed. Meyers, R. (Springer-Verlag, New York), pp. 823–848.
• [6] Alonso-Sanz, R. [2011] Discrete Systems with Memory (World Scientific Series on Nonlinear Science, Series A, Vol. 75).
• [7] Alonso-Sanz, R. [2013] “Elementary cellular automata with memory of delay type,” Kari, J., Kutrib, M., Malcher, A. (Eds.), Lecture Notes in Computer Science 8155, 67-83.
• [8] Alonso-Sanz, R. [2014] “Reversible cellular automata with memory of delay type,” Complexity 20(1), 49–56.
• [9] Arbib, M. A. [1969] Theories of Abstract Automata (Prentice-Hall Series in Automatic Computation).
• [10] Alonso-Sanz, R. and Adamatzky, A. [2008] “On memory and structural dynamism in excitable cellular automata with defensive inhibition,” Int. J. Bifurcation and Chaos 18(2), 527–539.
• [11] Boccara, N. [2004] Modelling Complex Systems (Springer-Verlag, New York).
• [12] Chopard, B. and Droz, M. [1998] Cellular Automata Modeling of Physical Systems (Collection Aléa Saclay, Cambridge University Press).
• [13] Culik II, K. and Yu, S. [1988] “Undecidability of CA Classification Schemes,” Complex Systems 2, 177–190.
• [14] Hoekstra, A. G., Kroc, J. and Sloot, P. M. A. (eds.) [2010] Simulating Complex Systems by Cellular Automata: Understanding Complex Systems (Springer-Verlag, Berlin, Heidelberg).
• [15] Hopcroft, J. E. and Ullman, J. D. [1987] Introduction to Automata Theory Languages, and Computation (Addison-Wesley Publishing Company).
• [16] Martínez, G. J., Adamatzky, A., Alonso-Sanz, R. and Seck-Tuoh-Mora, J. C. [2010] “Complex dynamic emerging in Rule 30 with majority memory,” Complex Systems 18(3), 345–365.
• [17] Martínez, G. J., Adamatzky, A. and Alonso-Sanz, R. [2012] “Complex dynamics of elementary cellular automata emerging in chaotic rules,” Int. J. Bifurcation and Chaos 22(2), 1250023-13.
• [18] Martínez, G. J., Adamatzky, A. and Alonso-Sanz, R. [2013] “Designing Complex Dynamics in Cellular Automata with Memory,” Int. J. Bifurcation and Chaos 23(10), 1330035-131.
• [19] Martínez, G. J., Adamatzky, A. Chen, F. and Chua, L. [2012] “On Soliton Collisions between Localizations in Complex Elementary Cellular Automata: Rules 54 and 110 and Beyond,” Complex Systems 21(2), 117–142.
• [20] Martínez, G. J., Adamatzky, A. and McIntosh, H. V. [2006] “Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates,” Chaos, Solitons and Fractals 28, 100–111.
• [21] Martínez, G. J., Adamatzky, A. and McIntosh, H. V. [2014] “Complete Characterization of Structure of Rule 54,” Complex Systems 32(3), 259–293.
• [22] Martínez, G. J. [2013] “A Note on Elementary Cellular Automata Classification,” J. Cellular Automata 8(3-4), 233–259.
• [23] Martínez, G. J., Adamatzky, A., Seck-Tuoh-Mora, J. C. and Alonso-Sanz, R. [2010] “How to make dull cellular automata complex by adding memory: Rule 126 case study,” Complexity 15(6), 34–49.
• [24] Martínez, G. J., McIntosh, H. V. and Seck-Tuoh-Mora, J. C. [2006] “Gliders in Rule 110,” Int. J. Unconventional Computing 2(1), 1–49.
• [25] McIntosh, H. V. [1990] “Wolfram’s Class IV and a Good Life,” Physica D 45, 105–121.
• [26] McIntosh, H. V. [2009] One Dimensional Cellular Automata (Luniver Press).
• [27] Minsky, M. [1967] Computation: Finite and Infinite Machines (Prentice Hall, Inc.).
• [28] Morita, K. [1998] “Cellular Automata and Artificial Life,” Complex Systems, eds. Goles, E. and Martinez, S. (Kluwer Academic Publishers), pp. 151–200.
• [29] Rogozhin, Y. [1996] “Small Universal Turing Machines,” Theor. Comput. Sci. 168(2), 215–240.
• [30] Rogozhin, Y. and Verlan, S. [2006] “On the Rule Complexity of Universal Tissue P Systems,” Lecture Notes in Computer Science 3850, 356–362.
• [31] Toffoli,T. [1984] “Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics,” Physica D 10, 117–27.
• [32] Voorhees, B. H. [1996] Computational analysis of one-dimensional cellular automata (World Scientific Series on Nonlinear Science, Series A, Vol. 15).
• [33] Voorhees, B. H. [2008] “Remarks on Applications of De Bruijn Diagrams and Their Fragments,” J. Cellular Automata 3(3), 187–204.
• [34] von Neumann, J. [1966] Theory of Self-reproducing Automata, edited and completed by Burks, A. W., (University of Illinois Press, Urbana and London).
• [35] Wuensche, A. and Lesser, M. [1992] The Global Dynamics of Cellular Automata (Addison-Wesley Publishing Company).
• [36] Wolfram, S. [1983] “Statistical Mechanics of Cellular Automata,” Rev. Mod. Phys. 55, 601–644.
• [37] Wolfram, S. [1984] “Universality and complexity in cellular automata,” Physica D 10, 1–35.
• [38] Wolfram, S. [1984] “Computation Theory of Cellular Automata,” Commun. Math. Phys. 96(1), 15–57.
• [39] Wolfram, S. [1986] Theory and Applications of Cellular Automata (World Scientific Publishing Company, Singapore).
• [40] Wolfram, S. [1994] Cellular Automata and Complexity: Collected Papers (Addison-Wesley Publishing Company).
• [41] Wolfram, S. [2002] A New Kind of Science (Wolfram Media, Inc., Champaign, Illinois).
• [42] Wuensche, A. [1999] “Classifying Cellular Automata Automatically,” Complexity 4(3), 47–66.