Still Life Generation in Conway's Game of Life
by
Paul
Callahan
from
Ingenuity
Systems
Monday, November 13, 2000 at 3:45 p.m.
Science Building 1, Room SC1125
Still Life Generation in Conway's Game of Life
by
Paul
Callahan
from
Ingenuity
Systems
Monday, November 13, 2000 at 3:45 p.m.
Science Building 1, Room SC1125
A still life is a pattern in the Game of Life that does not change between generations. More precisely, this is a pattern in which every live cell has 2 or 3 live neighbors, and no dead cell has exactly 3 live neighbors. Generating a still life is a type of Constraint Satisfaction Problem, and one that has been found to be solvable in practice by a wide variety of methods such as backtracking search. Note that an empty pattern is a trivial still life, but non-empty still life patterns can also be generated easily.
This talk demonstrates a novel method of generating still life patterns using a randomized fixed point algorithm. Conway's rules are themselves a fixed point for still life patterns, but in most cases converge to period-2 arrangements of patterns. The algorithm we present can be seen to converge to high-density still life patterns, though we do not have a proof of this property. The iterative rule is based on some intuitive ideas about how a person might correct local constraint violations as well as a randomized rule to make it possible to escape from cyclic iterations. While a rigorous analysis of this algorithm would be ideal, its empirical behavior is itself intriguing and suggests a generalization to higher period oscillators.
We extend the problem to allow cells that are required to be live or dead. In this case, it is possible to impose constraints that hinder convergence substantially. This is not surprising, since the problem of completing a partially-specified still life can be shown to be NP-hard. We conjecture that this problem is in fact NP-complete, but need to show that every fixed set of cells that can be stabilized to form a still life has a polynomial-size stabilization. We present strong intuition that this is the case and pose proof of the conjecture as an open problem.
This lecture series on cellular automata and complex systems is sponsored by the Santa Fe Institute's Fellows-at-Large Program 2000 and taking place at Cal State Northridge.
