Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.