We show that if a cellular automaton in two or more dimensions supports growing ladders which can turn or block each other, then it can express arbitrary Boolean circuits. This class includes the Life without Death rule, in which cells turn on if exactly three of their neighbors are on, and never turn off.

The above CA crystal, a cosmic variant of the ancient Zia design on the New Mexico state flag, is generated by one of our favorite cellular automaton rules - Life without Death (LwoD) - started from a small lattice ball. While spending a month at the Santa Fe Institute this spring, I wrote a little paper with Cris Moore, one of the resident CA mavens, showing that LwoD can emulate any Boolean circuit. The ability to do so establishes a degree of algorithmic complexity known as P-completeness. Simple CA models of ballistic computation are known to have this property; see Chapter 18 of Cellular Automata Machines by Toffoli and Margolus (MIT Press, 1987). The novelty of our argument is to show how the ladders of LwoD, which leave tracks that cannot be crossed, nevertheless are able to perform logic. Some rather delicate engineering is needed since the chaotic growth of LwoD has a propensity to generate parasitic chutes and uncontrollable dendritic lava.

We offer our work in two forms: a gentler hypertext version with some companion Java demos, and a downloadable copy of the complete manuscript which includes more quantitative details.

To the html version...

To the Java demos...

Download the complete manuscript (compressed postscript)...