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.

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.