Still Life Theory

People familiar with Conway's Game of Life often talk about "still-lifes": patterns with period 1, also known as stable patterns.

These can be organized into the following categories:

Stable Pattern Any arrangement of on and off cells that stays the same from generation to generation honey farm
Cluster Any stable pattern in which every pair of live cells is connected by a path of cells (using horizontal, vertical, or diagonal steps) that does not have two consecutive empty cells. di-block by hive
General Still-Life Any stable pattern in which every pair of live cells is connected by a path of live or overcrowded cells. switch
Pseudo-Still-Life A general still-life whose islands can be partitioned into two subsets so that each subset is stable on its own. tri-block
Strict Still-Life A general still-life whose islands cannot be partitioned into two subsets so that each subset is stable on its own. dead spark coil on table
Island Any pattern in which every pair of live cells is connected by a path of live cells. sphinx


<<insert examples here>>

Alternate Strict Still-Life Definitions

The standard definitions for pseudo-still-lifes and strict still-lifes talk about partitioning into exactly two proper subsets. But other definitions are plausible -- in particular, it would be reasonable to allow any number of proper subsets.

First of all, we note the surprising result that any pattern whose islands can be partitioned into 5 or more stable proper subsets can also have them partitioned into 4 or fewer such subsets. (proof)

So we can consider the following definitions:

                                                                      difficulty in
                                                                      distinguishing
                                                                      pseudo from strict
exactly two                  subsets   (the standard definition)      O(n^2)
        two or three         subsets                                  NP-complete
        two or three or four subsets   (i.e. any number of subsets)   [open problem]