\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.