Introduction

An ``elementary'' cellular automaton consists of a sequence of sites carrying values 0 or 1 arranged on a line. The value at each site evolves deterministically with time according to a set of definite rules involving the values of its nearest neighbours. In general, the sites of a cellular automaton may be arranged on any regular lattice, and each site may take on any discrete set of values. This article concentrates on the case of ``elementary'' cellular automata in one dimension with binary values at each site, and shows that despite their simple construction, such systems can exhibit complicated behaviour. Details, extensions and further discussion, together with more extensive references, are given in ref. [1].

Cellular automata were introduced by von Neumann and Ulam as simple models in which to study biological processes such as self-reproduction [2]. Any system with many identical discrete elements undergoing deterministic local interactions may be modelled as a cellular automaton. Non-trivial cellular automata are obtained when the local evolution is non-linear. Physical examples may be found in aggregation phenomena such as snowflake growth (c.f. [3]). Biological examples are found when organisms grow into complicated forms by repeated application of simple local rules (e.g. [4]). Mathematical systems akin to cellular automata are found in number theory [5]. The solitaire computer game of ``Life'' [6] is an example of a two-dimensional cellular automaton.

Cellular automata may be considered as (parallel-processing) computers, in which the initial configuration encodes the program and input data, and time evolution yields the final output (e.g. [2]). Sufficiently complicated cellular automata (such as the game of ``Life'' [7]) are found to be ``computationally universal'' (e.g. [8]), and thus behave as ``general-purpose'' computers, capable of evaluating any Turing computable function given appropriate input. According to Church's thesis in the formal theory of computation, such cellular automata may thus potentially simulate any possible system.

Figure 1 shows an example of a set of local rules for an elementary cellular automaton. Each of the eight possible sets of values for a site and its nearest neighbours appear on the upper line, while the lower line gives the value to be taken by the central site on the next time step. These rules are applied synchronously to each site at every time step. Thus for example, the sequence 010110110 becomes -0011011- after one time step according to the rule illustrated in fig. 1 (the two end sites depend on unspecified values). Rules may be interpreted as Boolean operations on the values of the three sites in each nieghbourhood. Thus, for example, the rule illustrated in fig. 1 may be considered to take the value of a site to be the sum modulo two of the values of its two neighbours on the previous time step. Rules may be denoted by the decimal equivalents of their binary specifications: fig. 1 thus gives rule . Since any sequence of eight binary digits corresponds to a (elementary) cellular automaton rule in analogy with fig. 1, there are possible such rules. Only the 32 rules of the form satisfy reflection symmetry and leave the ``quiescent'' configuration -000000- unchanged, and are therefore considered ``legal''.

[ Figure 1 ] Example of a set of local rules for an elementary cellular automaton.

previous  l  next