Life Without Death is P-complete
David Griffeath
Mathematics Department, University of Wisconsin,
Madison, WI 53706
Cristopher Moore
Santa Fe Institute,
1399 Hyde Park Road, Santa Fe, NM 87501
Abstract
It is shown that if a cellular automaton (CA) in two or more dimensions supports growing "ladders" which can turn or block each other, then it can express arbitrary boolean circuits. Thus 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.
