1
$\begingroup$

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.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.