Life Without Death is P-Complete
David S. Griffeath, Cristopher Moore · 1996
. 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. 1 Introduction Given the initial conditions of a d-dimensional cellular automaton, suppose we want to know the state at a site t time-steps in the future. We can do this in O(t d+1 ) steps on a serial computer, or O(t) steps on a parallel one, simply by simulating the CA explicitly and filling in the light-cone above the site in question. Thus CA Prediction is in the class P of problems solvable by a deterministic Turing mac...