MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is possible to implement $\lambda$-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 $\lambda$-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.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.