Papers, chapters, and beyond
All papers are available in PDF format.
Title: Synchronizing a virtual cellular automaton collider
Journal: IEEE Explore, 2022 Tenth International Symposium on Computing and Networking (CANDAR), Himeji, Japan, pp. 1-10, 2023. [PDF soon]
Authors: Oswaldo L. Barrientos, Genaro J. Martínez, Andrew Adamatzky, Shigeru Ninagawa
URL: https://ieeexplore.ieee.org/document/10035245
Abstract: Cellular automata have been a topic of great interest in unconventional computation theory for its architecture: simple but capable of producing complex structures with a dynamic behavior and massive parallel computation. Collision-based computing with multiple reactions is a way to explore such capacities. Following this logic, a virtual collider was proposed as a way to develop computers by using the elementary cellular automaton rule 110. The main result in this paper is the computational implementation of the virtual collider, capable of supporting the execution of three simultaneous cyclotrons. The lateral cyclotrons handle particles which are injected to the main collider to perform a computation. Particles move until they reach a contact point, where they trigger a series of chained reactions among hundreds of thousands of cells. Using this program, we present a configuration of the collider that simulates the execution of the first nine transitions of a cyclic tag system using rule 110 particles, the largest simulation of this kind to date.
Title: Some Notes About the Game of Life Cellular Automaton
Book: The Mathematical Artist, In: Das, S., Roy, S., Bhattacharjee, K. (eds). Emergence, Complexity and Computation, vol 45, pages 93-104. Springer, Cham., 2022. [PDF soon]
Authors: Genaro J. Martínez, Andrew Adamatzky, Juan C. Seck-Tuoh-Mora
URL: https://link.springer.com/chapter/10.1007/978-3-031-03986-7_4
Abstract: This is a short review of selected results related to John Conway’s Game of Life cellular automaton. The review is base on our participation in the “A Tribute to Conway: A Lectures Series on the Memory of John Horton Conway” (https://youtu.be/WqKkmfOt9Ww), celebrated virtually in India and organized by Sukanta Das and Kamalika Bhattacharjee in 2020. Additional contributions are made by Andrew Adamatzky and Juan C. Seck-Tuoh-Mora.
Title: Unconventional Computing Art in Cellular Automata
Book: Unconventional Computing, Arts, Philosophy. World Scientific Publishing Company, chapter 16, pages 291-303, 2022. [PDF soon]
Authors: Genaro J. Martínez, Andrew Adamatzky, Marcin J. Schroeder
URL: https://www.worldscientific.com/doi/abs/10.1142/9789811257155_0016
Abstract: The exploration of unconventional computing in its diverse forms is not only, and not primarily a result of the natural human pursuit for innovation but rather a response to challenges faced by the current information technology. Some of these challenges are not new, e.g. the expected end of applicability of Moore’s Law or the von Neumann bottleneck in the transfer of data between the CPU (central processing unit) and RAM (random-access memory). However, the bottleneck in the past was just a nuisance, but at present the need for massive processing of synaptic weights in the network for machine learning which requires multiple transfer makes this primary tool of AI (artificial intelligence) inefficient and hopeless in the competition with the natural, biological systems of information processing.
Title: A New Algorithm Inspired on Reversible Elementary Cellular Automata for Global Optimization
Journal: IEEE Access, (10), 112211-112229, 2022. [PDF soon]
Authors: Juan C. Seck-Tuoh-Mora, Omar Lopez-Arias, Norberto Hernández-Romero, Genaro J. Martínez, Valeria Volpi-León
URL: https://ieeexplore.ieee.org/document/9927178
Abstract: This work presents a new global optimization algorithm of functions inspired by the dynamic behavior of reversible cellular automata, denominated Reversible Elementary Cellular Automata Algorithm (RECAA). This algorithm adapts the reversible evolution rules in elementary cellular automata (in one dimension and only with two states) to work with vectors of real values to realize optimization tasks. The originality of RECAA lies in adapting the dynamic of the reversible elementary cellular automata to perform exploration and exploitation actions in the optimization process. This work shows that diversity in cellular automata behaviors (in this case, reversibility) is useful to define new metaheuristics to solve optimization problems. The algorithm is compared with 15 recently published metaheuristics that recognized for their good performance, using 50 test functions in 30, 500, and with a fixed number of dimensions, and the CEC 2022 benchmark suit. Additionally, it is shown that RECAA has been applied in 3 engineering problems. In all the experiments, RECAA obtained satisfactory results. RECAA was implemented in MATLAB, and its source code can be consulted in GitHub. https://github.com/juanseck/RECAA
Title: Computing with Modular Robots
Journal: International Journal of Unconventional Computing, 17(1-2), 31-60, 2022. [PDF].
Authors: Genaro J. Martínez, Andrew Adamatzky, Ricardo Q. Figueroa, Eric Schweikardt, Dmitry A. Zaitsev, Ivan Zelinka, Luz N. Oliva-Moreno
Abstract: Propagating patterns are used to transfer and process information in chemical and physical prototypes of unconventional computing devices. Logical values are represented by fronts of traveling diffusive, trigger or phase waves. We apply this concept of pattern based computation to develop experimental prototypes of computing circuits implemented in small modular robots. In the experimental prototypes the modular robots Cubelets are concatenated into channels and junction. The structures developed by Cubelets propagate signals in parallel and asynchronously. The approach is illustrated with a working circuit of a one-bit full adder. Complementarily a formalization of these constructions are developed across Sleptsov nets. Finally, a perspective to swarm dynamics is discussed.
Title: On Wave-Based Majority Gates with Cellular Automata
Book: Handbook of Unconventional Computing, World Scientific Publishing Company, chapter 9, pages 271-288, 2021. [PDF].
Authors: Genaro J. Martínez, Andrew Adamatzky, Shigeru Ninagawa, Kenichi Morita
URL: https://www.worldscientific.com/doi/10.1142/9789811235740_0009
Abstract: We demonstrate a discrete implementation of a wave-based majority gate in a chaotic Life-like cellular automaton. The gate functions via controlling of patterns' propagation into stationary channels. The gate presented is realizable in many living and non-living substrates that show wave-like activity of its space-time dynamics or pattern propagation. In the gate a symmetric pattern represents a binary value 0 while a non-symmetric pattern represents a binary value 1. Origination of the patterns and their symmetry type are encoded by the particle reactions at the beginning of computation. The patterns propagate in channels of the gate and compete for the space at the intersection of the channels. We implement 3-inputs majority gates using a W topology showing additional implementations of 5-inputs majority gates and one tree (cascade) majority gate.
Title: Following the spacial dynamics of COVID-19 in Mexico and some notes
Arxiv: arXiv:2109.05183 [physics.soc-ph], 2021. [PDF].
Europe PMC: PPR: PPR414436, 2021. [PDF].
Authors: Genaro J. Martínez, Magali Cárdenas-Tapia, Ricardo A. Tena-Nuñez, Adriana de la Paz Sánchez-Moreno
URL: https://arxiv.org/abs/2109.05183
Abstract: Actually, after one year it is recognized that the evolution of COVID-19 is different in each country or region around the world. In this paper, we do a revision to the date about COVID-19 evolution in Mexico, we explain where the main epicenter and states with most high impact. Mexico has a particular geographical position in the American continent because it is a natural bridge between the USA and Latin America, that represents a special point of propagation because between other facts this virus is transported by people of different nationalities migrating to the USA. The research in this paper helps to understand why Mexico is one of the countries with the most high mortality impact by this new virus and how the lockdown works in the population. Finally, we give a practical perspective as this evolution is a complex system.
Title: Visualization of the Computation Process of a Universal Register Machine
Journal: Journal of Cellular Automata, 15(5-6), 359-376, 2021. [PDF].
Authors: Shigeru Ninagawa, Genaro J. Martínez
Abstract: Universal register machine, a formal model of computation, can be emulated on the array of the Game of Life, a two-dimensional cellular automaton. We perform spectral analysis on the computation dynamical process of the universal register machine on the Game of Life. The array is divided into small sectors and the power spectrum is calculated from the evolution in each sector. The power spectrum can be classified into four categories by its shape; null, white noise, sharp peaks, and power law. By representing the shape of power spectrum by a mark, we can visualize the activity of the sector during the computation process. For example, the track of pulse moving between components of the universal register machine and the position of frequently modified registers can be identified. This method can expose the functional difference in each region of computing machine.
Title: Random expansion method for the generation of complex cellular automata
Journal: Information Sciences, 549, 310–327, 2021. [PDF]
Authors: Juan C. Seck-Tuoh-Mora, Norberto Hernández-Romero, Joselito Medina-Marín, Genaro J. Martínez, Irving Barragan-Vite
URL: https://www.sciencedirect.com/science/article/abs/pii/S0020025520311294
Abstract: The complex behaviors in cellular automata have been widely developed in recent years to generate and analyze automata that produce space-moving patterns or gliders that interact in a periodic background. This type of automata has been frequently found either by con- ducting an exhaustive search or through a meticulous construction of the evolution rule. In this study, the specification of cellular automata with complex behaviors was obtained by utilizing randomly generated specimens. In particular, it was proposed that a cellular automaton of n states should be specified at random and then extended to another automaton with a higher number of states so that the original automaton operates as a periodic background where the additional states serve to define the gliders. Moreover, this study presents an explanation of this method. Furthermore, the random way of defining complex cellular automata was studied by using mean-field approximations for various states and local entropy measures. This specification was refined with a genetic algorithm to obtain specimens of a higher degree of complexity. By adopting this methodology, it was possible to generate complex automata with hundreds of states, demonstrating the fact that randomly defined local interactions with multiple states can construct complexity.
Title: Brief Notes and History Computing in Mexico during 50 years
Journal: International Journal of Parallel, Emergent and Distributed Systems, 35(2), 185-192, 2020. [PDF]. Special issue: A Half Century of Computing.
Authors: Genaro J. Martínez, Juan C. Seck Tuoh Mora, Sergio V. Chapa Vergara, Christian Lemaitre
URL: https://www.tandfonline.com/doi/full/10.1080/17445760.2019.1608990
Abstract: The history of computing in Mexico cannot be thought without the name of Prof. Harold V. McIntosh (1929–2015). For almost 50 years, in Mexico, he contributed to the development of computer science with wide international recognition. Approximately in 1964, McIntosh began working in the Physics Department of the Advanced Studies Center (CIEA) of the National Polytechnic Institute (IPN), now called CINVESTAV. In 1965, at the National Center of Calculus (CeNaC), he was a founding member of the Master in Computing, first in Latin America. With the support of Mario Baez Camargo and Enrique Melrose, McIntosh continues his research of Martin-Baltimore Computer Center and University of Florida at IBM 709.
Title: Fungal automata
Journal: Complex Systems, 29(4), 759–778, 2020. [PDF]
Authors: Andrew Adamatzky, Eric Goles, Genaro J. Martínez, Michail-Antisthenis Tsompanas, Martin Tegelaar, Han A.B. Wosten
URL: https://www.complex-systems.com/abstracts/v29_i04_a02/
Abstract: We study a cellular automaton (CA) model of information dynamics on a single hypha of a fungal mycelium. Such a filament is divided in compartments (here also called cells) by septa. These septa are invaginations of the cell wall and their pores allow for the flow of cytoplasm between compartments and hyphae. The septal pores of the fungal phylum of the Ascomycota can be closed by organelles called Woronin bodies. Septal closure is increased when the septa become older and when exposed to stress conditions. Thus, Woronin bodies act as informational flow valves. The one-dimensional fungal automaton is a binary-state ternary neighborhood CA, where every compartment follows one of the elementary cellular automaton (ECA) rules if its pores are open and either remains in state 0 (first species of fungal automata) or its previous state (second species of fungal automata) if its pores are closed. The Woronin bodies closing the pores are also governed by ECA rules. We analyze a structure of the composition space of cell-state transition and pore-state transition rules and the complexity of fungal automata with just a few Woronin bodies, and exemplify several important local events in the automaton dynamics.
Title: Computational universality of fungal sandpile automata
Journal: Physics Letters A, 384(22), 126541, 2020. [PDF]
Authors: Eric Goles, Michail-Antisthenis Tsompanas, Andrew Adamatzky, Martin Tegelaar, Han A.B. Wosten, Genaro J. Martínez
URL: https://www.sciencedirect.com/science/article/pii/S0375960120304084
Abstract: Hyphae within the mycelia of the ascomycetous fungi are compartmentalised by septa. Each septum has a pore that allows for inter-compartmental and inter-hyphal streaming of cytosol and even organelles. The compartments, however, have special organelles, Woronin bodies, that can plug the pores. When the pores are blocked, no flow of cytoplasm takes place. Inspired by the controllable compartmentalisation within the mycelium of the ascomycetous fungi we designed two-dimensional fungal automata. A fungal automaton is a cellular automaton where communication between neighbouring cells can be blocked on demand. We demonstrate computational universality of the fungal automata by implementing sandpile cellular automata circuits there. We reduce the Monotone Circuit Value Problem to the Fungal Automaton Prediction Problem. We construct families of wires, cross-overs and gates to prove that the fungal automata are P-complete.
Title: On Patterns and Dynamics of Rule 22 Cellular Automaton
Journal: Complex Systems 28(2), 125-174, 2019. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Rolf Hoffmann, Dominique Désérable, Ivan Zelinka
URL: https://www.complex-systems.com/abstracts/v28_i02_a01/
Abstract: Three-cell neighborhood, binary cell state, where a cell takes state “1” if there is exactly one neighbor, including the cell itself, in state 1. In Boolean terms, the cell state transition is an XOR function of three cell states. In physico–chemical terms, the rule might be seen as describing propagation of self-inhibiting quantities/species. Spacetime dynamics of rule 22 demonstrate nontrivial patterns and quasi-chaotic behavior. We characterize the phenomena observed in this rule using mean field theory, attractors, de Bruijn diagrams, subset diagrams, filters, fractals and memory.
Title: A Turing Machine Constructed with Cubelets Robots
Journal: Journal of Robotics, Networking and Artificial Life 5(4), 1-4, 2019. [PDF]
Authors: Ricardo Q. Figueroa, Daniel A. Zamorano, Genaro J. Martínez, Andrew Adamatzky
URL: https://www.atlantis-press.com/journals/jrnal/125905739/
Post Modular Robotics: Can you make a computer out of Cubelets?
Abstract: We describe the design and implementation of a modular and distributed robot that physically simulates functioning of a 2-symbols Turing machine. The robot is constructed with Cubelets (small autonomous robot-cubes used for teaching basic robotics and programming for kids) and Lego® bricks (thus the robot is called CULET). The Cubelets robotic blocks allow for a high level programming: instead of a traditional code, the robots are programmed by assembling various elementary blocks of robots together. We illustrate how read and write operations are physically implemented by the CULET.
Title: Universal One-Dimensional Cellular Automata Derived from Turing Machines
Journal: International Journal of Unconventional Computing 14(2), 121-138, 2019. [PDF]
Authors: Sergio J. Martínez, Iván M. Mendoza, Genaro J. Martínez, Shigeru Ninagawa
Abstract: Universality in cellular automata theory is a central problem studied and developed from their origins by John von Neumann. In this paper, we present an algorithm where any Turing machine can be converted to one-dimensional cellular automaton with a 2-linear time and display its spatial dynamics. Three particular Turing machines are converted in three universal one-dimensional cellular automata, they are: binary sum, rule 110 and a universal reversible Turing machine.
Title: Conservative Computing in a One-dimensional Cellular Automaton with Memory
Journal: Journal of Cellular Automata 13(4), 325-346, 2018. [PDF]
Authors: Genaro J. Martínez, Kenichi Morita
Abstract: We propose a scheme to simulate Fredkin gates in a one-dimensional cellular automaton with memory by collision of particles, which is a moving pattern in this cellular space. Operations by collisions are confined in a black box with ballistic interaction, solitons and other collisions. We made a systematic analysis of binary collisions, i.e., collisions of two particles with different phases. They are used for handling these particles and obtaining the final outputs.
Title: Research Frontier in Chaos Theory and Complex Networks
Journal: Entropy 20(10), 734, 2018. [PDF]
Authors: Guanrong Chen, Marius-F. Danca, Xiaosong Yang, Genaro J. Martínez, Hai Yu
URL: https://www.mdpi.com/1099-4300/20/10/734
Abstract: In recent years, as natural and social sciences are rapidly evolving, classical chaos theory and modern complex networks studies are gradually interacting each other with a great joined development. In particular, the notion of complex networks is becoming a self-contained interdiscipline. Network science as a whole has merged with the basic research and real-world applications of chaos theory, forming one of the most active fields in cognitive science, data science, cloud computing, social sciences, artificial intelligence, and the like. The theme of this special Issue is on the current research efforts and progress in the promising field of chaos theory as well as complex networks. It comprises 17 selected manuscripts primarily involving four types of subjects, namely theoretical and characteristic analysis of chaotic dynamics, control systems and synchronization, complex networks, and chaos-based applications.
Title: Recognizing complex behavior emerging from chaos in cellular automata
Book: Unifying Themes in Complex Systems IX. In: Morales, A., Gershenson, C., Braha, D., Minai, A., Bar-Yam, Y. (eds.). Springer Proceedings in Complexity, pp. 82-90, 2018. [PDF]
Authors: Gabriela M. González, Genaro J. Martínez, M.A. Aziz Alaoui, Fangyue Chen
URL: https://link.springer.com/chapter/10.1007/978-3-319-96661-8_8
Abstract: In this research, we explain and show how a chaotic system displays non-trivial behavior as a complex system. This result is reached modifying the chaotic system using a memory function, which leads to a new system with elements of the original function which are not evident in a first step. We proof that this phenomenology can be apprehended selecting a typical chaotic function in the domain of elementary cellular automata to discover complex dynamics. By numerical simulations, we demonstrate how a number of gliders emerge in this automaton and how some controlled subsystems can be designed within this complex system.
Title: Logical Gates via Gliders Collisions
Book: Reversibility and Universality: Essays Presented to Kenichi Morita on the Occasion of his 70th Birthday, Springer, (A. Adamatzky Ed.), chapter 9, pages 199-220, 2018. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita
URL: https://link.springer.com/chapter/10.1007%2F978-3-319-73216-9_9
Abstract: An elementary cellular automaton with memory is a chain of finite state machines (cells) updating their state simultaneously and by the same rule. Each cell updates its current state depending on current states of its immediate neighbours and a certain number of its own past states. Some cell-state transition rules support gliders, compact patterns of non-quiescent states translating along the chain. We present designs of logical gates, including reversible Fredkin gate and controlled NOT gate, implemented via collisions between gliders.
Title: Simple networks on complex cellular automata: From de Bruijn diagrams to jump-graphs
Book: Swarm Dynamics as a Complex Network, Springer, (I. Zelinka and G. Chen Eds.), chapter 12, pages 241-264, 2018. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Bo Chen, Fangyue Chen, Juan C.S.T. Mora
URL: https://link.springer.com/chapter/10.1007/978-3-662-55663-4_12
Abstract: We overview networks which characterise dynamics in cellular automata. These networks are derived from one-dimensional cellular automaton rules and global states of the automaton evolution: de Bruijn diagrams, subsystem diagrams, basins of attraction, and jump-graphs. These networks are used to understand properties of spatially-extended dynamical systems: emergence of non-trivial patterns, self-organisation, reversibility and chaos. Particular attention is paid to networks determined by travelling self-localisations, or gliders.
Title: Meet the Editors: Genaro J. Martínez
Journal: Journal of Cellular Automata 13(1), 179-180, 2017. [PDF]
Authors: Genaro J. Martínez
URL: http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-13-number-1-2-2018/
Title: Graphs Related to Reversibility and Complexity in Cellular Automata
Book: Encyclopedia of Complexity and Systems Science. Springer, Berlin, Heidelberg, (R.A. Meyers, Ed.), chapter 24, pages 479-492, 2017. [PDF]
Author: Juan C. Seck Tuoh Mora, Genaro J. Martínez
URL: https://link.springer.com/referenceworkentry/10.1007%2F978-3-642-27737-5_677-1
Abstract: Concepts from graph theory have been used in the local and global analysis and characterization of a cellular automaton (CA). In particular, De Bruijn graph, pair graph, subset graph, and cycle graph have been employed to represent the local cell-state transition rules and their induced global transformations. These graphs are useful to analyze, classify, and construct interesting dynamics in one-dimensional CAs. Reversibility and complexity have been a common field of study where graphic tools have been successfully applied.
Title: Glider Collisions in Hybrid Cellular Automaton with Memory Rule (43,74)
Journal: International Journal of Bifurcation and Chaos 27(6), 1750082-32, 2017. [PDF]
Authors: Bo Chen, Fangyue Chen, Genaro J. Martínez
URL: http://www.worldscientific.com/doi/abs/10.1142/S0218127417500821
Abstract: In the case of one-dimensional cellular automata (CA), a hybrid CA (HCA) is the member whose evolution of the cells is dependent on non-unique global functions. The HCAs exhibit a wide range of traveling and stationary localisations in their evolution. We focus on HCA with memory (HCAM) because they produce a host of gliders and complicated glider collisions by introducing the hybrid mechanism. In particular, we undertake an exhaustive search of gliders and describe their collisions using quantitative approach in HCAM(43,74). By introducing the symbol vector space and exploiting the mathematical definition of HCAM, we present an analytical method of complex asymptotic dynamics of the gliders.
Title: East-West paths to unconventional computing
Journal: Progress in Biophysics and Molecular Biology 131, 469-493, 2017. [PDF]
Authors: Andrew Adamatzky, Selim Akl, Mark Burgin, Cristian S. Calude, José Félix Costa, Mohammad Mahdi Dehshibi, Yukio-Pegio Gunji, Zoran Konkoli, Bruce MacLennan, Bruno Marchal, Maurice Margenstern, Genaro J. Martínez, Richard Mayne, Kenichi Morita, Andrew Schumann, Yaroslav D. Sergeyev, Georgios Ch. Sirakoulis, Susan Stepney, Karl Svozil, Hector Zenil
URL: http://www.sciencedirect.com/science/article/pii/S0079610717301177
Abstract: Unconventional computing is about breaking boundaries in thinking, acting and computing. Typical topics of this non-typical field include, but are not limited to physics of computation, non-classical logics, new complexity measures, novel hardware, mechanical, chemical and quantum computing. Unconventional computing encourages a new style of thinking while practical applications are obtained from uncovering and exploiting principles and mechanisms of information processing in and functional properties of, physical, chemical and living systems; in particular, efficient algorithms are developed, (almost) optimal architectures are designed and working prototypes of future computing devices are manufactured. This article includes idiosyncratic accounts of ‘unconventional computing’ scientists reflecting on their personal experiences, what attracted them to the field, their inspirations and discoveries.
Title: A Computation in a Cellular Automaton Collider Rule 110
Book: Advances in Unconventional Computing: Volume I Theory, Springer, (A. Adamatzky, Ed.), chapter 15, pages 391-428, 2017. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh
Videos: https://www.youtube.com/watch?v=i5af0tQiVd4, https://www.youtube.com/watch?v=kciEa6cF1QQ&t=30s, https://www.youtube.com/watch?v=HFJlbz7qATg, https://www.youtube.com/watch?v=JElxQt32Odc&t=6s
Abstract: A cellular automaton collider is a finite state machine build of rings of one-dimensional cellular automata. We show how a computation can be performed on the collider by exploiting interactions between gliders (particles, localisations). The constructions proposed are based on universality of elementary cellular automaton rule 110, cyclic tag systems, supercolliders, and computing on rings.
Title: 1/f Noise in the Computation Process by Rule 110
Journal: Journal of Cellular Automata 12(1-2), 47-61, 2017. [PDF]
Authors: Shigeru Ninagawa, Genaro J. Martínez
Abstract: An elementary cellular automaton rule 110 supports universal computation by emulating cyclic tag system and its evolution starting from random initial configuration exhibits 1/f noise. In this research we investigate the power spectra of the computation process of rule 110 emulating cyclic tag system. As a result, 1/f-type power spectra are observed in the most actively interacting area among the whole array, while in the less active area the power spectra exhibit Lorentzian, Brownian or periodic types. These results suggest a possibility that the dynamics ac- companied with 1/f noise and the one capable of performing computation overlap each other in cellular automaton rule space.
Title: On plant roots logical gates
Journal: Biosystems 156(157), 40-45, 2017. [PDF]
Authors: Andrew Adamatzky, Georgios Ch. Sirakoulis, Genaro J. Martínez, Frantisek Baluska, Stefano Mancuso
URL: http://www.sciencedirect.com/science/article/pii/S0303264716302374
Abstract: Theoretical constructs of logical gates implemented with plant roots are morphological computing asynchronous devices. Values of Boolean variables are represented by plant roots. A presence of a plant root at a given site symbolises the logical True, an absence the logical False. Logical functions are calculated via interaction between roots. Two types of two-inputs–two-outputs gates are proposed: a gate ⟨x,y⟩ → ⟨xy,x+y⟩ where root apexes are guided by gravity and a gate ⟨x,y⟩ → ⟨~xy,x⟩ where root apexes are guided by humidity. We propose a design of binary half-adder based on the gates.
Title: Welch sets for random generation and representation of reversible one-dimensional cellular automata
Journal: Information Sciences 382(383), 81-95, 2017. [PDF]
Authors: Juan C.S.T. Mora, Joselito M. Marina, Norberto H. Romero, Genaro J. Martínez, Irving B. Vite
URL: http://www.sciencedirect.com/science/article/pii/S0020025516319193
Abstract: Reversible one-dimensional cellular automata are studied from the perspective of Welch Sets. This paper presents an algorithm to generate random Welch sets that define a reversible cellular automaton. Then, properties of Welch sets are used in order to establish two bipartite graphs describing the evolution rule of reversible cellular automata. The first graph gives an alternative representation for the dynamics of these systems as block mappings and shifts. The second graph offers a compact representation for the evolution rule of reversible cellular automata. Both graphs and their matrix representations are illustrated by the generation of random reversible cellular automata with 6 and 18 states.
Title: Block Transformation of Hybrid Cellular Automata
Journal: Journal of Applied Analysis and Computation 6(4), 1164-1179, 2016. [PDF]
Authors: Bo Chen, Fangyue Chen, Junbiao Guan, Genaro J. Martínez
URL: http://jaac.ijournal.cn/ch/reader/view_abstract.aspx?file_no=JAAC-6-4-fangyuechen
Abstract: By introducing a sequence-block transformation and vector-block transformation, we explore the dynamical properties of hybrid cellular automation (HCA) and hybrid cellular automation with memory (HCAM) in the framework of symbolic dynamics. As the local evolution rules of HCA and HCAM are not-uniform, the new uniform cellular automata (CAs) with multiple states are constructed by specific the block transformations. Furthermore, because the new CA rules are topologically conjugate with the originals, the complex dynamics of the HCA and HCAM rules can be investigated via the new CA rules.
Title: Gliders in One-Dimensional Cellular Automata
Book: Designing Beauty: The Art of Cellular Automata, Springer, (A. Adamatzky, G. Martínez, Eds.), chapter 29, pages 167-172, 2016. [PDF]
Author: Genaro J. Martínez
URL: http://link.springer.com/chapter/10.1007/978-3-319-27270-2_29
Abstract: Gliders are non-trivial complex patterns emerging typically in complex cellular automata (CA). The most famous glider (mobile self-localizations, particles, waves) is the five-live cells glider moving diagonally in five steps in the two-dimensional CA Conway’s Game of Life. Pictures shown here are space-time configurations of elementary CA rule 110. Rule 110 CA is universal because it simulates a cyclic tag system. The cyclic tag system if programmed into an initial configuration of CA. The processing of just four values on the tape of this machine requires over three millions of cells.
Title: A Symbolic Dynamics Perspective of The Game of Three-Dimensional Life
Journal: Complex Systems 25(1), 51-77, 2016. [PDF]
Authors: Bo Chen, Fangyue Chen, Genaro J. Martínez, Danli Tong
URL: http://www.complex-systems.com/abstracts/v25_i01_a04.html
Abstract: The games of three-dimensional life are the extension models of Con- way’s game of life. Under the framework of symbolic dynamics, we undertake an analysis of the complexity of gliders in three-dimensional life rules by the directed graph representation and transition matrix. More specifically, the gliders here are topologically mixing and possess the positive topological entropy on their concrete subsystems. Finally, the method presented in this paper is also applicable to other gliders in different D-dimensions.
Title: A Symbolic Dynamics Perspective of Rock-Paper-Scissor Game
Journal: Journal of Nonlinear Systems and Applications 5(1), 35-46, 2016. [PDF]
Authors: Danli Tong, Bo Chen, Fangyue Chen, Genaro J. Martínez
URL: http://jnsaonline.watsci.org/contents2016/v5n1.html
Abstract: The Rock-Paper-Scissor (RPS) games are investigated under the framework of symbolic dynamics. It is of interest that several Chua’s nonlinear dynamics analytical methods are appropriate for the RPS game rule. And a series of dynamical properties on the its subsystems are explored by the directed graph and transition matrix. Moreover, the method presented in this paper is also applicable to other game rules.
Title: Obituary: Prof. Harold V. McIntosh
Journal: Journal of Cellular Automata 11(2-2), 265-269, 2016. [PDF]
Author: Genaro J. Martínez
Abstract: Professor Harold V. McIntosh was a prominent researcher who dedicated his life to Science. He was a big promoter of educating young students in several scientific fields simultaneously, such as physics, history, mathematics, biology, chemistry, and computer science. McIntosh was born in Colorado, USA in 1929 and died last November in Puebla, Mexico. McIntosh's legacy in different scientific fields is an example of dedication, passion and principles, in order to investigate problems from the easiest perspective, with didactic and visual interpretations, to establish later a formal solution. He was a great mentor and inspiration for many generations of students and researchers, and will be always remembered and honoured as a brilliant scientist and an exceptional person.
Title: Recolonisation of USA: Slime Mould on 3D Terrains
Book: Advances in Physarum Machines: Sensing and Computing with Slime Mould, Springer, (A. Adamatzky, Ed.), chapter 16, pages 337-348, 2016. [PDF]
Authors: Andrew Adamatzky, Genaro J. Martínez
URL: http://www.springer.com/kr/book/9783319266619
Abstract: P. polycephalum imitates development of man-made transport networks of a country when configuration of nutrients represents major urban areas. We employ this feature of the slime mould to imitate Mexican migration to USA, which is the Worlds’s largest migration system. In laboratory experiments with 3D Nylon terrains of USA we analyse development of migratory routes from Mexico-USA border to ten urban areas with high concentration of Mexican migrants. From results of laboratory experiments we extract topologies of migratory routes, and highlight a role of elevations in shaping the human movement networks.
Title: Describing Complex Dynamics in Life-Like Rules with de Bruijn Diagrams on Complex and Chaotic Cellular Automata
Journal: Journal of Cellular Automata 11(1), 91-112, 2016. [PDF]
Author: Paulina A. León, Genaro J. Martínez
Abstract: De Bruijn diagrams are useful tools for a systematic analysis of one-dimensional cellular automata (CA), i.e. calculating particular kinds of configurations, ancestors, complex patterns, cycles, Garden of Eden configurations, and formal languages. The de Brujin diagrams are barely employed in two-dimensions because complexity of their calculation increases exponentially.We apply de Bruijn diagrams for analysis of two evolution rules in two dimensions: the Conway’s Game of Life and the quasi-chaotic Diffusion Rule.
Title: Computing with Virtual Cellular Automata Collider
Book: Proceedings of IEEE Technically Co-Sponsored Science and Information Conference, London, UK, pages 62-68, 2015. DOI: 10.1109/SAI.2015.7237127. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh
Abstract: We present computer models of nano-scale computing circuits based on propagation of localised excitations or defects in complexes of polymer chain rings. A cyclotron automata are sets of rings of one-dimensional array of finite states (cellular automata) which exhibits a wide range of travelling localisations (gliders). When information (e.g. values of logical variables) is encoded in the initial positions and velocity vectors of the gliders the cyclotron automata are becoming power abstract machines which execute high-performance computing. The computing is based on collisions between the mobile localisations. We present collisions that emulate basic types of interactions between localisations typical for spatially-extended non-linear media: fusion, particles, elastic collision, and soliton-like collision, all they implement basic computing primitives. Mobile localisations in complex one-dimensional cellular automata are compact sets of non-quiescent patterns translating along evolution space. These non-trivial patterns can be coded as binary strings (regular expressions) or symbols travelling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions and computation.
Title: Majority Gates and Circular Computation in Slime Mould
Book: Proceedings of the European Conference on Artificial Life 2015, p. 18-24, York, UK, 2015. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Richard Mayne, Fangyue Chen, Qinbin He
URL: https://www.cs.york.ac.uk/nature/ecal2015/paper-16.html
Abstract: Slime mould has been proven to be a fruitful living substrate for implementing a wide range of computing circuits from computational geometry to collision-based logical circuits to robot control. It is apparent, however, that constructing work-ing real-time universal processors from the slime mould is non-trivial task. We explore here similarities between development of slime mould protoplasmic tubes, transportation of cytoplasm inside the tubes and dynamics of propagating patterns in cellular automata. Based on these analogies we will propose computing devices realisable in the living slime mould.
Title: On the Dynamics of Cellular Automata with Memory
Journal: Fundamenta Informaticae 137, 1-16, 2015. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Ramon Alonso-Sanz
URL: http://content.iospress.com/articles/fundamenta-informaticae/fi138-1-2-02
Abstract: 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.
Title: Complete Characterization of Structure of Rule 54
Journal: Complex Systems 23(3), 259-293, 2014. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh
URL: http://www.complex-systems.com/abstracts/v23_i03_a04.html
Abstract: The dynamics of the rule 54 one-dimensional, two-state cellular automaton (CA) are a discrete analog of a space-time dynamics of excitations in a nonlinear active medium with mutual inhibition. A cell switches its state 0 to state 1 if one of its two neighbors is in state 1 (propagation of a perturbation), and a cell remains in state 1 only if its two neighbors are in state 0. A lateral inhibition is because a 1-state neighbor causes a 1-state cell to switch to state 0. The rule produces a rich spectrum of space-time dynamics, including gliders and glider guns just from four primitive gliders. We construct a catalog of gliders and describe them by tiles. We calculate a subset of regular expressions \Phi_{R54} to encode gliders. The regular expressions are derived from de Bruijn diagrams, tile- based representation of gliders, and cycle diagrams sometimes. We con- struct an abstract machine that recognizes regular expressions of gliders in rule 54 and validate \Phi_{R54}. We also propose a way to code initial con- figurations of gliders to depict any type of collision between the gliders and explore self-organization of gliders, formation of larger tiles, and soliton-like interactions of gliders and computable devices.
Title: Compression-Based Analysis of Cyclic Tag System Emulated by Rule 110
Journal: Journal of Cellular Automata 9(1), 23-35, 2014. [PDF]
Authors: Shigeru Ninagawa, Genaro J. Martínez
Abstract: An elementary cellular automaton rule 110 supports universal computation by emulating cyclic tag system. We employ Lempel-Ziv (LZ) complexity as a measure of compressibility and calculate it during the cyclic tag system emulation process by rule 110. We observe the stepwise decline of LZ complexity during the process. That is caused by the conversion of appendants, symbols added onto the end of the tape, into moving data and the elimination of appendants. These phenomena occur if a cyclic tag system emulation process is solving a problem described by a recursive language.
Title: Designing Complex Dynamics in Cellular Automata with Memory
Journal: International Journal of Bifurcation and Chaos 23(10), 1330035-131, 2013. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Ramon Alonso-Sanz
URL: http://www.worldscientific.com/doi/abs/10.1142/S0218127413300358
Abstract: Since their inception at `Macy conferences’ in later 1940s complex systems remain the most controversial topic of inter-disciplinary sciences. The term `complex system' is the most vague and liberally used scientific term. Using elementary cellular automata (ECA), and exploiting the CA classification, we demonstrate elusiveness of `complexity' by shifting space-time dynamics of the automata from simple to complex by enriching cells with `memory’. This way, we can transform any ECA class to another ECA class -- without changing skeleton of cell-state transition function --- and vice versa by just selecting a right kind of memory. A systematic analysis display that memory helps `discover' hidden information and behaviour on trivial -- uniform, periodic, and non-trivial -- chaotic, complex -- dynamical systems.
Title: A Note on Elementary Cellular Automata Classification
Journal: Journal of Cellular Automata 8(3-4), 233-259, 2013. [PDF]
Author: Genaro J. Martínez
Abstract: We overview and compare classifications of elementary cellular automata, including Wolfram's, Wuensche's, Li and Packard, communication complexity, power spectral, topological, surface, compression, lattices, and morphological diversity classifications. This paper summarises several classifications of elementary cellular automata (ECA) and compares them with a newly proposed one, that induced by endowing rules with memory.
Title: Logic gates and complex dynamics in a hexagonal cellular automaton: the Spiral rule
Journal: Journal of Cellular Automata 8(1-2), 53-71, 2013. [PDF]
Authors: Rogelio Basurto, Paulina A. León, Genaro J. Martínez, Juan C. Seck-Tuoh-Mora
Abstract: In previous works, hexagonal cellular automata (CA) have been studied as a variation of the famous Game of Life CA, mainly for spiral phenomena simulations; where the most interesting constructions are related to the Belousov-Zhabotinsky reaction. In this paper, we analyse a special kind of hexagonal CA, {\it Spiral rule}. Such automaton shows a non-trivial complex behaviour related to discrete models of reaction-diffusion chemical media, dominated by spiral guns which easily emerge from random initial conditions. The computing capabilities of this automaton are shown by means of logic gates. These are defined by collisions between mobile localizations. Also, an extended classification of complex self-localisation patterns is presented, including some self-organised patterns.
Title: Bio-Imitation of Mexican Migration Routes to the USA with Slime Mould on 3D Terrains
Journal: Journal of Bionic Engineering 10(2), 242-250, 2013. [PDF]
Authors: Andrew Adamatzky, Genaro J. Martínez
URL: http://www.sciencedirect.com/science/article/pii/S1672652913602206
Abstract: Plasmodium of Physarum polycephalum (P. polycephalum) is a large single cell visible by an unaided eye. It shows sophisticated behavioural traits in foraging for nutrients and developing an optimal transport network of protoplasmic tubes spanning sources of nutrients. When placed in an environment with distributed sources of nutrients the cell ‘computes’ an optimal graph spanning the nutrients by growing a network of protoplasmic tubes. P. polycephalum imitates development of man-made transport networks of a country when configuration of nutrients represents major urban areas. We employed this feature of the slime mould to imitate mexican migration to USA. The Mexican migration to USA is the World's largest migration system. We bio-physically imitated the migration using slime mould P. polycephalum. In laboratory experiments with 3D Nylon terrains of USA we imitated development of migratory routes from Mexico-USA border to ten urban areas with high concentration of Mexican migrants. From results of laboratory experiments we extracted topologies of migratory routes, and highlighted a role of elevations in shaping the human movement networks.
Title: Computation and Universality: Class IV versus Class III Cellular Automata
Journal: Journal of Cellular Automata 7(5-6), 393-430, 2013. [PDF]
Authors: Genaro J. Martínez, Juan C. Seck-Tuoh-Mora, Hector Zenil
Abstract: This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram’s classification) are capable of (Turing universal) computation. We explore some chaotic CA (believed to belong to Class III) reported over the course of the CA history, that may be candidates for universal computation, hence spurring the discussion on Turing universality on both Wolfram’s classes III and IV.
Title: Emergence of density dynamics by surface interpolation in elementary cellular automata
Journal: Communications in Nonlinear Science and Numerical Simulation 19(4), 941-966, 2013. [PDF]
Authors: Juan C. Seck-Tuoh-Mora, Joselito Medina Marin, Genaro J. Martínez, Norberto Hernández Romero
URL: http://www.sciencedirect.com/science/article/pii/S1007570413003638
Abstract: A classic problem in elementary cellular automata (ECAs) is the specification of numerical tools to represent and study their dynamical behaviour. Mean field theory and basins of attraction have been commonly used; however, although the first case gives the long term estimation of density, frequently it does not show an adequate approximation for the step-by-step temporal behaviour; mainly for non-trivial behaviour. In the second case, basins of attraction display a complete representation of the evolution of an ECA, but they are limited up to configurations of 32 cells; and for the same ECA, one can obtain tens of basins to analyse. This paper is devoted to represent the dynamics of density in ECAs for hundreds of cells using only two surfaces calculated by the nearest-neighbour interpolation. A diversity of surfaces emerges in this analysis. Consequently, we propose a surface and histogram based classification for periodic, chaotic and complex ECA.
Title: Expressiveness of Elementary Cellular Automata
Journal: International Journal of Modern Physics C 24(3), 1350010-14, 2013. [PDF]
Authors: Markus Redeker, Andrew Adamatzky, Genaro J. Martínez
URL: http://www.worldscientific.com/doi/abs/10.1142/S0129183113500101
Abstract: We investigate expressiveness, a parameter of one-dimensional cellular automata, in the context of simulated biological systems. The development of elementary cellular automata is interpreted in terms of biological systems, and biologically inspired parameters for biodiversity are applied to the configurations of cellular automata. This article contains a survey of the Elementary Cellular Automata in terms of their expressiveness and an evaluation whether expressiveness is a meaningful term in the context of simulated biology.
Title: Wolfram's Classification and Computation in Cellular Automata Classes III and IV
Book: Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science (Hector Zenil Ed.), Springer Verlag, chapter 17, pages 237-259, 2013. [PDF]
Authors: Genaro J. Martínez, Juan C. Seck-Tuoh-Mora, Hector Zenil
URL: http://www.springer.com/physics/complexity/book/978-3-642-35481-6
Abstract: We conduct a brief survey on Wolfram's classification, in particular related to the computing capabilities of Cellular Automata (CA) in Wolfram's classes III and IV. We formulate and shed light on the question of whether Class III systems are capable of Turing universality or may turn out to be "too hot" in practice to be controlled and programmed. We show that systems in Class III are indeed capable of computation and that there is no reason to believe that they are unable, in principle, to reach Turing-completness.
Title: On Soliton Collisions between Localizations in Complex Elementary Cellular Automata: Rules 54 and 110 and Beyond
Journal: Complex Systems 21(2), 117-142, 2012. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Fangyue Chen, Leon Chua
Review: Complexity Can Come from Simplicity, New Kind of Science - Homologus, Homologus: Frontier in Bioinformatics, November 20th, 2013.
URL: http://www.complex-systems.com/abstracts/v21_i02_a02.html
Abstract: In this paper, a single-soliton two-component cellular automaton (CA) model of waves is presented as mobile self-localizations, also known as particles, waves, or gliders, in addition to its version with memory. The model is based on coding sets of strings where each chain represents a unique mobile self-localization. The original soliton models in CAs proposed with filter automata are briefly discussed, followed by solutions in elementary CAs (ECAs) domain with the famous universal ECA rule 110, and reporting a number of new solitonic collisions in ECA rule 54. A mobile self-localization in this study is equivalent to a single soliton because the collisions of the mobile self-localizations studied in this pa- per satisfy the property of solitonic collisions. A specific ECA with memory (ECAM), the ECAM rule \phi_{R9maj:4}, is also presented; it displays single-soliton solutions from any initial codification (including random initial conditions) for a kind of mobile self-localization because such an automaton is able to adjust any initial condition to soliton structures.
Title: Book Review “Exploring Discrete Dynamics (by Andrew Wuensche)”, Luniver Press, 2011.
Journal: Artificial Life, MIT Press, 18(3), 325-328, 2012. [PDF]
Author: Genaro J. Martínez
URL: http://www.mitpressjournals.org/doi/abs/10.1162/artl_r_00068
Abstract: Exploring Discrete Dynamics is a very extended computational and analytic exploration of discrete dynamical systems. The book makes a summary of more than 19 years of results, programming, and research by Andrew Wuensche. In 1992, at the Santa Fe Institute, Wuensche together with Mike Lesser published the celebrated book in cellular automata theory The Global Dynamics of Cellular Automata. This book introduced a reverse algorithm for cellular automata, and presented an Atlas of basin of attraction fields computed by means of the algorithm. Motivated by these results and Kauffman's model of genetic regulatory networks, Wuensche subsequently developed new algorithms for random Boolean networks and discrete dynamical networks in general. His achievements have had a great influence on outstanding researchers such as Stuart Kauffman, Harold V. McIntosh, Andrew Adamatzky, and Christopher Langton, among many others; and hundreds of references in books and research papers.
Title: Physarum Narcotráficum: Mexican Highways and Slime Mould
Book: Bioevaluation of World Transport Networks (Andrew Adamatzky Ed.), World Scientific Press, chapter 12, pages 195-211, 2012. [PDF soon]
Authors: Andrew Adamatzky, Genaro J. Martínez, Sergio V. C. Vergara, René A. Palacio, Christopher R. Stephens
URL: http://www.worldscientific.com/worldscibooks/10.1142/8482
Abstract: We analyse the results of our experimental laboratory approximation of motorways networks with slime mould Physarum polycephalum. Motorway networks of fourteen geographical areas are considered: Australia, Africa, Belgium, Brazil, Canada, China, Germany, Iberia, Italy, Malaysia, Mexico, The Netherlands, UK, USA. For each geographical entity we represented major urban areas by oat flakes and inoculated the slime mould in a capital. After slime mould spanned all urban areas with a network of its protoplasmic tubes we extracted a generalised Physarum graph from the network and compared the graphs with an abstract motorway graph using most common measures. The measures employed are the number of independent cycles, cohesion, shortest paths lengths, diameter, the Harary index and the Randic index. We obtained a series of intriguing results, and found that the slime mould approximates best of all the motorway graphs of Belgium, Canada and China, and that for all entities studied the best match between Physarum and motorway graphs is detected by the Randic index (molecular branching index).
Title: Computing on rings
Book: A computable Universe: Understanding and Exploring Nature as Computation (Hector Zenil Ed.), World Scientific Press, chapter 14, pages 283-302, 2012. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh
Review: Computers Made Out of DNA, Slime and Other Strange Stuff: Particle Collisions, WIRED, Science, April 3, 2013.
URL: http://www.worldscibooks.com/compsci/8306.html
Abstract: In this paper, we will review the features of develop computations based on rings. Particularly, we will analyse what kinds of interaction occur between gliders travelling on a cellular automaton `cyclotron' derived from a catalog of collisions. We will demonstrate that collisions between gliders emulate the basic types of interaction that occur between localizations in non-linear media: fusion, elastic collision, and soliton-like collision. Computational outcomes of a swarm of gliders circling on a one-dimensional torus are analysed via implementation some easy computing models. Gliders in one-dimensional cellular automata are compact groups of non-quiescent patterns translating along automaton lattice. They are cellular-automaton analogous of localizations or quasi-local collective excitations travelling in a spatially extended non-linear medium. So, they can be represented as binary strings or symbols travelling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions. We present a number of complex one-dimensional cellular automata with such features.
Title: Complex Dynamics in Life-like Rules Described with de Bruijn Diagrams: Complex and Chaotic Cellular Automata
Journal: Proceedings of the 2012 International Conference on High Performance Computing & Simulation (HPCS 2012), IEEE Xplore 10.1109/HPCSim.2012.6266919, 245-251, 2012. [PDF]
Authors: Paulina A. León, Genaro J. Martínez, Sergio V. C. Vergara
URL: http://ieeexplore.ieee.org/xpl/abstractKeywords.jsp?arnumber=6266919
Abstract: De Bruijn diagrams have been used as a useful tool for the systematic analysis of one-dimensional cellular automata (CA). They can be used to calculate particular kind of con- figurations, ancestors, complex patterns, cycles, Garden of Eden configurations and formal languages. However, there is few progress in two dimensions because its complexity increases exponentially. In this paper, we will offer a way to explore systematically such patterns by de Bruijn diagrams from initial configurations. Such analysis is concentrated mainly in two evolution rules: the famous Game of Life (complex CA) and the Diffusion Rule (chaotic CA ). We will display some preliminary results and benefits to use de Bruijn diagrams in these CA.
Title: Are motorways rational from slime mould's point of view?
Journal: International Journal of Parallel, Emergent and Distributed Systems 28(3), 1-19, 2012. [PDF]
URL: http://www.tandfonline.com/doi/abs/10.1080/17445760.2012.685884
Book: Bioevaluation of World Transport Networks (Andrew Adamatzky Ed.), World Scientific Press, chapter 18, pages 309-339, 2012.
URL: http://www.worldscientific.com/worldscibooks/10.1142/8482
CERN: http://cds.cern.ch/record/1431780?ln=en
Authors: Andrew Adamatzky, Selim Akl, Ramon Alonso-Sanz, Wesley van Dessel, Zuwairie Ibrahim, Andrew Ilachinski, Jeff Jones, Anne V. D. M. Kayem, Genaro J. Martínez, Pedro de Oliveira, Mikhail Prokopenko, Theresa Schubert, Peter Sloot, Emanuele Strano, Xin-She Yang
Abstract: We analyse the results of our experimental laboratory approximation of motorways networks with slime mould Physarum polycephalum. Motorway networks of fourteen geographical areas are considered: Australia, Africa, Belgium, Brazil, Canada, China, Germany, Iberia, Italy, Malaysia, Mexico, The Netherlands, UK, USA. For each geographical entity we represented major urban areas by oat flakes and inoculated the slime mould in a capital. After slime mould spanned all urban areas with a network of its protoplasmic tubes we extracted a generalised Physarum graph from the network and compared the graphs with an abstract motorway graph using most common measures. The measures employed are the number of independent cycles, cohesion, shortest paths lengths, diameter, the Harary index and the Randic index. We obtained a series of intriguing results, and found that the slime mould approximates best of all the motorway graphs of Belgium, Canada and China, and that for all entities studied the best match between Physarum and motorway graphs is detected by the Randic index (molecular branching index).
Title: Complex dynamics of elementary cellular automata emerging in chaotic rules
Journal: International Journal of Bifurcation and Chaos 22(2), 1250023-13, 2012. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Ramon Alonso-Sanz
URL: http://www.worldscinet.com/ijbc/22/2202/S021812741250023X.html
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: Invertible behavior in elementary cellular automata with memory
Journal: Information Sciences 199, 125-132, 2012. [PDF]
Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Ramon Alonso-Sanz, Norberto H. Romero
URL: http://www.sciencedirect.com/science/article/pii/S0020025512001910
Abstract: Elementary cellular automata (ECAs) have been studied for their ability to generate complex global behavior, despite their simplicity. One variation of ECAs is obtained by adding memory to each cell in a neighborhood. This process generates a provisional configuration in which the application of an evolution rule establishes the dynamics of the system. This version is known as an ECA with memory (ECAM). Most previous work on ECAMs analyzed the complex behavior taking chaotic ECAs. However, the present paper investigates reversible ECAMs as obtained from reversible and permutative ECAs. These ECAs have at least one ancestor for every configuration; thus, the correct permutation of states may specify the memory function to obtain reversible ECAMs. For permutative ECAs, which are often irreversible, we demonstrate that the use of a quiescent state and the correct manipulation of de Bruijn blocks produce reversible ECAMs.
Title: Cellular automaton supercolliders
Journal: International Journal of Modern Physics C 22(4), 419-439, 2011. [PDF]
Review: Computer Scientists Build Cellular Automaton Supercollider, Technology Review, Published by MIT, May 25, 2011.
Authors: Genaro J. Martínez, Andrew Adamatzky, Christopher R. Stephens, Alejandro F. Hoeflich
URL: http://www.worldscientific.com/doi/abs/10.1142/S0129183111016348
Abstract: Gliders in one-dimensional cellular automata are compact groups of non-quiescent and non-ether patterns (ether represents a periodic background) translating along automaton lattice. They are cellular-automaton analogous of localizations or quasi-local collective excitations travelling in a spatially extended non-linear medium. They can be considered as binary strings or symbols travelling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions. We analyse what types of interaction occur between gliders travelling on a cellular automaton `cyclotron' and build a catalog of the most common reactions. We demonstrate that collisions between gliders emulate the basic types of interaction that occur between localizations in non-linear media: fusion, elastic collision, and soliton-like collision. Computational outcomes of a swarm of gliders circling on a one-dimensional torus are analysed via implementation of cyclic tag systems.
Title: Reproducing the cyclic tag system developed by Matthew Cook with Rule 110 using the phases f1_1
Journal: Journal of Cellular Automata 6(2-3), 121-161, 2011. [PDF]
Authors: Genaro J. Martínez, Harold V. McIntosh, Juan C. Seck-Tuoh-Mora, 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: Approximating Mexican highways with slime mould
Journal: Natural Computing 10(3), 1195-1214, 2011. [PDF]
Authors: Andrew Adamatzky, Genaro J. Martínez, Sergio V. C. Vergara, René A. Palacio, Christopher R. Stephens
URL: http://www.springerlink.com/content/2rqx07812136kh8v/
Review: New Scientist TV: Slime mould takes over Mexican highway system, published by New Scientist TV, November 5, 2010.
CERN: http://cds.cern.ch/record/1297546?ln=en
Abstract: Plasmodium of Physarum polycephalum is a single cell visible by unaided eye. During its foraging behavior the cell spans spatially distributed sources of nutrients with a protoplasmic network. Geometrical structure of the protoplasmic networks allows the plasmodium to optimize transport of nutrients between remote parts of its body. Assuming major Mexican cities are sources of nutrients how much structure of Physarum protoplasmic network correspond to structure of Mexican Federal highway network? To find an answer undertook a series of laboratory experiments with living Physarum polycephalum. We represent geographical locations of major cities by oat flakes, place a piece of plasmodium in Mexico city area, record the plasmodium's foraging behavior and extract topology of nutrient transport networks. Results of our experiments show that the protoplasmic network formed by Physarum is isomorphic, subject to limitations imposed, to a network of principle highways. Ideas and results of the paper may contribute towards future developments in bio-inspired road planning.
Title: Complex Dynamics in a Hexagonal Cellular Automaton
Journal: Proceedings of the 2011 International Conference on High Performance Computing & Simulation (HPCS 2011), IEEE Xplore 10.1109/HPCSim.2011.5999904, 750-756, 2011. [PDF]
Authors: Paulina A. León, Rogelio Basurto, Genaro J. Martínez, Juan C. Seck-Tuoh-Mora
Abstract: Hexagonal cellular automata (CA) were studied with interest as a variation of the famous Game of Life CA, mainly for spiral phenomena simulations; where the most interesting constructions are related to the Belousov-Zhabotinsky reaction. In this paper, we study a special kind of hexagonal CA known as the Spiral rule. Such automaton displays a non-trivial complex behaviour related to discrete models of reaction-diffusion chemical media, dominated by spiral guns that easily emerge from random initial conditions. Computing abilities of Spiral rule automata are shown by means of logic gates, defined by collisions between mobile self-localizations. Also, a more extended classification of complex self-localization patterns is presented, including some self-organized patterns.
Title: How to make dull cellular automata complex by adding memory: Rule 126 case study
Journal: Complexity 15(6), 34-49, 2010. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Juan C. Seck-Tuoh-Mora, Ramon Alonso-Sanz
URL: http://onlinelibrary.wiley.com/doi/10.1002/cplx.20311/abstract
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: Computation with competing patterns in Life-like automaton
Book: Game of Life Automata (Andrew Adamatzky Ed.), Springer, chapter 27, pages 547-572, 2010. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita, Maurice Margenstern
URL: http://www.springer.com/computer/theoretical+computer+science/book/978-1-84996-216-2
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: Localization dynamics in a binary two-dimensional cellular automaton: the Diffusion Rule
Journal: Journal of Cellular Automata 5(4-5), 289-313, 2010. [PDF]
Book: Game of Life Automata (Andrew Adamatzky Ed.), Springer, chapter 17, pages 291-315, 2010.
URL: http://www.springer.com/computer/theoretical+computer+science/book/978-1-84996-216-2
CERN: http://cds.cern.ch/record/1198124?ln=en
Authors: Genaro J. Martínez, Andrew Adamatzky, 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: Elementary cellular automaton Rule 110 explained as a block substitution system
Journal: Computing 88, 193-205, Springer-Verlag, 2010. [PDF]
Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Norberto H. Romero, Joselito M. Marín
URL: http://www.springerlink.com/content/c883338q3j470377/
Abstract: This paper presents the characterization of Rule 110 as a block substitution system of three symbols. Firstly, it is proved that the dynamics of Rule 110 is equivalent to cover the evolution space with triangles formed by the cells of the
automaton. It is hence demonstrated that every finite configuration can be partitioned in several blocks of symbols and, that the dynamics of Rule 110 can be reproduced by a set of production rules applied to them. The shape of the blocks in the current
configuration can be used for knowing the number of them in the next one; with this, the evolution of random configurations, ether and gliders can be modeled.
Title: Majority adder implementation by competing patterns in Life-like rule B2/S2345
Journal: Lecture Notes in Computer Science 6079, 93-104, 2010. [PDF]
Authors: Genaro J. Martínez, Kenichi Morita, Andrew Adamatzky, Maurice Margenstern
URL: http://www.springerlink.com/content/q38873422m4774x4/
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: Operating binary strings using gliders and eaters in reaction-diffusion cellular automaton
Journal: Mathematical and Computer Modeling 52, 177-190, 2010. [PDF]
Authors: Andrew Adamatzky, Genaro J. Martínez, Liang Zhang, Andrew Wuensche
URL: http://www.sciencedirect.com/science/article/pii/S0895717710000580
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: 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, Juan C. Seck-Tuoh-Mora
URL: http://www.complex-systems.com/abstracts/v18_i03_a05.html
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), 72-82, 2010. [PDF]
Authors: Andrew Adamatzky, Genaro J. Martínez
URL: http://www.emeraldinsight.com/journals.htm?articleid=1846948
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: 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. Seck-Tuoh-Mora, Sergio V. C. Vergara
URL: http://eprints.uwe.ac.uk/10576/
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, Harold V. McIntosh
URL: http://link.springer.com/chapter/10.1007/978-3-540-79992-4_11
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, chapter 26, pages 356-366, 2008. [PDF]
Authors: Genaro J. Martínez, Andrew Adamatzky, Harold V. McIntosh, Ben De Lacy Costello
URL: http://uncomp.uwe.ac.uk/genaro/Diffusion_Rule/B2-S2345678.html
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, Ben De Lacy Costello
URL: http://www.sciencedirect.com/science/article/pii/S0375960108008736
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. Seck-Tuoh-Mora, 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: Unconventional invertible behaviors in reversible one-dimensional cellular automata
Journal: International Journal of Bifurcation and Chaos 18(12), 3625–3632, 2008. [PDF]
Authors: Juan C. Seck-Tuoh-Mora, Manuel G. Hernández, Genaro J. Martínez, Serigo V. C. Vergara, Harold V. McIntosh
URL: http://www.worldscientific.com/doi/abs/10.1142/S0218127408022597
Abstract: Reversible cellular automata are discrete invertible dynamical systems determined by local interactions among their components. For the one-dimensional case, there are classical references providing a complete characterization based on combinatorial properties. Using these results and the simulation of every automaton by another with neighborhood size 2, this paper describes other types of invertible behaviors embedded in these systems different from the classical one observed in the temporal evolution. In particular spatial reversibility and diagonal surjectivity are studied, and the generation of macrocells in the evolution space is analyzed.
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. Seck-Tuoh-Mora, 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, Juan C. Seck-Tuoh-Mora
Journal: International Journal of Bifurcation and Chaos 16(10), 1-21, 2006. [PDF]
URL: http://www.worldscientific.com/doi/abs/10.1142/S0218127406016598
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. Seck-Tuoh-Mora, Genaro J. Martínez, 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, Harold V. McIntosh
URL: http://www.sciencedirect.com/science/article/pii/S0960077905004893
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, Juan C. Seck-Tuoh-Mora
URL: http://www.oldcitypublishing.com/IJUC/IJUCabstracts/IJUC2.1abstracts/IJUCv2n1p1-49Martinez.html
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. Seck-Tuoh-Mora, Sergio V. C. Vergara, Genaro J. Martínez, Harold V. McIntosh
URL: http://www.sciencedirect.com/science/article/pii/S0167278905000540
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
Place: Escuela Superior de Cómputo, Instituto Politécnico Nacional, México, 2005. [PDF] spanish workpaper
Authors: Genaro Juárez Martínez, Adriana Menchaca Méndez, Miriam Mecate 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
Place: 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
Place: 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: Calculating ancestors in one-dimensional cellular automata
Journal: International Journal of Modern Physics C 15(8), 1151-1169, 2004. [PDF]
Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, Harold V. McIntosh
Abstract: One-dimensional cellular automata are dynamical systems characterized by discreteness (in space and time), determinism and local interaction. We present a procedure in order to calculate ancestors for a given sequence of states, this procedure is based on a special kind of graph called subset diagram. We use this diagram to specify subset tables for calculating ancestors which are not Garden-of-Eden sequences, hence the process is able to yield ancestors in several generations. Some examples are illustrated using the cellular automaton Rule 110 which is the most interesting automaton of two states and three neighbors.
Title: Correspondence between the temporal and spacial behavior in reversible one-dimensional cellular automata equivalent with the full shift
Place: DMCS Workshop, University of Turku, Finland, 2004. [PDF]
Authors: Juan C. Seck-Tuoh-Mora, Genaro J. Martínez, 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: 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, Juan C. Seck-Tuoh-Mora
URL: http://link.springer.com/chapter/10.1007%2F978-3-540-39432-7_19
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. Seck-Tuoh-Mora, Sergio V. C. Vergara, Genaro J. Martínez, 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
Publication: Workpaper.
Place: 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
Publication: Workpaper.
Place: 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
Publication: Workpaper.
Place: Departamento de Microcomputadoras, Universidad Autónoma de Puebla, México, 2001. [HTML]
Authors: Genaro J. Martínez, Harold V. McIntosh