Next: 1.3 Pointer Machines. Up: 1 Models of Computations; Previous: 1.1 Deterministic Computation.

## 1.2 Rigid Models.

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.

### Cellular Automata (CA).

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.

### An example: the Game of Life (GL).

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.

### Turing Machines.

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|2T ) of state changes (volume) one can solve the 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.

#### 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). Hint: B may keep a field to simulate A and maintain (in other fields) two binary counters h (with θ(1) density of heads) for the number of heads of A and v for A's volume. The least significant digits of h,v would be at the leftmost cell. The most significant digit of h is added at each step to the same digit of v (if needed, with a head assigned to move the carry on v and return).

Next: 1.3 Pointer Machines. Up: 1 Models of Computations; Previous: 1.1 Deterministic Computation.

Leonid Levin
Wed Aug 21 20:35:42 EDT 1996