Question: The complexity apparent in the behavior of Class 4 cellular automata suggests that these systems may be capable of universal computation. A computer can be seen as a system in which definite rules transform an initial sequence of states into a final sequence of states. The initial sequence may be considered as a program and data stored in computer memory, and part of the final sequence may be considered as the result of the computation. CA may be considered computers: their initial configurations represent programs and initial data, and their configurations after a long time contain the results of computations.

A system is a universal computer if, given a suitable initial program, its time evolution can implement any finite algorithm (Chapter 9). A universal computer thus needs only be reprogrammed, not rebuilt to perform each possible calculation. Virtually every digital computer implements each of its operations in terms of the logical primitives AND, OR, and NOT. Strictly speaking, only one of AND or OR is needed, since each can be implemented by the other with the help of the NOT operation. If something can provide these basic logical primitives, then it is capable of universal computation.

Demonstrate that the Game of Life is capable of performing universal computation.