Life Without Death Is P-Complete

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.