450 | 41 IS THE wHOlE UNIVERSE A COmPUTER?
mathematical equation), CAs can also solve such problems. The problem is encoded in the
grid’s initial pattern of activity, and once the grid reaches its ‘halting’ state, the user reads off
the solution from the residual pattern of activity. Different CAs can have different transition
rules; and some may have different kinds of grid, or more than just two possible cell states. Even
though CAs are remarkably different from conventional computers, it nevertheless turns out
that if a problem can be solved by a conventional computer then it can also be solved by a CA
(and vice versa): different computational architecture, but the same computational power.
In 1970 the British mathematician John Conway invented a CA engagingly called the ‘Game
of Life’. This CA has four very simple transition rules (Box 41.1). Conway noted an interesting
fact about the Game of Life: through applying these simple rules to small-scale patterns on the
grid, large-scale patterns of surprising complexity emerge.
If you were to zoom in and watch individual cells during the course of the Game of Life’s
computation, all you would see would be the cells switching on and off according to the four
rules. Zoom out, though, and something else appears. Large structures, composed of many
cells, are seen to grow and disintegrate over time. Some of these structures have recognizable
Box 41.1 The Game of Life
The Game of Life has just four transition rules:- If a cell is on, and fewer than two of its neighbours are also on, it will turn off at the next
time-step. - If a cell is on, and either two or three of its neighbours are also on, it will stay on at the next
time-step. - If a cell is on and more than three of its neighbours are on, it will turn off at the next time-step.
- If a cell is off and exactly three of its neighbours are on, it will turn on at the next time step.
figure 41.3 John Conway playing the Game of Life.
Kelvin Brodie. Sun News Syndication.