Introduction

The above image shows what the simplest possible interaction net that grows forever does. What are interaction nets, and what does this mean? I’ll start by writing about why I became interested in them in the first place, and then we’ll explore more what they can do in later sections.
​
For a while I’ve been interested in exploring the space of all possible programs in different ways. One could do this by exploring something like Turing machines or cellular automata, however these have a built-in list or grid like structure. Combinators and Lambda calculus and are interesting for this as they seem “higher level” and so can more closely correspond to programming languages that people tend to actually use when writing arbitrary programs.
​
However, lambda calculus and combinators are still constrained in a way, in that while Turing machines are linear in shape, lambda calculus and combinator expressions are fundamentally structured like trees. I thought it would be interesting to work with something that’s more fundamentally an arbitrary graph structure, as then one maybe wouldn’t have to go through as many steps to get the program to do something in whatever number of dimensions one wants, for instance. For this, I’ve been intrigued by Stephen Wolfram’s hypergraph rewriting system which can be shown to be able to run any other kind of program in the end. For all of the above programs, there have been searches through the space of all programs of those kinds. I at least know that Stephen Wolfram has done so extensively.
​
But there was still something missing, I felt. With the hypergraph rewriting Wolfram models, searching the space involved searching for many graph rewriting rules. A nice technical thing about searching the space of lambda calculus and combinators is that the rules for rewriting those expressions are generally the same. The search for programs generally takes place in the initial conditions, not the rules. So I wondered to myself for a bit if there was some nice specific graph rewriting rule of some kind where the initial conditions of the graph would allow one to change the graph as one wants, from inside.
​
Then I learned about interaction nets, which have actually apparently been around for a while, since 1990, but I was happy to learn about them much more recently. The simplest kind of interaction net, but that can also emulate any other interaction net, are networks with three specific kinds of nodes and 6 specific rewrite rules that tell how those 3 nodes interact. The rules for this system also happen to look nice and symmetrical. On top of being made of relatively simple components and so easy to study in full, this system can evolve to make all kinds of graphs depending on the initial condition of nodes and connections, just how I’d hoped. Besides all of all this, they also, despite being simple, seem to be high level enough, like lambda calculus, and can be used without too much fuss to make a useable programming language, which people have done. There are other fascinating aspects about interaction nets like these in that for instance might allow one to do especially efficient parallel programming in at least some cases, that I won’t get into right now but that you can read about in the earlier link about them.
​
So I thought, well, since it’s such a simple and elegant system, wouldn’t it be interesting to systematically explore the space of all possible interaction nets? To that end, I wrote some code that generates all possible interaction nets up to a certain size, and some other code to somewhat randomly generate interaction nets of a certain size to probe the space of larger interaction nets (as the space of all interaction nets is pretty big for not-tiny net size). Fortunately Nikolay Murzin had already written up some code for evaluating and displaying interaction nets that I was able to use for the evaluation / display parts of the project, and so I just wrote up the code that generated all the nets. Along the way I did find that one of the simplest possible interaction nets has rather complex behavior, and that it matches with behavior from a system coming from a rather different direction.

Code


Enumerating All Nets of a Certain Size

Size 2

