Title: Computation with competing patterns in Life-like automaton

Book: The Game of Life Cellular Automata, A. Adamatzky (Ed.), Springer, 2010.

Authors: Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita, and Maurice Margenstern

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.

Title: Majority adder implementation by competing patterns in Life-like rule B2/S2345

Journal: submitted.

Authors: Genaro J. Martínez, Kenichi Morita, Andrew Adamatzky, and Maurice Margenstern

Abstract: In this paper we present a two-dimensional chaotic cellular automaton, the Life rule B2/S2345, able to simulate the action of an adder with majority gates, stimulated by gliders collisions transformed as competing patterns. 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. We construct basic logical gates and elementary arithmetical circuits by simulating logical signals with gliders reaction propagating geometrically restricted by stationary non-destructible still life. Therefore an implementation of universal logical gates and a majority binary adder is constructed.

Title: How to make dull cellular automata complex by adding memory: Rule 126 case study

Journal: Complexity, DOI: 10.1002/cplx.20311 (on line version), 2010.

Authors: Genaro J. Martínez, Andrew Adamatzky, Juan C. S. T. Mora, and Ramon Alonso-Sanz

Abstract: Using Rule 126 elementary cellular automaton (ECA) we demonstrate that a chaotic discrete system --- when enriched with memory -- hence exhibits complex dynamics where such space exploits on an ample universe of periodic patterns induced from original information of the ahistorical system. First we analyse classic ECA Rule 126 to identify basic characteristics with mean field theory, basins, and de Bruijn diagrams. In order to derive this complex dynamics, we use a kind of memory on Rule 126; from here interactions between gliders are studied for detecting stationary patterns, glider guns and simulating specific simple computable functions produced by glider collisions.

Title: Complex dynamics of elementary cellular automata emerging in chaotic rules

Journal: International Journal of Bifurcation and Chaos, accepted.

Authors: Genaro J. Martínez, Andrew Adamatzky, and Ramon Alonso-Sanz

Abstract: We show novel techniques of analysing complex dynamics of cellular automata (CA) with chaotic behaviour. CA are well known computational substrates for studying emergent collective behaviour, complexity, randomness and interaction between order and disorder. A number of attempts have been made to classify CA functions on their spatio-temporal dynamics and to predict behavior of any given function. Examples include mechanical computation, lambda and Z-parameters, mean field theory, differential equations and number conserving features. We propose to classify CA based on their behaviour 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 behaviour 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 analysis of well-known chaotic functions in one-dimensional CA, and decompose dynamics of the automata using majority memory.

Title: Reproducing the cyclic tag system developed by Matthew Cook with Rule 110 using the phases f1_1

Journal: Journal of Cellular Automata, in press. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. S. T. Mora, and Sergio V. C. Vergara

Abstract: This paper implements the cyclic tag system (CTS) in Rule 110 developed by Cook in [1, 2] using regular expressions denominated phases fi_1 [3]. The main problem in CTS is coding the initial condition based in a system of gliders. In this way, we develop a method to control the periodic phases of the strings representing all gliders until now known in Rule 110, including glider guns. These strings form a subset of regular expressions implemented in a computational system to facilitate the construction of CTS. Thus, these phases are useful to establish distances and positions for every glider and then to delineate more sophisticated components or packages of gliders. In this manuscript, it is possible to find differences with the results exposed in Wolfram's book [2], inclusively some mistakes which avoid to obtain an appropriated realization of CTS in Rule 110; fortunately, these irregularities were discussed and clarified by Cook.

Title: Complex dynamics emerging in Rule 30 with majority memory

Journal: Complex Systems 18 (3), 345-365, 2010. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Ramon Alonso-Sanz, and Juan C. S. T. Mora

Abstract: In cellular automata with memory, the unchanged maps of the conventional cellular automata are applied to cells endowed with memory of their past states in some specified interval. We implement Rule 30 automata with a majority memory and show that using the memory function we can transform quasi-chaotic dynamics of classical Rule 30 into domains of travelling structures with predictable behaviour. We analyse morphological complexity of the automata and classify dynamics of gliders (particle, self-localizations) in memory-enriched Rule 30. We provide formal ways of encoding and classifying glider dynamics using de Bruijn diagrams, soliton reactions and quasi-chemical representations.

Title: On generative morphological diversity of elementary cellular automata

Journal: Kybernetes 39 (1), 2010. [PDF]

Authors: Andrew Adamatzky and Genaro J. Martínez

Abstract: Studies in complexity of cellular automata do usually deal with measures taken on integral dynamics or statistical measures of space-time configurations. No one every tried to analyze a generative power of cellular-automaton machines. We aim to fill the gap and develop a basis for future studies in generative complexity of large-scale spatially extended systems.

Title: Localization dynamics in a binary two-dimensional cellular automaton: the Diffusion Rule

