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