When enumerating interaction nets, one must specify an even “node count”. The reason for this is as follows. As I mentioned, there are three types of nodes in the system I’m studying, which are creatively named delta epsilon and gamma, though I’ve also heard to them referred to as, probably more usefully, respectively, duplicator, constructor, and eraser. Dup and Cons are 3 way nodes, whereas Er is a 1 way node, and networks made of only 1 or 3 way nodes can only be made with an even number of nodes. In interaction nets, there can also be “dangling edges” coming out of the 3 way nodes that don’t connect to anything, but these can be thought of as a special kind of the 1 way nodes. To illustrate, here are all the possible ways you can put together 2 nodes that can have these kinds of connections (I wrote the code for generating these):
In[]:=
Show[#,ImageSize->Medium]&/@trivalentGraphs[2,"danglingEdges"->True]//Row
Out[]=
In[]:=
trivalentGraphs[4,"danglingEdges"->True]//Row
Out[]=
But now we want the 3 way nodes to be either gamma or delta, and for the one way nodes to be either epsilon, or an empty dangling edge. In interaction nets, the order that the edges go around a node matter, and so there may be nets that look like duplicates if not for the fact that their ports have their edges connected in a different order. So here are all the ways one can do that with two nodes (where again, one, or in one case, two, of the “nodes” can actually just be a dangling edge / dangling edges):
In[]:=
nets2=interactionNets[2];
In[]:=
Multicolumn[myInetPlot/@nets2,5,Appearance->"Horizontal"]
Out[]=
​
​
​
There are 52 of these, including the empty interaction net, where both “nodes” are dangling edges, and so there are in fact no ports and nothing to see in the net itself.
In[]:=
Length[nets2]
Out[]=
52
You’ll notice that some of the nets have red in them. When the two pointy ends of a node are connected to each other, this means they are active, and that the net will evolve one step later from there.
There are 12 of these interacting ones.
In[]:=
interactable2s=Select[nets2,interactableNetQ];
In[]:=
Length[interactable2s]
Out[]=
12
In[]:=
Grid[myInetPlot/@iNetEvaluateList[#,5]&/@interactable2s,Frame->All]
Out[]=
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
As you can see, most of them just die out after a few steps. But two of them seem to be doing something rather interesting, though both appear to be doing the same interesting thing. Let’s look at one of them more closely:
This net seems to me at least to be growing in a rather complex way. This, I think, was the coolest finding of this project, though as you will see, someone else found a similar result before, coming form a very different / non-interaction net direction. But anyway it is interesting that one of the almost smallest possible interaction nets can grow in such an interesting / complex way. I’m not sure if this is a known result for interaction nets anyway, I couldn’t find anything about this result for interaction combinators, but definitely leave a comment if you find anything by anyone else about it in that area.
​
It does however appear that someone else has in fact seen this pattern, but again, coming from a different direction. This is going to seem like a completely random comment, but, when I was looking at this smallest growing network, I thought to myself that they looked a bit like some strange animal with a long nose, big cheeks, and pointy ears. Why would I mention this you may ask yourself. Because the shape actually rang a bell, I felt that I had seen it before. In a blog post about a totally different network system here, about halfway down the page, there is a similar looking network, I thought. From that page, highlighting mine:
Here’s the evolution of that system, which looks rather similar to the interaction net system:
Here’s the specific (one! See below) rewrite rule that generates the above evolution:
So far as I can tell, the two graph evolutions are the same. The nearby above system though is from a blog post by Stephen Wolfram where he was looking at all possible essentially arbitrary graph rewriting rules and seeing what they all do, whereas I am looking at a system with very specific rules, but just starting from different graphs. Dr. Wolfram was actually using these graph rewriting systems in an attempt to model the universe itself as a graph rewriting system believe it or not! Anyway there is a similarity in the systems we are looking at, in that the above images from Wolfram’s blog were not entirely arbitrary, but were all ordered graph rewrite rules of a certain type, and in interaction nets, as mentioned before, the order that the edges go into the nodes does matter.
​
A difference between the two systems though is that Wolfram was looking at systems in which there is essentially only one kind of node, and the nodes all interact according to the same one specific rule, whereas interaction nets are somewhat more complicated, using 3 types of nodes and 6 updating rules. Notably, in the interaction net case, there are only two kinds of nodes in the net, and there’s always a pairing of one of each node in each interaction that occurs in it. In this way, my understanding is that it is really only using one of the 6 rules, and the gamma and delta nodes are symmetric enough that they can apparently be modeled exactly by this simpler system that Wolfram found.
​
It is interesting to me that Wolfram apparently stumbled upon the rules for delta and gamma node interactions without, so far as I know, realizing he’d done so when he was just looking at the behaviour of all possible ordered graph rewriting systems of a certain kind.

Size 4

Here’s all the size 4 graphs including with dangling edges:
Let’s generate all the interaction nets then:
​
So there are about 9000 of them. Let’s narrow it down to just the ones of those that are able to evolve for at least one step:
​
So there are 4717 of these, so a bit over half of them.
Apparently 1443 of them are still updatable after 7 steps of network evolution, whereas the rest have halted. I spent a good amount of time looking through and exploring all of these. New behaviors outside of the size two ones were that they would get stuck in a loop, grow in a “line” like this one:
Or they’d make a “globular” structure like that neat size 2 one, except this time they didn’t have to be symmetric like that above one was:
So yeah really I didn’t find anything particularly exciting in the size 4 ones outside the size 2 ones, though there were many different types of globular structures that did all look rather complex while qualitatively similar to the one above. The ones that died out all died out within less than 10 steps, so there weren’t any that grew for a while before halting or anything.

Generating Larger Random Interaction nets

I also wrote some code to generate larger somewhat randomly generated interaction networks. I can’t say I found anything particularly new or interesting there, but I’ve included the associated notebook as an attachment to this post if anyone wants to try it out some more. As interaction nets are computationally universal, they should be able to do pretty much anything in theory, so it should be possible if maybe not simple to find ones that do some other interesting thing.

Discussion

It was neat to see what kinds of patterns the nets could generate. It was interesting to see that that simple interaction net corresponded to an ordered rewrite system I’d seen before.
I had kind of hoped maybe I’d see something like the generation of a network that clearly had a grid of 2 or 3 dimensions, but the graphs that did anything interesting that I found didn’t seem to want to stick to a nice integer amount of dimensions (besides a repetitive 1 dimensional result). It also would have been neat to have found a graph that grows in some interesting way but only rather slowly. It would be amazing to stumble upon “in the wild” an interaction net that does something that some other well known but different kind of system does, like emulating a cellular automaton from a single cell, or doing some other well known interesting computation like computing the digits of pi, or pointing towards emulating some new computational system like those but that nobody’s looked at much yet. But at least at first glance I haven’t noticed anything like that, so far. Possibly even with this flexible higher level system, searching the space still has a large-ish density of non-immediately-useful-to-humans programs.
More though could be done to search for these kinds of systems more, or to simply catalogue how quickly nets can grow, or which ones might grow for a while and then halt, and how long to they run for before doing so.

Appendix

Notes on files attached to this post

To run this code, download the notebook for this page, along with the attached files and put them all in the same folder before running.
​
Also, while writing this code, I implemented an additional option that I haven’t mentioned above, but that might be useful for further analysis of these networks, so I just thought I’d show how it works. The option allows one to generate only networks that have (or don’t have) certain kinds of “dangling edges”. The default behavior:
Is equivalent to writing:
Which allows for both empty dangling edges, and dangling edges that have “epsilon” nodes on them. One can also specify only epsilon nodes, only empty dangling edges, or no dangling edges at all, setting the “dangles” option to, respectively, “epsilons”, “dangle”, and None (without quotes). The options also work in the same way for the attached notebook for generating random interaction nets.
Another thing to note is that, as I said, I used Murzin’s code for evaluating / displaying the nets I generated. I threw together some of his code into a rough paclet, but since then Murzin has told me he’s generated a more well organized paclet that he’s published himself for doing general work with noded graphs. I’d have used it but I’d already put things together using Murzin’s older code, but for future reference, here is that newer paclet.

CITE THIS NOTEBOOK

Exploring the space of interaction nets (a graph rewrite based computer language)​
by Eric Parfitt​
Wolfram Community, STAFF PICKS, August 10, 2025
​https://community.wolfram.com/groups/-/m/t/3528318