\newpage\subsection {Rigid Models.}
{\em Rigid} computations have another node parameter: {\em location} or {\em
cell}. Combined with time, it designates the event uniquely. Locations have
{\em structure} or {\em proximity} edges between them. They (or their short
chains) indicate all neighbors of a node to which pointers may be directed.
\subsubsection* {Cellular Automata (CA).}
CA are a parallel rigid model. Its sequential restriction is the {\em Turing
Machine (TM)}. The configuration of CA is a (possibly multi-dimensional) grid
with a fixed (independent of the grid size) number of {\em 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 {\em 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.
\paragraph {An example: the Game of Life (GL).} GL is a plane grid of cells,
each holds a 1-bit state (dead/alive) and pointers to the 8 adjacent cells.
A 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) or stays dead.
A {\em simulation} of a machine $M_1$ by $M_2$ is a correspondence between
memory configurations of $M_1$ and $M_2$ which is preserved during the
computation (may be with some time dilation). Such constructions show that the
computation of $M_1$ on any input $x$ can be performed by $M_2$ 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 $(i,j)$ of GL are mapped to cell
$(\lfloor i/a\rfloor,\lfloor j/a\rfloor)$ of CA $M$ (compressing $a\times a$
blocks). We represent cell states of $M$ by states of $a\times a$ 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.
\subsubsection* {Turing Machines.}
Consider an infinite (say, to the right) chain or {\em 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 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\|^2T$) of state changes (volume) one can solve the {\em
Bounded Halting Problem} $H(p,x,T)$: find out whether the machine with a
program $p$ stops on an input $x$ within volume $T$ of computation.
\paragraph {Problem:} Find a method to transform any given multi-head TM $A$
into another one $B$ such that the value of the output of $B(x)$ (as a binary
integer) and the volumes of computation of $A(x)$ and of $B(x)$ are all equal
within a constant factor (for all inputs $x$). {\bf Hint:} $B$-cells may have a
field to simulate $A$ and maintain (in other fields) two binary counters $h$
(with $\theta(1)$ density of heads) for the number of heads of $A$ and $v$ for
$A$'s volume. Their least significant digits are at the left. $h$ adds its most
significant digit to the same position in $v$ at each step of $A$. To move the
carry $1$ on $v$ a head is borrowed from $h$. These $1$-heads move right in $v$
till they empty their carry into its $0$ digit. Then empty $0$-heads move back
to $h$, by switching places with ``headless'' cells or $1$-heads (next-left or
across a ``headless'' cell). Borrowed or returned heads make low or high
head-density areas in $h$. These areas shift left until absorbed at the
leftmost cell.