Journal: arXiv:0908.0828v1, 2007-2009. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, and Harold V. McIntosh

Abstract: We study a two-dimensional cellular automaton (CA), called Diffusion Rule (DR), which exhibits diffusion-like dynamics of propagating patterns. In computational experiments we discover a wide range of mobile and stationary localizations (gliders, oscillators, glider guns, puffer trains, etc), analyze spatio-temporal dynamics of collisions between localizations, and discuss possible applications in unconventional computing.

Title: Operating binary strings using gliders and eaters in reaction-diffusion cellular automaton

Journal: arXiv:0908.0853v1, 2009. [PDF]

Authors: Andrew Adamatzky, Genaro J. Martínez, Liang Zhang, and Andrew Wuensche

Abstract: We study transformations of 2-, 4- and 6-bit numbers in interactions between traveling and stationary localizations in the Spiral Rule reaction-diffusion cellular automaton. The Spiral Rule automaton is a hexagonal ternary-state two-dimensional cellular automaton -- a finite-state machine imitation of an activator-inhibitor reaction-diffusion system. The activator is self-inhibited in certain concentrations. The inhibitor dissociates in the absence of the activator. The Spiral Rule cellular automaton has rich spatio-temporal dynamics of traveling (glider) and stationary (eater) patterns. When a glider brushes an eater the eater may slightly change its configuration, which is updated once more every next hit. We encode binary strings in the states of eaters and sequences of gliders. We study what types of binary compositions of binary strings are implementable by sequences of gliders brushing an eater. The models developed will be used in future laboratory designs of reaction-diffusion chemical computers.

Title: A note about the regular language of Rule 110 and its general machine: the scalar subset diagram

Journal: Japan Society for Artificial Intelligence C3004, 39-49, Yokohama, Japan, 2008. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. S. T. Mora, and Sergio V. C. Vergara

Abstract: As it was published in other papers, a regular language can be derived in the elemental cellular automaton (ECA) Rule 110 from a subset of regular expressions produced from its set of gliders. This way, a full description of this subset too is known and reported. This paper will discuss in detail a general machine able to validate completely the subset of regular expressions in Rule 110 and other characteristics, such as, the calculus of Garden of Eden configurations in Rule 110. Such machine is the subset diagram.

Title: On the representation of gliders in Rule 54 by de Bruijn and cycle diagrams

Journal: Lecture Notes in Computer Science 5191, 83-91, 2008. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, and Harold V. McIntosh

Abstract: Rule 54, in Wolfram’s notation, is one of elementary yet complexly behaving one-dimensional cellular automata. The automaton supports gliders, glider guns and other non-trivial long transients. We show how to characterize gliders in Rule 54 by diagram representations as de Bruijn and cycle diagrams; offering a way to present each glider in Rule 54 with particular characteristics. This allows a compact encoding of initial conditions which can be used in implementing non-trivial collision-based computing in one-dimensional cellular automata.

Title: Computation by competing patterns: Life rule B2/S2345678

Book: Automata 2008: Theory and Applications of Cellular Automata, Luniver Press, 2008. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh, and Ben D. L. Costello

Abstract: Patterns, originating from different sources of perturbations, propagating in a precipitating chemical medium do usually compete for the space. They sub-divide the medium onto the regions unique for an initial configuration of disturbances. This sub-division can be expressed in terms of computation. We adopt an analogy between precipitating chemical media and semi-totalistic binary two-dimensional cellular automata, with cell-state transition rule B2/S2...8. We demonstrate how to implement basic logic and arithmetical operations (computability) by patterns propagating in geometrically constrained Life rule B2/S2...8 medium.

Title: On logical gates in precipitating medium: cellular automaton model

Journal: Physics Letters A 1 (48), 1-5, 2008. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, and Ben D. L. Costello

Abstract: We study a two-dimensional semi-totalistic binary cell-state cellular automaton, which imitates a reversible precipitation in an abstract chemical medium. The systems exhibits a non-trivial growth and nucleation. We demonstrate how basic computational operation can be realized in the system when the propagation of the growing patterns is self-restricted by stationary localizations. We show that precipitating patterns of different morphology compete between each other and thus implement serial and non-serial logical gates.

Title: Determining a regular language by glider-based structures called phases fi_1 in Rule 110

Journal: Journal of Cellular Automata 3 (3), 231-270, 2008. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. S. T. Mora, and Sergio V. C. Vergara

Abstract: Rule 110 is a complex elementary cellular automaton able of supporting universal computation and complicated collision-based reactions between gliders. We propose a representation for coding initial conditions by means of a finite subset of regular expressions. 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 in detail.

Title: Rule 110 objects and other constructions based-collisions

Journal: Journal of Cellular Automata 2 (3), 219-242, 2007. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. S. T. Mora, and Sergio V. C. Vergara

