## Saturday, February 23, 2013

### 68. Cellular Automata and the 'Game of Life'

The notion of cellular automata was put forward in the 1940s by Stanislaw Ulam, a colleague of John von Neumann. Ulam suggested to Neumann to consider a digital programmable universe, in which 'time' is imagined as defined by the ticking of a cosmic digital clock, and 'space' is a discrete lattice of cells, each cell occupied by an abstractly defined very simple computer called a finite automaton. Very simple local rules determine the state of any cell at any discrete point of time. There are only a finite number of states available to a cell or an automaton. These states could be, say, a few colours, or a few integers, or just 'dead' or 'alive', etc. At each tick of the digital clock, every automaton changes over to a new state determined by its present state and the present states of the neighbouring cellular automata (CA). The rules by which the state of any automaton changes at a given instant of digital time are the equivalent of the physical laws of our actual universe.

The subject of cellular automata has got a big boost from the work of Stephen Wolfram. He established that CA have a truly wide-ranging applicability and, in particular, have features of nonlinear dynamical systems. He emphasized that the complex phenomena we see in the real universe can be usually thought of as the running of 'simple programs'. The best and often the only way to understand these phenomena is by modelling them on a computer with the help of CA, rather than by working out the consequences of idealized and approximate mathematical models based on a set of equations. Approximations are generally not a good idea for modelling complex systems: No approximation may be a good enough one when things are really complex.

Wolfram's idea of a 'simple program' typically has the following ingredients:
• A set of transformation or operation rules (usually 'local' rules).
• Data to operate on.
• An engine that applies the rules to the data.
In a cellular automaton, the data enter only at the beginning of the computation ('initial conditions'), and the engine keeps applying the same deterministic rules to the outputs of its previous application of the rules. Wolfram investigated a large number of simple programs, and demonstrated that extremely complex-looking patterns can be generated by many of them. The figure below illustrates the point.

Shown here is a 1-dimensional cellular automaton. It consists of a row of squares, and each square can be either black or white. Starting from just one such row of squares (the top row in the upper figure), each time the system is updated, a new row of squares is created just below the previous row, following a simple rule. The simple transformation rule operative in this figure says that a square in the new row should be black only if one or the other, but not both, of its vertically-above predecessor's neighbours is black.

Shown in a separate figure at the bottom is a graphical depiction of this rule, in which 8 block are drawn, corresponding to the 8 possible configurations of three neighbouring cells, each configuration determining the colour of the cell in the next row. Starting with a single black square in the top row of squares, this rule produces a complex pattern of nested triangles.

Shown at the bottom, below the graphical depiction of the operating rule for this CA, are the numbers 0, 1, 0, 1, 1, 0, 1, 0, where 0 corresponds to a white cell, and 1 to a black cell. Treating this sequence of digits as a binary number, we get 01011010, which is the number 90 in the decimal system. Wolfram therefore calls this cellular automaton as generated by Rule 90. The sequence of the eight blocks for depicting this rule has been so chosen as to generate the smallest possible number for labelling or classifying the rule.

A particularly popular example of CA is the Game of Life (GOL), invented (around 1970) by John Conway. It provides a graphic demonstration of artificial evolution; the evolving structures can be seen on a computer screen. One starts with a 2-dimensional lattice of square cells, each cell randomly taken to be either black or white. Let black mean that the 'creature' denoted by a black cell is 'alive', and let white mean that the corresponding creature is 'dead'. Very simple local rules are introduced for how the cells are to change from one time step to the next.

For example, if a cell has two or three neighbours which are alive (i.e. black), then the cell becomes alive if it was dead to start with, or remains alive if it was already so. If the number of neighbours is less than two, the cell dies of 'loneliness'. And if the number of neighbours is more than three, again the cell dies, this time due to 'overcrowding'. Remarkable patterns emerge on the computer screen when this program is run.

Every run is different, and it is not possible to exhaust all possibilities. Often the 'live' cells organize themselves into coherent and ever-changing patterns. The figure below shows the so-called 'Gosper glider gun'.

A 'gun' is a configuration of the GOL which repeatedly and endlessly shoots out moving objects such as 'gliders'.

An unlimited variety of patterns, including bizarre-looking 'creatures' or manmade contraptions, can emerge as the CA evolve. Here is a 'spaceship':