<p>Turing machines and unidimensional cellural automata may both be regarded as "unidimensional" interaction net systems (see Lafont's <a href="http://iml.univ-mrs.fr/~lafont/pub/combinators.ps" rel="nofollow noreferrer"><em>Interaction Combinators</em></a> paper).  So any <a href="https://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine?rq=1">simple UTM</a> or <a href="https://en.wikipedia.org/wiki/Rule_110" rel="nofollow noreferrer">Turing-complete cellula automaton</a> induces a "simple" Turing-complete system.  I'm afraid no better answer is known.</p>

<p>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.</p>

CC BY-SA 3.0
2016-04-16T13:00:31.733Z
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 :(
MaiaVictor
CC BY-SA 3.0
2016-04-16T14:22:25.967Z
Identifying Turing-complete cellular automata is definitely not an easy task. [Rule 110](https://en.wikipedia.org/wiki/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.
Damiano Mazza
CC BY-SA 3.0
2016-04-16T17:42:19.337Z
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).
MaiaVictor
CC BY-SA 3.0
2016-04-16T07:08:42.673Z
2016-04-16T07:21:10.803Z
2017-04-13T12:32:28.053Z
Damiano Mazza
<p>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?</p>

<computability><automata-theory><turing-machines>
What is the simplest universal unidimensional interaction net system?
MaiaVictor
# What is the simplest universal unidimensional interaction net system?

(Asked by: username_0 on 2016-04-15)

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?

**Tags:** computability, automata-theory, turing-machines

---

## 1 answers

### Answer by username_1 on 2016-04-16. Score: 3 | Accepted answer

Turing machines and unidimensional cellural automata may both be regarded as "unidimensional" interaction net systems (see Lafont's [*Interaction Combinators*](http://iml.univ-mrs.fr/~lafont/pub/combinators.ps) paper). So any [simple UTM](https://cstheory.stackexchange.com/questions/10207/whats-the-simplest-noncontroversial-2-state-universal-turing-machine?rq=1) or [Turing-complete cellula automaton](https://en.wikipedia.org/wiki/Rule_110) 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.

> **Comments:**
> **username_0**: 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 :(  
> **username_1**: Identifying Turing-complete cellular automata is definitely not an easy task. [Rule 110](https://en.wikipedia.org/wiki/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.  
> **username_0**: 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).  

---

