Since it was invented by John Conway and popularized in Martin Gardner’s “Mathematical Games” column in Scientific American in 1970 [1], the Game of Life (GoL) has held a special fascination for fans of recreational mathematics. The GoL is a two-dimensional cellular automaton, a rectangular array of cells that can be in one of two states, alive or dead. A dead cell with exactly three neighbors becomes alive in the next generation, and a live cell with fewer than two or more than three neighbors dies. Though the computation in each cell is thus limited to a finite state automaton, in 1982 Conway, together with Elwyn Berlekamp and Richard Guy [2], published a proof that the overall system has the computational power of a Turing machine (TM). This result shows that interacting machines at one level of computational complexity can yield computation at a qualitatively higher level, and is a cornerstone of the modern understanding of emergent behavior.

For the academic computer scientist, the result of Berlekamp, Conway, and Guy is satisfying and sufficient. Like a TM, the GoL is an abstract model of computation, not a platform on which one would build a practical application. But the very name “Game of Life” anticipates the recreational potential of the system, and it has continued to attract a coterie of researchers who delight to use it to construct the universal computers that we have long known it can support, and to explore how to optimize the structure and execution time of these machines. Rendell’s volume reports an extended project on such engineering of universal computers in the GoL.

Rendell begins with an introduction to the GoL, the Turing machine model, and the computationally equivalent counter machine, and a summary of the known universality of the game. He then reviews previous constructions of universal computation in the GoL, whether as counter machines or as a TM. In chapter 4, he constructs a TM, and in chapter 5 a universal TM, which can accept a model of a given TM and an input on its tape and simulate the execution of the modeled machine on the input. Chapter 6 is devoted to the problem of optimizing the encoding of the modeled machine, which is an instance of the quadratic assignment problem. Though this problem in the general case is NP-hard, Rendell uses Tabu search to explore the space and finds that this instance has a very broad basin of attraction, rendering it tractable.

Rendell models the TM’s infinite tape as two stacks and devotes chapters 7 and 8 to the problem of constructing the superstructure for these stacks fast enough that the TM doesn’t run out of tape. Chapters 9 and 10 review implementations of a universal counter machine and Wolfram’s two-state, three-symbol universal TM. Chapter 11 offers a concluding discussion, and chapter 12 anticipates further work. Appendices contain the complete code for some of the machines described in the text, which run on simulators available through the author’s website. The book has an index, but no integrated bibliography, though individual chapters have references to the literature relevant to each of them.

Aficionados of the Game of Life will welcome this volume as the journal of a fellow enthusiast as he explores new ways to configure and manipulate the simple potential of this fascinating algorithm.