THEME SECTION: Complex Systems and Applications — PapersNo Access

COMPLEX DYNAMICS OF ELEMENTARY CELLULAR AUTOMATA EMERGING FROM CHAOTIC RULES

Instituto de Ciencias Nucleares, and Centro de Ciencias de la Complejidad, Universidad Nacional Autónoma de México, México

Search for more papers by this author

ANDREW ADAMATZKY

Bristol Institute of Technology, University of the West of England, Bristol, UK

Search for more papers by this author

, and

RAMON ALONSO-SANZ

ETSI Agrónomos, Polytechnic University of Madrid, Madrid, Spain

Search for more papers by this author

https://doi.org/10.1142/S021812741250023XCited by:26 (Source: Crossref)

Abstract

We show techniques of analyzing complex dynamics of cellular automata (CA) with chaotic behavior. CA are well-known computational substrates for studying emergent collective behavior, complexity, randomness and interaction between order and chaotic systems. A number of attempts have been made to classify CA functions on their space-time dynamics and to predict the behavior of any given function. Examples include mechanical computation, λ and Z-parameters, mean field theory, differential equations and number conserving features. We aim to classify CA based on their behavior when they act in a historical mode, i.e. as CA with memory. We demonstrate that cell-state transition rules enriched with memory quickly transform a chaotic system converging to a complex global behavior from almost any initial condition. Thus, just in few steps we can select chaotic rules without exhaustive computational experiments or recurring to additional parameters. We provide an analysis of well-known chaotic functions in one-dimensional CA, and decompose dynamics of the automata using majority memory exploring glider dynamics and reactions.

Keywords:

References

A. Adamatzky , Identification of Cellular Automata ( Taylor and Francis , London , 1994 ) . Google Scholar
A. Adamatzky (ed.) , Collision-Based Computing ( Springer-Verlag , London , 2002 ) . Crossref, Google Scholar
A. Adamatzky, G. J. Martínez and J. C. Seck-Tuoh-Mora, Int. J. Bifurcation and Chaos 16, 1 (2006). Web of Science, Google Scholar
R. Alonso-Sanz and M. Martin, Compl. Syst. 14, 99 (2003). Web of Science, Google Scholar
R. Alonso-Sanz, J. Cellular Autom. 1, 71 (2006). Web of Science, Google Scholar
R. Alonso-Sanz , Cellular Automata with Memory ( Old City Publishing, Inc. , 2008 ) . Google Scholar
R. Alonso-Sanz , Encyclopedia of Complexity and Systems Science , ed. R. Meyers ( Springer , NY , 2009 ) . Google Scholar
R. Alonso-Sanz, Chaos 19, 023102 (2009), DOI: 10.1063/1.3106322. Crossref, Web of Science, Google Scholar
S. Amoroso and G. Cooper, Proc. Amer. Math. Soc. 44, 189 (1970). Web of Science, Google Scholar
Y. Bar-Yam , Dynamics of Complex Systems ( Perseus Books , 1997 ) . Google Scholar
N. Boccara and H. Fukś, Fund. Inform. 52, 1 (2002). Web of Science, Google Scholar
L. O. Chua , A Nonlinear Dynamics Perspective of Wolfram's New Kind of Science ( World Scientific Publishing Company , 2007 ) . Link, Google Scholar
Das, R., Mitchell, M. & Crutchfield, J. P. [1994] "A genetic algorithm discovers particle-based computation in cellular automata," Lecture Notes in Computer Science, Vol. 866, pp. 344–353 . Google Scholar
D. Eppstein, MSRI Publ. 42, 433 (2002). Google Scholar
J. E. Hanson and J. P. Crutchfield, Physics D 103, 169 (1997), DOI: 10.1016/S0167-2789(96)00259-X. Crossref, Web of Science, Google Scholar
K. Imaiet al., IEICE Trans. Inform. Syst. E 87-D, 694 (2004). Google Scholar
S. A. Kauffman , The Origins of Order: Self-Organization and Selection in Evolution ( Oxford University Press , NY , 1993 ) . Crossref, Google Scholar
M. Margenstern , Cellular Automata in Hyperbolic Spaces ( Old City Publishing, Inc. , 2007 ) . Google Scholar
G. J. Martínez, H. V. McIntosh and J. C. Seck-Tuoh-Mora, Int. J. Unconvent. Comput. 2, 1 (2006). Web of Science, Google Scholar
G. J. Martínez, A. Adamatzky and H. V. McIntosh, Chaos Solit. Fract. 28, 100 (2006). Crossref, Web of Science, Google Scholar
Martínez, G. J., Adamatzky, A. & McIntosh, H. V. [2008] "On the representation of gliders in Rule 54 by de Bruijn and cycle diagrams," Lecture Notes in Computer Science, Vol. 5191, pp. 83–91 . Google Scholar
G. J. Martínezet al., Compl. Syst. 18, 345 (2010). Crossref, Google Scholar
G. J. Martínezet al., Complexity 15, 34 (2010). Crossref, Web of Science, Google Scholar
H. V. McIntosh, Physica D 45, 105 (1990), DOI: 10.1016/0167-2789(90)90177-Q. Crossref, Web of Science, Google Scholar
H. V. McIntosh , One Dimensional Cellular Automata ( Luniver Press , 2009 ) . Google Scholar
M. Minsky , Computation: Finite and Infinite Machines ( Prentice Hall , 1967 ) . Google Scholar
M. Mitchell and M. Newman , Encyclopedia of Evolution , ed. M. Pagel ( Oxford University Press , 2002 ) . Google Scholar
M. Mitchell , Complexity: A Guided Tour ( Oxford University Press , 2009 ) . Crossref, Google Scholar
Morita, K. [1998] "Cellular automata and artificial life," 6th. Summer School on Complex Systems . Google Scholar
C. Robinson , Dynamical Systems: Stability, Symbolic Dynamics and Chaos ( CRC Press , 1994 ) . Google Scholar
S. Wolfram, Physica D 10, 1 (1984), DOI: 10.1016/0167-2789(84)90245-8. Crossref, Web of Science, Google Scholar
S. Wolfram , Cellular Automata and Complexity ( Addison-Wesley Publishing Company , 1994 ) . Google Scholar
S. Wolfram , A New Kind of Science ( Wolfram Media, Inc. , Champaign, Illinois , 2002 ) . Google Scholar
A. Wuensche and M. Lesser , The Global Dynamics of Cellular Automata ( Addison-Wesley Publishing Company , 1992 ) . Google Scholar
Wuensche, A. [1994] "Complexity in one-d cellular automata," Santa Fe Institute working paper 94-04-025 . Google Scholar
A. Wuensche, Complexity 4, 47 (1999). Crossref, Google Scholar