Abstract: The one-dimensional cellular automaton Rule 110 shows a very ample and diversified glider dynamics. The huge number of collision-based reactions presented in its evolution space are useful to implement some specific (conventional and unconventional) computable process, hence Rule 110 may be used to implement any desired simulation. Therefore there is necessity of defining some interesting objects as: solitons, eaters, black holes, flip-flops, fuses and more. For example, this work explains the construction of meta-gliders; for these constructions, we specify a regular language in Rule 110 to code in detail initial conditions with a required behavior. The paper depicts as well several experimental collision-based constructions.

Title: Phenomenology of reaction-diffusion binary-state cellular automata

Authors: Andrew Adamatzky, Genaro J. Martínez, and Juan C. S. T. Mora

Journal: International Journal of Bifurcation and Chaos 16 (10), 1-21, 2006. [PDF]

Abstract: We study a binary-cell-states eight-cell neighborhood two-dimensional cellular automaton model of a quasi-chemical system with a substrate and a reagent. Reactions are represented by semi-totalistic transitions rules: every cell switches from state 0 to state 1 depending on if sum of neighbors in state 1 belongs to some specified interval, cell remains in state 1 if sum of neighbors in state 1 belong to another specified interval. We investigate space-time dynamics of 1296 automata, establish morphology-bases classification of the rules, explore precipitating and excitatory cases and scrutinize collisions between mobile and stationary localizations (gliders, cycle life and still life compact patterns). We explore reaction-diffusion like patterns produced in result of collisions between localizations. Also, we propose a set of rules with complex behavior called Life 2c22.

Title: The inverse behavior of a reversible one-dimensional cellular automaton obtained by a single welch diagram

Journal: Journal of Cellular Automata 1 (1), 25-39, 2006. [PDF]

Authors: Juan C. S. T. Mora, Genaro J. Martínez, and Harold V. McIntosh

Abstract: Reversible cellular automata are discrete dynamical systems based on local interactions which are able to produce an invertible global behavior. Reversible automata have been carefully analyzed by means of graph and matrix tools, in particular the extensions of the ancestors in these systems have a complete representation by Welch diagrams. This paper illustrates how the whole information of a reversible one-dimensional cellular automaton is conserved at both sides of the ancestors for sequences with an adequate length. We give this result implementing a procedure to obtain the inverse behavior by means of calculating and studying a single Welch diagram corresponding with the extensions of only one side of the ancestors. This work is a continuation of our study about reversible automata both in the local and global sense. An illustrative example is also presented.

Title: Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates

Journal: Chaos, Fractals and Solitons 28, 100-111, 2006. [PDF]

Authors: Genaro J. Martínez, Andrew Adamatzky, and Harold V. McIntosh

Abstract: Rule 54, a two state, three neighbor cellular automaton in Wolfram Rule 110, but nevertheless possess a rich and complex dynamics. We provide a systematic and exhaustive analysis of glider behavior and interactions, including a catalog of collisions. Many of them shows promise are computational elements.

Title: Gliders in Rule 110

Journal: International Journal of Unconventional Computing 2 (1), 1-49, 2006. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, and Juan C. S. T. Mora

Abstract: 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. We investigate the types of gliders, their properties and production through collisions in Rule 110 and their representation by tiles.

Title: Procedures for calculating reversible one-dimensional cellular automata

Journal: Physica D 202, 134-141, 2005. [PDF]

Authors: Juan C. S. T. Mora, Sergio V. C. Vergara, Genaro J. Martínez, and Harold V. McIntosh

Abstract: Two algorithms for calculating reversible one-dimensional cellular automata of neighborhood size 2 are presented. It is explained how this kind of automata represents all the rest. Using two basic properties of these systems such as the uniform multiplicity of ancestors and Welch indices, these algorithms only require matrix products and the transitive closure of binary relations to yield the calculation of reversible automata. The features, advantages and differences of these algorithms are described and results for reversible automata of 3, 4, 5 and 6 states are comprised.

Title: Un subconjunto de autómata celular con comportamiento complejo en dos dimensiones

Site: Escuela Superior de Cómputo, Instituto Politécnico Nacional, México, 2005. [PDF] spanish workpaper

Authors: Genaro J. Martínez, Adriana M. Méndez, y Miriam M. Zambrano

Abstract: Modelos matemáticos con la capacidad de soportar comportamiento complejo han sido formulados y análizados a través de la historia de las matemáticas. Nosotros estudiamos un modelo discreto en dos dimensiones conocido como autómata celular. Dentro de estos sistemas dinámicos existen funciones que pueden soportar comportamiento complejo, como el famoso “Juego de la Vida.” En este artículo presentamos un nuevo subconjunto de reglas que soportan partículas y que llamamos Life 2c22. Además calculamos sus mutaciones con la capacidad de soportar comportamientos del tipo reacción-difusión a través de choques entre partículas.

