Complex Systems

A Language for Particle Interactions in Rule 54 and Other Cellular Automata Download PDF

Markus Redeker
Hamburg, Germany


This is a study of localized structures in one-dimensional cellular automata, with the elementary cellular automaton rule 54 as a guiding example.

A formalism for particles on a periodic background is derived, applicable to all one-dimensional cellular automata. We can compute which particles collide and in how many ways. We can also compute the fate of a particle after an unlimited number of collisions—whether they only produce other particles, or the result is a growing structure that destroys the background pattern.

For rule 54, formulas for the four most common particles are given and all two-particle collisions are found. We show that no other particles arise, which particles are stable and which can be created, provided that only two particles interact at a time. More complex behavior of rule 54 requires therefore multi-particle collisions.