\newpage\subsection {Pointer Machines.}

The memory configuration of a {\em Pointer Machine (PM)}, called {\em
pointer graph}, is a finite directed labeled graph. One node is marked
as {\em root} and has directed paths to all nodes. Nodes {\em see} the
configuration of their out-neighborhood of constant (2 suffices) depth
and change it acting as automata. Edges ({\em pointers}) are labeled
with {\em 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 {\em
working} and not used in inputs/outputs. One of them (as well as
pointers carrying it and nodes seeing them) is called {\em active}.
Active pointers must have inverses and form a tree to the root:
they can be dropped only in leaves.

All active nodes each step execute an identical {\em program}.
 At its first {\em pulling} stage, nodes acquire copies of all pointers
of their 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\}$.
 It also creates new nodes with pointers to and from them. Then, the
node transforms the set of colors of its pointers, drops the pointers
left with composite colors, and vanishes if no pointers are left.
 Nodes with no path from the root are permanently 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.

{\bf 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 {\em 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 {\em parallel, PPM} [Barzdin' Kalnin's
74] or {\em sequential}. The latter differ by allowing only pointers to
the root and nodes seeing them through pointers with inverses to be
active.

A {\em Kolmogorov} or {\em Kolmogorov-Uspenskii} Machine (KM)
[Kolmogorov Uspenskii 58], is a special case of Pointer Machine
[Shonhage 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.

{\em Fixed Connection} Machine (FCM) is a variant of the PKM with the
restriction that pointers once created {\em 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 pointers.

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.

 \paragraph {Example Problem.} Design a machine of each model
 (TM, CA, KM, PPM) which determines if an input string $x$ is a double
(i.e. has a form $ww$, $w\in\{a,b\}^*$). Analyze time (depth) and space.
KM/PPM takes input $x$ in the form of colors of edges in a chain of
nodes, with root linked to both ends. The PPM nodes also have pointers
to the root. Below are hints for TM,PM,CA. The space is $O(|x|)$ in all
three cases.

{\bf 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: $T(x)=O(|x|^2)$. 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: $T(x)=O(|x|)$.

{\bf 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: $T(x)=O(|x|)$.