Complexity_ A Guided Tour - Melanie Mitchell [69]
Von Neumann also was able to show that his cellular automaton was equivalent to a universal Turing machine (cf. chapter 4). The cell update rule plays the role of the rules for the Turing machine tape head, and the configuration of states plays the role of the Turing machine tape—that is, it encodes the program and data for the universal machine to run. The step-by-step updates of the cells correspond to the step-by-step iteration of the universal Turing machine. Systems that are equivalent in power to universal Turing machines (i.e., can compute anything that a universal Turing machine can) are more generally called universal computers, or are said to be capable of universal computation or to support universal computation.
The Game of Life
Von Neumann’s cellular automaton rule was rather complicated; a much simpler, two-state cellular automaton also capable of universal computation was invented in 1970 by the mathematician John Conway. He called his invention the “Game of Life.” I’m not sure where the “game” part comes in, but the “life” part comes from the way in which Conway phrased the rule. Denoting on cells as alive and off cells as dead, Conway defined the rule in terms of four life processes: birth, a dead cell with exactly three live neighbors becomes alive at the next time step; survival, a live cell with exactly two or three live neighbors stays alive; loneliness, a live cell with fewer than two neighbors dies and a dead cell with fewer than three neighbors stays dead; and overcrowding, a live or dead cell with more than three live neighbors dies or stays dead.
FIGURE 10.3. Close-up picture of a glider in the Game of Life. After four time steps, the original glider configuration has moved in the southeast direction.
Conway came up with this cellular automaton rule when looking for a rule that would create interesting (or perhaps life-like) behavior. Indeed the Game of Life has plenty of interesting behavior and there is a whole community of Life aficionados whose main hobby is to discover initial patterns that will create such behavior.
One simple pattern with interesting behavior is the glider, illustrated in figure 10.3. Here, instead of lightbulbs, I simply represent on (live) states by black squares and off (dead) states by white squares. The figure shows a glider “moving” in a southeast direction from its initial position. Of course, it’s not the cells that move; they are all fixed in place. The moving entities are on states that form a coherent, persisting shape. Since, as I mentioned earlier, the cellular automaton’s boundaries wrap around to create a donut shape, the glider will continue moving around and around the lattice forever.
Other intricate patterns that have been discovered by enthusiasts include the spaceship, a fancier type of glider, and the glider gun, which continually shoots out new gliders. Conway showed how to simulate Turing machines in Life by having the changing on/ off patterns of states simulate a tape head that reads and writes on a simulated tape.
John Conway also sketched a proof (later refined by others) that Life could simulate a universal computer. This means that given an initial configuration of on and off states that encodes a program and the input data for that program, Life will run that program on that data, producing a pattern that represents the program’s output.
Conway’s proof consisted of showing how glider guns, gliders, and other structures could be assembled so as to carry out the logical operations and, or, and not. It has long been known that any machine that has the capacity to put together all possible combinations of these logic operations is capable of universal computation. Conway’s proof demonstrated that, in principle, all such combinations of logical operations are possible in the Game of Life.