3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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$ – MaiaVictor Apr 16 '16 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$ – Damiano Mazza Apr 16 '16 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$ – MaiaVictor Apr 16 '16 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.