Title: Introduction to Rule 110

Site: Bielefeld, Germany, 2004. [HTML or PDF workpaper] (also available from Rule110.org)

Author: Genaro J. Martínez

Abstract: A brief introduction to the study of the cellular automaton Rule 110 is presented. We begin with a general historical background of cellular automata theory, discussing the most important stages of development. Later we show the antecedents in the study of Rule 110, making special emphasis in the conjecture of Stephen Wolfram and the results of Matthew Cook. Finally we develop a relation between the models of John von Neumann, John Horton Conway and Cook, discussing important problems in cellular automata theory.

Title: Introduction to OSXLCAU21 System

Site: Bielefeld, Germany, 2004. [HTML and PDF workpaper] (also available from Rule110.org)

Author: Genaro J. Martínez

Abstract: This paper describes each one of the parts of OSXLCAU21 system, the main feature of this application is the panel of gliders which allows to reproduce any binary collisions among them. The system is implemented with the idea of providing an useful and easy environment to the user for studying and realizing experimentation in the analysis of Rule 110.

Title: Correspondence between the temporal and spacial behavior in reversible one-dimensional cellular automata equivalent with the full shift

Site: DMCS Workshop, University of Turku, Finland, 2004. [PDF]

Authors: Juan C. S. T. Mora, Genaro J. Martínez, and Harold V. McIntosh

Abstract: We present the basic properties of reversible one-dimensional cellular automata equivalent by permutations with the full shift, this work only takes reversible automata of neighborhood size 2. In these cases, we prove that the evolution rule defining the temporal behavior of the automaton may specify the spacial behavior as well. Based in this result we present a procedure for constructing configurations with a predefined dynamical behavior. Some examples of these results are presented.

Title: Calculating ancestors in one-dimensional cellular automata

..., 2003. [PDF]

Title: Production of gliders by collisions in Rule 110

Journal: Lecture Notes in Computer Science 2801, 175-182, 2003. [PDF]

Authors: Genaro J. Martínez, Harold V. McIntosh, and Juan C. S. T. Mora

Abstract: We investigate the construction of all the periodic structures or “gliders” up to now known in the evolution space of the one-dimensional cellular automaton Rule 110. The production of these periodic structures is developed and presented by means of glider collisions. We provide a methodology based on the phases of each glider to establish the necessary conditions for controlling and displaying the collisions of gliders from the initial configuration.

Title: Spectral properties of reversible one-dimensional cellular automata

Journal: International Journal of Modern Physics C 14 (3), 379-395, 2003. [PDF]

Authors: Juan C. S. T. Mora, Sergio V. C. Vergara, Genaro J. Martínez, and Harold V. McIntosh

Abstract: Reversible cellular automata are invertible dynamical systems characterized by discreteness, determinism and local interaction. This article studies the local behavior of reversible one-dimensional cellular automata by means of the spectral properties of their connectivity matrices. We use the transformation from every one-dimensional cellular automaton to another of neighborhood size 2 to generalize the results exposed in this paper. In particular we prove that the connectivity matrices have a single positive eigenvalue equal to 1; based on this result we also prove the main result of this paper: the idempotent behavior of these matrices. This property is an important feature for detecting which one-dimensional cellular automata are reversible. Hence we present a procedure using the eigenvectors of these matrices to find the inverse rule for a given reversible one-dimensional cellular automaton. Finally illustrative examples are provided.

Title: Solitones en el autómata celular unidimensional regla 110

Site: Sección Computación, CINVESTAV, 2002. [HTML or PDF] spanish workpaper

Author: Genaro J. Martínez

Abstract: Se estudia el fenómeno solitón en el autómata celular unidimensional regla 110. Se presentan las propiedades generales del espacio de evoluciones y sus estructuras periódicas, útiles para la generación de choques y solitones, mostrando el procedimiento para reproducir solitones bajo ciertas condiciones. Finalmente se presenta un caso especial donde un seudo-solitón puede cambiar su forma y regresar a su estado original conservando su velocidad.

Title: Encontrando solitones en el autómata celular regla 110

Site: Sección Computación, CINVESTAV, 2002. [HTML from UNAM] spanish workpaper

Author: Genaro J. Martínez

Abstract: El fenómeno solitón es una área de la física bien fundamentada, es este reporte se muestra como un autómata celular en una dimensión puede simular este fenómeno. Una característica importante es que es un sistema dinámico discreto fácil implementar computacionalmente.

Title: ATLAS: Collisions of gliders as phases of ether in rule 110

Site: Departamento de Microcomputadoras, Universidad Autónoma de Puebla, México, 2001. [HTML workpaper]

Authors: Genaro J. Martínez and Harold V. McIntosh