Distribution and scaling of complexity in Conway's Game of Life, and connections to nonequilibrium dynamics.

We present results for the scaling properties of lifetimes as a function of grid size for Conway’s Game of Life (GOL). We discuss the implications for both fundamental questions in computational complexity and the connection to phase transitions including nonequilibrium dynamics for 2D Ising models. It is well-known that Turing complete cellular automata are capable of universal computing. We take the view of the initial state on a n x n GOL grid as a program and its evolution as a computation. Assuming periodic boundary conditions, the rules of GOL are invariant under both translations and the symmetries of a square. Consequently, initial states belong to equivalence classes which can each be identified with a unique shape, corresponding program, and computation. We implement Polya’s Enumeration Theorem to determine the number of symmetry equivalent states per shape (i.e. per program), and we analyze the statistical distribution of GOL evolution lifetimes over the set of unique shapes. We use a novel history-dependent definition of lifetime that treats the evolution as a non-Markovian process.