Skip navigation
PDF 190KB
DOI: http://dx.doi.org/10.7551/978-0-262-32621-6-ch084
Pages 530-531
First published 30 July 2014

There can be Only One: Reversible Cellular Automata and the Conservation of Genki

Nathaniel Virgo and Takashi Ikegami

Abstract (Excerpt)

Reversible cellular automata (RCAs) are a special class of cellular automata with some very distinctive properties. We present a novel observation regarding a certain class of RCAs, a class that includes Norman Margolus' "Critters" rule. From a broad range of initial conditions, this class of cellular automata converge to a state in which all the structures in the system are periodic (the equivalent of blockers and blinkers in Conway's life), with the exception of a single glider.

The glider that remains is immortal. It follows from a generic property of RCAs that the last glider in the system cannot be destroyed, and its motion cannot enter a periodic cycle. On colliding with a periodic structure, the last glider may change direction or turn into a different type of glider. Very occasionally it will transform into two gliders for a period of time, but when these collide the result is likely to contain only a single glider again. We give some intuitive explanations for why the system converges to a state with only one glider, rather than many.

It seems relatively easy to construct systems with this singleglider property using block CA rules. We give an example where cells can take a number of different colours, and gliders must contain at least three colours (including the background one). When a glider collides with a periodic structure, the new glider resulting from this collision may be composed of different coloured cells than the original one. Thus, some essential organisational property has been transferred from one set of coloured tiles to another. We call this property "genki", after a Japanese word meaning health or vitality. We speculate on how it might be formally defined and whether it is applicable to RCAs in general.