\newpage\subsection {Pointer Machines.}
The memory configuration of a {\em Pointer Machine (PM)}, called
{\em pointer graph}, is a finite directed labeled multigraph. One node $R$
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, must form a tree to the root, and can be
dropped only in leaves.
All active nodes each step execute an identical {\em program}.
At its first {\em 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
considered dropped. 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 to
be active only pointers to the root and nodes seeing them through
pointers with inverses.
A {\em Kolmogorov} or {\em 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.
{\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\|)$.