The memory configuration of a *Pointer Machine (PM)*,
called *pointer graph*, is a finite directed labeled multigraph.
One node **R** is marked as *root* and has directed
paths to all nodes. Nodes *see* the configuration of their
out-neighborhood of constant (2 suffices) depth and change it
acting as automata. Edges (*pointers *) are labeled with
*colors* from a finite alphabet common to all graphs
handled by a given program. The pointers coming out of a node must
have different colors (which bounds the outdegree). Some colors
are designated as *working* and not used in inputs/outputs.
One of them (as well as pointers carrying it and nodes seeing
them) is called *active*. Active pointers must have
inverses, must form a tree to the root, and can be dropped only in
leaves.

All active nodes each step execute an identical *
program*. At its first *pulling* stage, node **A**
acquires copies of all pointers of its children using
``composite'' colors: e.g., for a two-pointer path **(A,B,C)**
colored **x,y**, the new pointer **(A,C)** is colored
**xy**, or an existing **z**-colored pointer **(A,C)** is
recolored **{z,xy}**. **A** also spawns new nodes with
pointers to and from **A**. Next, **A** transforms the
colors of its set of pointers, drops the pointers left with composite
colors, and vanishes if no pointers are left. Nodes with no path
from the root are forever invisible and effectively removed.
The computation is initiated by inserting an active loop-edge into
the root. When no active pointers remain, the graph, with all
working colors dropped, is the output.

**Problem:** Design a PM transforming the input graph into the
same one with two extra pointers from each node: to its parent in a BFS
spanning tree and to the root. Hint: Nodes with no path * to* the
root can never be activated. They should be copied with pointers, copies
connected to the root, then the original input removed.

Pointer Machines can be either *Parallel, PPM*
[Barzdin' Kalnin's 74] or *Sequential*. The latter differ
by allowing to be active only pointers to the root and nodes
seeing them through pointers with inverses.

A *Kolmogorov* or *Kolmogorov-Uspenskii* Machine (KM)
[Kolmogorov Uspenskii 58], is a special case of Pointer Machine
[Schoenhage 80] with the restriction that all pointers have inverses. This
implies the bounded in/out-degree of the graph which we further assume
to be constant.

*Fixed Connection* Machine (FCM) is a variant of the PKM with
the restriction that pointers once created *cannot* be removed,
only re-colored. So when the memory limits are reached, the structure of
the machine cannot be altered and the computation can be continued only
by changing the colors of the edges.

PPM is the most powerful model we consider: it can simulate the others in the same space/time. E.g., cellular automata make a simple special case of a PPM which restricts the Pointer Graph to be a grid.

**Turing and Pointer Machines.** TM uses extra symbols **A,B**. First find the
middle of **ww** by capitalizing the letters at both ends one by one.
Then compare letter by letter the two halves, lowering the case of the compared
letters. The complexity is: . PM algorithm is similar to the
TM's, except that the root keeps and updates the pointers to the borders
between the upper and lower case substrings. This allows commuting between
these substrings in constant time. So, the complexity is: .

**Cellular Automata.** The computation begins from the leftmost cell sending
right two signals. Reaching the end the first signal turns back. The second
signal propagates three times slower than the first. They meet in the middle of
**ww** and disappear. While alive, the second signal copies the input field **i**
of each cell into a special field **a**. The **a** symbols will try to move right
whenever the next cell's **a** field is blank. So the chain of these symbols
alternating with blanks will start moving right from the middle of **ww**. When
they reach the end they will push the blanks out and pack themselves back into
a copy of the left half of **ww** shifted right. When an **a** symbol does not have
a blank at the right to move to, it compares itself with the **i** field of the
same cell. They should be identical, if the **ww** form is correct. Otherwise a
signal is generated which halts all activity and rejects **x**. If all
comparisons are successful, the last symbol generates the accepting signal.
The complexity is: .

Wed Aug 21 20:35:42 EDT 1996