Pointer machine
Encyclopedia
In theoretical computer science
a pointer machine is an "atomistic" abstract computational machine model akin to the Random access machine
.
Depending on the type, a pointer machine may be called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc. (cf Ben-Amram 1995). At least three major varieties exist in the literature—the Kolmogorov-Uspenskii model (KUM, KU-machine), the Knuth linking automaton, and the Schönhage Storage Modification Machine model (SMM). The SMM seems to be the most common.
From its "read-only tape" (or equivalent) a pointer machine receives input -- bounded symbol-sequences ("words") made of at least two symbols e.g. { 0 , 1 } -- and it writes output symbol-sequences on an output "write-only" tape (or equivalent). To transform a symbol-sequence (input word) to an output symbol-sequence the machine is equipped with a "program" -- a finite-state machine (memory and list of instructions). Via its state machine the program reads the input symbols, operates on its storage structure -- a collection of "nodes" (registers) interconnected by "edges" (pointers labelled with the symbols e.g. { 0, 1 }), and writes symbols on the output tape.
Pointer machines cannot do arithmetic. 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. "Information" is in the storage structure.
But Ben-Amram add more:
van Emde Boas (1990) expresses concern that this form of abstract model is:
Gurevich 1988 also expresses concern:
The fact that, in §3 and §4 (pp. 494–497), Schönhage himself (1980) demonstrates the real-time equivalences of his two Random Access Machine
models "RAM0" and "RAM1" leads one to question the necessity of the SMM for complexity studies.
Potential uses for the model: However, Schönhage (1980) demonstrates in his §6, Integer-multiplication in linear time. And Gurevich wonders whether or not the "parallel KU machine" "resembles somewhat the human brain" (Gurevich (1988) p. 5)
> unlike register machine
model. More difficult to understand quite unlike a "computer" -- abstract or otherwise.
> Attempt here to give an understanding from a more basic-concept level.
Alphabet k = list of symbols input to the machine. k=2 is the minimum number of edges/symbols. Typical is the binary alphabet { 0, 1 }. A ternary set might be { a, b, c } etc.
Word = a string of symbols, e.g. 101101, input to the machine. A machine will "accept" a subset of all the possible strings U that can be generated by all SUM0 to n( 2(n*k) ) ( verify formula: this is in reference to the number of subsets creatable from the universal superset ) possible combinations of the symbols
Node or State: Each node is distinguishable and labelled with a unique symbol inside it (the symbols are not necessarily related to the alphabetic words). From each node emerges k arrows (e.g. 2 arrows for the binary set of symbols { 0 , 1 }).
Edge: From each node emerges as many "arrows" as there are symbols in the alphabet; The arrow's head indicates the "next" node, and each arrow is labelled with a symbol. Example: for a binary alphabet, e.g. { 0, 1 }, two arrows will emerge from every node; one of the two arrows will be labelled with "0", the other with "1". for a ternary alphabet, e.g. { a, b, c }, three symbols will emerge, each will bear the (unique) symbol "a", "b", or "c".
Path: A path along nodes and arrows represents every word (string of symbols e.g. 101101) "the machine" can accept. A path will be determined in part by the history of how it was created.
Instruction: An instruction changes the layout of the graph: the new w instruction creates a new node which "results" in the string w, while the set w to v instruction (re)directs an edge to a different node. Here w and v represent words. v is a former word—i.e. a previously-created string of symbols—so that the redirected edge will point "backwards" to an old node that "culminates/results" in that string.
(1) new w: creates a new node. w represents the new word that creates the new node. The machine reads the word w, following the path represented by the symbols of w until the machine comes to the last (extra, additional, concatenated) symbol in the word. The additional symbol forces the last state to "flip" its corresponding arrow from "backward"-pointing to "forward"-pointing, to create a new node, and to point the arrow to the node. The new node in turn points all its edges back to the old last-state, where they just "rest" until redirected by new or set.
(2)Set w to v: redirects (moves) an edge (arrow) from the path represented by word w to a former node that represents word v. Again it is the last arrow in the path that is redirected.
(3)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.
-- generic register-based abstract machine
computational model
Turing machine
-- generic tape-based abstract machine
computational model
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
a pointer machine is an "atomistic" abstract computational machine model akin to the Random access machine
Random access machine
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
.
Depending on the type, a pointer machine may be called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc. (cf Ben-Amram 1995). At least three major varieties exist in the literature—the Kolmogorov-Uspenskii model (KUM, KU-machine), the Knuth linking automaton, and the Schönhage Storage Modification Machine model (SMM). The SMM seems to be the most common.
From its "read-only tape" (or equivalent) a pointer machine receives input -- bounded symbol-sequences ("words") made of at least two symbols e.g. { 0 , 1 } -- and it writes output symbol-sequences on an output "write-only" tape (or equivalent). To transform a symbol-sequence (input word) to an output symbol-sequence the machine is equipped with a "program" -- a finite-state machine (memory and list of instructions). Via its state machine the program reads the input symbols, operates on its storage structure -- a collection of "nodes" (registers) interconnected by "edges" (pointers labelled with the symbols e.g. { 0, 1 }), and writes symbols on the output tape.
Pointer machines cannot do arithmetic. 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. "Information" is in the storage structure.
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 6 "atomistic models" must be distinguished from "High-level" models. This article will discuss the following 3 atomistic models in particular:- Schönhage's Storage Modification Machines (SMM),
- Kolmogorov-Uspenskii Machines (KUM or KU-Machines),
- Knuth's "Linking Automaton"
But Ben-Amram add more:
- Atomistic Pure-LISP Machine (APLM)
- Atomistic Full-LISP machine (AFLM),
- General atomistic Pointer Machines,
- Jone's I Language (two types)
Problems with the pointer machine model
Use of the model in complexity theory:van Emde Boas (1990) expresses concern that this form of abstract model is:
- "an interesting theoretical model, but ... its attractiveness as a fundamental model for complexity theory is questionable. Its time measure is based on uniform time in a context where this measure is known to underestimate the true time complexity. The same observation holds for the space measure for the machine" (van Emde Boas (1990) p. 35)
Gurevich 1988 also expresses concern:
- "Pragmatically speaking, the Schönhage model provides a good measure of time complexity at the current state of the art (though I would prefer something along the lines of the random access computers of Angluin and Valiant)" (Gurevich (1988) p. 6 with reference to Angluin D. and Valiant L. G., Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings", Journal of Computer and System Sciences 18 (1979) 155-193.)
The fact that, in §3 and §4 (pp. 494–497), Schönhage himself (1980) demonstrates the real-time equivalences of his two Random Access Machine
Random access machine
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
models "RAM0" and "RAM1" leads one to question the necessity of the SMM for complexity studies.
Potential uses for the model: However, Schönhage (1980) demonstrates in his §6, Integer-multiplication in linear time. And Gurevich wonders whether or not the "parallel KU machine" "resembles somewhat the human brain" (Gurevich (1988) p. 5)
Schönhage's Storage Modification Machine (SMM) model
Outline: work in progress (follows van Emde Boas 1990 rather than Schonhage which is marred with virtually no examples). Seems to be the most common and accepted model:> unlike register machine
Register machine
In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine...
model. More difficult to understand quite unlike a "computer" -- abstract or otherwise.
> Attempt here to give an understanding from a more basic-concept level.
- directed "graph" (a drawing that looks virtually identical to a state diagramState diagramA state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems. State diagrams require that the system described is composed of a finite number of states; sometimes, this is indeed the case, while at other times this is a reasonable abstraction...
) of circles called nodes and labelled arrows called edges.
Alphabet k = list of symbols input to the machine. k=2 is the minimum number of edges/symbols. Typical is the binary alphabet { 0, 1 }. A ternary set might be { a, b, c } etc.
Word = a string of symbols, e.g. 101101, input to the machine. A machine will "accept" a subset of all the possible strings U that can be generated by all SUM0 to n( 2(n*k) ) ( verify formula: this is in reference to the number of subsets creatable from the universal superset ) possible combinations of the symbols
- U = { 0, 1, 00, 01, 10, 11, 100, 101, 110, 111, 1000, 1001, 1011, 1100, 1101, 1110, 1111, 11110, etc }
Node or State: Each node is distinguishable and labelled with a unique symbol inside it (the symbols are not necessarily related to the alphabetic words). From each node emerges k arrows (e.g. 2 arrows for the binary set of symbols { 0 , 1 }).
Edge: From each node emerges as many "arrows" as there are symbols in the alphabet; The arrow's head indicates the "next" node, and each arrow is labelled with a symbol. Example: for a binary alphabet, e.g. { 0, 1 }, two arrows will emerge from every node; one of the two arrows will be labelled with "0", the other with "1". for a ternary alphabet, e.g. { a, b, c }, three symbols will emerge, each will bear the (unique) symbol "a", "b", or "c".
Path: A path along nodes and arrows represents every word (string of symbols e.g. 101101) "the machine" can accept. A path will be determined in part by the history of how it was created.
Instruction: An instruction changes the layout of the graph: the new w instruction creates a new node which "results" in the string w, while the set w to v instruction (re)directs an edge to a different node. Here w and v represent words. v is a former word—i.e. a previously-created string of symbols—so that the redirected edge will point "backwards" to an old node that "culminates/results" in that string.
(1) new w: creates a new node. w represents the new word that creates the new node. The machine reads the word w, following the path represented by the symbols of w until the machine comes to the last (extra, additional, concatenated) symbol in the word. The additional symbol forces the last state to "flip" its corresponding arrow from "backward"-pointing to "forward"-pointing, to create a new node, and to point the arrow to the node. The new node in turn points all its edges back to the old last-state, where they just "rest" until redirected by new or set.
- "w" is the (new) word that "leads to" such as the 5-to-6 expansion: 10110[1]
- old edge: points toward new node, example 10110[1], the 5th node's 1-edge now points to the 6th node
- new edges: both new edges point "backward" to the previous node. In a sense they are "sleeping", waiting for an assignment. In the case of the starting or center node both edges point back to itself (the starting node).
(2)Set w to v: redirects (moves) an edge (arrow) from the path represented by word w to a former node that represents word v. Again it is the last arrow in the path that is redirected.
(3)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.
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. Since outgoing pointers must be labeled by distinct symbols of the alphabet, both KUM and SMM graphs have O(1) outdegree. However, KUM pointers' invertibility restricts the in-degree to O(1), as well. This addresses some concerns for physical (as opposite to purely informational) realism, like those in the above van Emde Boas quote.See also
Register machineRegister machine
In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine...
-- generic register-based abstract machine
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
computational model
- Counter machineCounter machineA counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines...
-- most primitive machine, base models' instruction-sets are used throughout the class of register machines - Random access machineRandom access machineIn computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
-- RAM: counter machine with added indirect addressing capability - Random access stored program machineRandom access stored program machineIn theoretical computer science the Random Access Stored Program machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory....
-- RASP: counter-based or RAM-based machine with a "program of instructions" to be found in the registers themselves in the matter of a Universal Turing machineUniversal Turing machineIn computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
i.e. the von Neumann architectureVon Neumann architectureThe term Von Neumann architecture, aka the Von Neumann model, derives from a computer architecture proposal by the mathematician and early computer scientist John von Neumann and others, dated June 30, 1945, entitled First Draft of a Report on the EDVAC...
.
Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
-- generic tape-based abstract machine
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
computational model
- Post-Turing machinePost-Turing machineA Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below. A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a...
-- minimalist one-tape, two-direction, 1 symbol { blank, mark } Turing-like machine but with default sequential instruction execution in a manner similar to the basic 3-instruction counter machines.