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).