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.
Read more about Pointer Machine: Types of "Pointer Machines", Problems With The Pointer Machine Model, Schönhage's Storage Modification Machine (SMM) Model, Knuth's "Linking Automaton" Model, Kolmogorov-Uspenskii Machine (KU-machine) Model
Famous quotes containing the words pointer and/or machine:
“The hardiest skeptic who has seen a horse broken, a pointer trained, or has visited a menagerie or the exhibition of the Industrious Fleas, will not deny the validity of education. “A boy,” says Plato, “is the most vicious of all beasts;” and in the same spirit the old English poet Gascoigne says, “A boy is better unborn than untaught.””
—Ralph Waldo Emerson (1803–1882)
“The American people is out to get the kaiser. We are bending every nerve and every energy towards that end; anybody who gets in the way of the great machine the energy and devotion of a hundred million patriots is building towards the stainless purpose of saving civilization from the Huns will be mashed like a fly. I’m surprised that a collegebred man like you hasn’t more sense. Don’t monkey with the buzzsaw.”
—John Dos Passos (1896–1970)