Still Life Theory


Matthew Cook

Graduate Student, Department of Computation and Neural Systems, Caltech

Monday, December 4, 2000 at 3:45 p.m. in Room SC1125

In Conway's Game of Life, random patterns always seem to evolve into a stable state consisting of stationary objects. To analyze these objects, we need a simple definition of what an object is, so that two neighboring blocks are recognized as distinct objects, while items such as an aircraft carrier are recognized as a single object (since the two halves are not stable on their own).

The standard terminology for this distinction is that patterns which consist of separately stable subpatterns are called pseudo still lifes, while indivisible stable patterns are strict still lifes.

Surprisingly, it turns out that the question of whether a stable pattern is a strict or pseudo still life is much more subtle than people have imagined. I will show several freak still lifes whose classification as strict vs. pseudo is very sensitive to the exact definition being used to determine indivisibility.

After considering some good-sounding definitions, we use the four-color theorem to narrow the space of definitions, and then the complexity of actually deciding strict vs. pseudo is examined for these definitions, and found to be very sensitive to the definition: The complexity of deciding strict vs. pseudo ranges from tractable to intractable, depending on seemingly innocent changes in one's definition of an indivisible pattern.

Students are encouraged to attend.

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.

Department of Mathematics

return to main page