Pointer machine
In theoretical computer science, a pointer machine is an atomistic abstract computational machine whose storage structure is a graph. A pointer algorithm could also be an algorithm restricted to the pointer machine model.
Some particular types of pointer machines are called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc.
Pointer machines do not have arithmetic instructions. Computation proceeds only by reading input symbols, modifying and doing various tests on its storage structure—the pattern of nodes and pointers, and outputting symbols based on the tests. In this sense, the model is similar to the Turing machine.
Types of "pointer machines"
Both Gurevich and Ben-Amram list a number of very similar "atomistic" models of "abstract machines"; Ben-Amram believes that the "atomistic models" must be distinguished from "high-level" models. The following atomistic models will be presented below:- Schönhage's storage modification machines,
- Kolmogorov–Uspenskii machines.
- Atomistic pure-LISP machine
- Atomistic full-LISP machine,
- General atomistic pointer machines,
- Jone's I language.
Schönhage's storage modification machine (SMM) model
The machine consists of a fixed alphabet of input symbols, a fixed program, and a mutable directed graph with its arrows labelled by alphabet symbols. The graph is the machine's storage. Each node of the graph has exactly one outgoing arrow labelled with each symbol, although some of these may loop back into the original node. One fixed node of the graph is identified as the start or "active" node.
Each word of symbols in the alphabet can then be translated to a pathway through the machine; for example, 10011 would translate to taking edge 1 from the start node, then edge 0 from the resulting node, then edge 0, then edge 1, then edge 1. Thus a word identifies a node, the final node of the path, but this identification will change as the graph changes during the computation.
The machine can receive instructions which change the layout of the graph. The basic instructions are:
new w instruction, which creates a new node at the end of the path w'', with all its edges directed to the next-to-last node in w.
set w to v instruction which directs an edge to a different node. Here w'' and v represent words. The instruction results in changing the destination of the last edge in the path w.
Image:Pointer-machine 2.JPG|thumbnail|500px|Some steps in the execution of a 2-symbol machine with instructions: new ε; new 1; new 11. Instruction #1 initializes the storage graph as a single node, node 1, in the storage graph.
If v = w then instruction z : Conditional instruction that compares two paths represented by words w and v to see if they end at the same node; if so jump to instruction z else continue. This instruction serves the same purpose as the if command in any imperative programming language.
Image:Pointer-machine 1.JPG|thumbnail|500px|Evolution of the storage graph in a 2-symbol machine with instructions: new ε; new 1; new 11; new 10; set 111 to 10. At this time, if the machine were to do the if 10=111 then xxx, then the test would be successful and the machine would indeed jump to xxx.
read and write instructions for input/output, accessing a read-only input tape and a write-only output tape, both containing symbols of the alphabet.
Knuth noted that the SMM model coincides with a type of "linking automaton" briefly explained in volume one of The Art of Computer Programming.
Kolmogorov–Uspenskii machine (KU-machine) model
KUM differs from SMM in allowing only invertible pointers: for every pointer from a node x to a node y, an inverse pointer from y to x must be present, labeled by the same symbol. In other words, the storage graph is undirected. Since outgoing pointers must be labeled by distinct symbols of the alphabet, both KUM and SMM graphs have O outdegree. However, KUM pointers' invertibility restricts the in-degree to O, as well. This addresses some concerns for physical realism.There are other, minor differences between the models, such as the form of the program - a state table instead of a list of instructions.
Considerations regarding the pointer-machine model
Use of the model in complexity theory:van Emde Boas expresses concern that this form of abstract model is:
Gurevich also expresses concern:
Schönhage demonstrates the real-time equivalences of two types of random-access machine with the SMM.
Algorithms in the SMM model: Schönhage demonstrates that the SMM can perform integer multiplication in linear time.
Potential uses for the model: Gurevich wonders whether or not a parallel KU machine "resembles somewhat the human brain"
Parallel computing: All the models mentioned above are sequential. A parallel pointer machine model has been proposed by Cook and Dymond; a high-level parallel pointer machine model has also been used