Schönhage’s SMM with only one instruction
May. 7th, 2013 06:32 amhttp://mathoverflow.net/questions/129923
It is possible to implement λ-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions set w to v (with different w and v) using a compact directed encoding for λ-terms closely related to directed interaction combinators by Lafont, and four infinite spaghetti stacks based on linked nodes to perform interaction and indirection rules on configurations.
Is it possible to preserve Turing-completeness of the SMM model while restricting its instruction set to only a single instruction set w to v (with constant w and v) during the whole computation process?
I would be very grateful for any references regarding this question.
It is possible to implement λ-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions set w to v (with different w and v) using a compact directed encoding for λ-terms closely related to directed interaction combinators by Lafont, and four infinite spaghetti stacks based on linked nodes to perform interaction and indirection rules on configurations.
Is it possible to preserve Turing-completeness of the SMM model while restricting its instruction set to only a single instruction set w to v (with constant w and v) during the whole computation process?
I would be very grateful for any references regarding this question.
