Complete Characterization of Structure of Rule 54
Genaro J. Martínez
Escuela Superior de Cómputo, Instituto Politécnico Nacional, México
and
Unconventional Computing Center, Computer Science Department
University of the West of England, Bristol BS16 1QY, United Kingdom
genaro.martinez@uwe.ac.uk
Andrew Adamatzky
Unconventional Computing Center, Computer Science Department
University of the West of England, Bristol BS16 1QY, United Kingdom
andrew.adamatzky@uwe.ac.uk
Harold V. McIntosh
Departamento de Aplicación de Microcomputadoras
Instituto de Ciencias, Universidad Autónoma de Puebla, Puebla, México
mcintosh@unam.mx
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 
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 . 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.
