Schönhage's Storage Modification Machine
May. 6th, 2013 06:24 pmIn 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.
This should definitely help to answer two questions on MathOverflow, regarding Turing-complete primitive blind automata and Universality of blind graph rewriting.
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.
This should definitely help to answer two questions on MathOverflow, regarding Turing-complete primitive blind automata and Universality of blind graph rewriting.
