Game of Life [cellular automaton]

Invented by John Conway around 1970 (see page 877), the Life 2D cellular automaton has been much studied in recreational computing, and as described on page 964 many localized structures in it have been identified. Each step in its evolution can be implemented using

LifeStep[a_List] := MapThread[If[(#1  1 && #2  4) || #2  3, 1, 0]&, {a, Sum[RotateLeft[a, {i, j}], {i, -1, 1}, {j, -1, 1}]}, 2]

A more efficient implementation can be obtained by operating not on a complete array of black and white cells but rather just on a list of positions of black cells. With this setup, each step then corresponds to

LifeStep[list_] := With[{p=Flatten[Array[List, {3, 3}, -1], 1]}, With[{u = Split[Sort[Flatten[Outer[Plus, list, p, 1], 1]]]}, Union[Cases[u, {x_, _, _}x], Intersection[Cases[u, {x_, _, _, _}x], list]]]]

(A still more efficient implementation is based on finding runs of length 3 and 4 in Sort[u].)