Search

Complexity has been a recurrent research topic in cellular automata because they represent systems where complex behaviors emerge from simple local interactions. A significant amount of previous research has been conducted proposing instances of complex cellular automata; however, most of the proposed methods are based on a careful search or a meticulous construction of evolution rules. This paper presents the emergence of complex behaviors based on reversible cellular automata. In particular, this paper shows that reversible cellular automata represent an adequate framework to obtain complex behaviors adding only new random states. Experimental results show that complexity can be obtained from reversible cellular automata appending a proportion of about two times more states at random than the original number of states in the reversible automaton. Thus, it is possible to obtain complex cellular automata with dozens of states. Complexity appears to be commonly obtained from reversible cellular automata, and using other operations such as permutations of states or row and column permutations in the evolution rule. The relevance of this paper is to present that reversibility can be a useful structure to implement complex behaviors in cellular automata., 26 pages, 14 figures, Submitted to: Comm Nonlinear Sci Numer Simulat

The emergence of complex behaviors in cellular automata is an area that has been widely developed in recent years with the intention to generate and analyze automata that produce space-moving patterns or gliders that interact in a periodic background. Frequently, this type of automata has been found through either an exhaustive search or 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 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 presented 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 with a higher degree of complexity. With this methodology, it was possible to generate complex automata with hundreds of states, demonstrating that randomly defined local interactions with multiple states can construct complexity., Comment: 30 pages, 22 figures, Submitted to: Inf Sci

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., 31 pages, 23 figures, 3 tables

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., 39 pages, 32 figures, 3 tables

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., Comment: 26 pages, 4 figures, accepted by publish in Journal of Cellular Automata

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., Comment: Accepted to Journal of Cellular Automata