Skip to main content

Research Repository

See what's under the surface

Complete characterization of structure of rule 54

Martinez, Genaro J.; Adamatzky, Andrew; McIntosh, Harold V.

Authors

Genaro J. Martinez genaro.martinez@uwe.ac.uk

Harold V. McIntosh



Abstract

The dynamics of rule 54 one-dimensional two-state cellular automaton (CA) are a discrete analog of a space-time dynamics of excitations in 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 catalogue of gliders and describe them by tiles. We calculate a subset of regular expressions $\Psi_{R54}$ to encode gliders. The regular expressions are derived from de Bruijn diagrams, tile-based representation of gliders, and cycle diagrams sometimes. We construct an abstract machine that recognizes regular expressions of gliders in rule 54 and validate $\Psi_{R54}$. We also propose a way to code initial configurations 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.

Journal Article Type Article
Publication Date Oct 8, 2014
Journal Complex Systems
Print ISSN 0891-2513
Peer Reviewed Peer Reviewed
Volume 23
Issue 3
Pages 259-293
APA6 Citation Martinez, G. J., Adamatzky, A., & McIntosh, H. V. (2014). Complete characterization of structure of rule 54. Complex Systems -Champaign-, 23(3), 259-293
Keywords elementary cellular automata, rule 54, complex systems, gliders, collisions, regular language
Publisher URL http://www.complex-systems.com/abstracts/v23_i03_a04.html
Related Public URLs http://uncomp.uwe.ac.uk/genaro/Papers/Papers_on_CA.html

Files







You might also like



Downloadable Citations