What is Chemlambda? In which ways could it be interesting for a mathematician?

Question

I${}^{*}$ have randomly come across a couple of websites (Chemlambda project, chorasimilarity) that seem to be about a certain "thing" (a computer program, I think) called Chemlambda that does "stuff" with some kind of decorated graphs called molecules according to some "rules".

${}^*$ Disclaimer: I don't know anything about computer science, computability theory, rewriting systems, distributed computing, or the like.

Chemlambda molecules look more or less like this:

and can make up much more complicated shapes:

Looks cool, doesn't it?

Also, there are links to very cool looking youtube videos which show such decorated graphs in action, such as this one or this one, and a gallery of videos perhaps trying to explain some elementary Chemlambda "operations". Notice that the title of one of the youtube videos contains "factorial of $4$",  so it seems to suggest that some kind of computation is being performed...

Question 0. Does all this contain some legitimate and/or interesting maths  ̶o̶r̶ ̶i̶s̶ ̶i̶t̶ ̶b̶u̶l̶l̶s̶h̶i̶t̶  ?

There are some articles on the arXiv authored by M. Buliga, such as this one or this one, that are relevant to the topic.  Notice that the second linked article is coauthored with L.H. Kauffman, who is a well known mathematician (for reasons unrelated to this project).

Question 1. What is Chemlambda?

Provided the definitions on which it is based are mathematically sound/rigorous, I would like to roughly understand what this program does with such decorated graphs and why it would be interesting (from the point of view of mathematical logic, or more generally of mathematics) to consider such kind of operations with decorated graphs. Skimming through the websites and the articles, I wasn't able to precisely understand what the point of Chemlambda is, besides providing cute animations:

Question(s) 2. As far as I -kind of- understand, Chemlambda graphically models $lambda$-calculus, so it's suitable for
  computation. Why would one want to encode computations graphically?
  Does it provide any conceptual insights or practical advantages? How are, roughly, inputs encoded and the output read off the resulting molecules? Are the operations on molecules performed deterministically or randomly? If randomly, how?

Marius Buliga · Answer

UPDATE (2020) There is now chemlambda.github.io which collects all the chemlambda related projects and articles. For the history of chemlambda see arXiv:2007.10288 or the associated html version Graph rewrites, from emergent algebras to chemlambda.
Author here. I think the most informative link is the GitHub repository (and links therein). I'll try to answer as short as possible to questions 1 and 2 and then comment on the mathematical relevance.
Question 1. What is Chemlambda? Chemlambda is an asynchronous graph rewrite automaton. There are 3 parts: graphs, rewrites and the algorithm of reduction. Source, alternative formalism of sticks and rings which might be interesting for this community.
The graphs are called molecules and they are oriented ribbon graphs, with the nodes decorated with colors. Molecules are built from 3valent nodes (A, L, FI, FO, FOE), a 2valent node Arrow and 1valent nodes FRIN (free in) FROUT (free out) T (termination). All the information (oriented ribbon graph, type of nodes) can be encoded as a 3 colors decoration of nodes and half-arrows.
As a graph rewrite system is of the same family as interaction nets. List of rewrites here.
The algorithm of the application of rewrites is very important as well. There are two of them and they are both the most stupid ones: deterministic, with a priority of moves in case there are conflicts (i.e. overlapping patterns to be rewritten), or the random one.
Question 2. Chemlambda, with the random reduction algorithm, is a model of computation which has the properties: is Turing universal, random and local, i.e. there is a small number N, a priori, so that the rewrites or the decision to apply them act (or need) at most N nodes and half-arrows of the graph.
On purpose, there are no global notions used: there is no typing, there is no categorical approach considered, there is no equivalence relation obtained from the closure of rewrites application, there is no limitation on the possible graphs, nor there is any other algorithm which has as input the whole molecule (graph) and as output a decoration of particular half-edges (as is the case with the association of a lambda term with its AST and then back from the AST to the term).
Chemlambda can model untyped lambda beta (but not eta) calculus. As well, by the introduction of supplementary 2valent nodes, it can as well model Turing machines with multiple heads, working asynchronously.
Comments. Chemlambda was not made with the goal to model lambda calculus, nor is lambda calculus the main interest here. I arrived to chemlambda from sub-riemannian geometry, where I used uniform idempotent right quasigroups, aka emergent algebras. That formalism can, almost entirely, be written as a graph rewrite system and the question I had was: is it Turing complete? The exact relation between chemlambda and emergent algebras is still work in progress, but basically emergent algebras resemble very much to a type system for chemlambda (which shows that emergent algebras, as they are presently, are too limited and hide something more interesting).

What is Chemlambda? In which ways could it be interesting for a mathematician?

One Answer

Add your own answers!

Ask a Question