*Rigid* computations have another node parameter: *location* or *
cell*. Combined with time, it designates the event uniquely. Locations have
*structure* or *proximity* edges between them. They (or their short chains)
indicate all neighbors of a node to which pointers may be directed.

CA are a parallel rigid model. Its sequential restriction is the *Turing
Machine (TM)*. The configuration of CA is a (possibly multi-dimensional) grid
with a fixed (independent of the grid size) number of *states* to label the
events. The states include, among other values, pointers to the grid neighbors.
At each step of the computation, the state of each cell can change as
prescribed by a *transition* function of the previous states of the cell
and its pointed-to neighbors. The initial state of the cells is the input for
the CA. All subsequent states are determined by the transition function (also
called program).

An example of a possible application of CA is a VLSI (very large scale integration) chip represented as a grid of cells connected by wires (chains of cells) of different lengths. The propagation of signals along the wires is simulated by changing the state of the wire cells step by step. The clock interval can be set to the time the signals propagate through the longest wire. This way delays implicitly affect the simulation.

Consider a plane grid of cells, each having a 1-bit state (dead/alive) and
pointers to the 8 natural neighbors. The cell remains dead or alive if the
number **i** of its live neighbors is **2**. It becomes (or stays) alive if **i=3**.
In all other cases it dies (of overpopulation or solitude).

A *simulation* of a machine by is a correspondence between
memory configurations of and which is preserved during the
computation (may be with some time dilation). Such constructions show that the
computation of on any input **x** can be performed by as well. GL can
simulate any CA (see a sketch of an ingenious proof in the last section of
[Berlekamp, Conway Guy 82]) in this formal sense:

We fix space and time periods **a,b**. Cells of GL are mapped to cell
of CA **M** (compressing
blocks). We represent cell states of **M** by states of blocks of
**GL**. This correspondence is preserved after any number **t** steps of **M** and **b
t** steps of **GL** regardless of the starting configuration.

Consider an infinite (say, to the right) chain or **tape** of
cells with two adjacent neighbors each. Each state of a cell has a
pointer to one neighbor. The input to this CA is an array of cells (only
one is leftward) followed at the right by leftward blanks. A cell
changes state, if and only if it and its neighbor ``face'', i.e. point
to each other. The transition function prevents the cells from ever
turning ``back-to-back.'' We can use these 1-pointer CA as a definition
of the TM. The pair of active cells can be viewed as the TM's moving
head (the cell which just changed the pointer direction) and the tape
symbol it works on.

Another type of CA represents a TM **A** with several
non-communicating heads. At most **O(1)** heads fit in a cell. They
cannot vanish, can split or drop off the tape only in the first cell
(which, thus, controls the number of active cells). The input **x**
makes an unchangeable ``ink'' part of each cell's state. The rest of the
cell's state is in ``pencil'' and can be changed by **A**. The
computation halts when all heads drop off. The output **A(x)** is the
pencil part of the tape's state. This model has convenient theoretical
features. E.g. with linear (in **T**) number (**|p| ^{2}T
**) of state changes (volume) one can solve the

Wed Aug 21 20:35:42 EDT 1996