Life Without Death is P-complete

David Griffeath and Cristopher Moore

Complex Systems 10 (1996) 437-447.

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. Then the problem of predicting the CA for a finite amount of time becomes P-complete, the question of whether a finite configuration grows to infinity is P-hard, and the long-term behavior of initial conditions with a periodic background is undecidable.

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.

Click here to download.

Click here to download a Java/html version with animated figures (and lots of other stuff).

Cris Moore <>