The Interaction Combinators are possibly the simplest multidimensional system of interaction nets that is Turing-complete. What about interaction nets with only 2 ports - 1 principal, 1 auxiliary? What is the simplest of those systems which is Turing-complete?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Turing machines and unidimensional cellural automata may both be regarded as "unidimensional" interaction net systems (see Lafont's Interaction Combinators paper). So any simple UTM or Turing-complete cellula automaton induces a "simple" Turing-complete system. I'm afraid no better answer is known.
Anyway, "simple" is relative: the interaction net system corresponding to even a very small UTM is big compared to the interaction combinators. Cellular automata probably give smaller systems (although still bigger than the interaction combinators) but the interest of these is nevertheless unclear as no special feature of interaction nets is used about them, they are just paraphrases of the original model.
answered Apr 16, 2016 at 7:08
-
$\begingroup$ I'm aware of the UTM case (I believe you showed it to me). I was thinking about simpler systems, like cellular automata, but I'm not sure how to identify if a system is turing complete. One feature that 1D inets could have that cellular automata don't is expansion/contraction of the cells, right? I don't know why I keep asking those questions here, though - seems like nothing is known about inets that isn't on the very few published papers on the subject :( $\endgroup$ Commented Apr 16, 2016 at 13:00
-
$\begingroup$ Identifying Turing-complete cellular automata is definitely not an easy task. Rule 110 is an example but, if I am not mistaken, its universality is controversial. And yes, you can say that cellular automata are "rigid" whereas interaction nets are more flexible. Still, it's unclear why one would want to study unidimensional nets. Anyway, as you say, research about the theory of interaction nets basically stopped in the mid-2000s. Nowadays they are sometimes used as a model, but never for its own sake. $\endgroup$ Commented Apr 16, 2016 at 14:22
-
$\begingroup$ I'm still having trouble understanding why the research has stopped. As you know, they are still the fastest method I found out to reduce λ-terms. Anyway, prof., the reason I think studying 1D nets is valuable is that, if I found a way to translate those nets to a 1D system without losing efficiency, that would make it a much easier job to implement a parallel reducer, since real-world memory is basically a 1D structure. The hardest part with reducing those nets in parallel is keeping allocated nodes close together (to reduce the communication overhead). $\endgroup$ Commented Apr 16, 2016 at 17:42