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:

enter image description here

and can make up much more complicated shapes:

enter image description here

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?

  • 1
    $\begingroup$ From what I understand from his blog, Buliga attempts to build a way to make space computable. Chemlambda can be viewed as an artificial chemistry but I think it's more than that : it seems to consist in building space as an emergent dynamic reality from a kind of graphic $ \lambda $ -calculus. If I'm right (the best is to ask Buliga directly), the potential applications are enormous. $\endgroup$ May 15 '18 at 15:56
  • 4
    $\begingroup$ it would seem that the 7 questions & answers listed here cover much of the ground in the OP. $\endgroup$ May 15 '18 at 18:21
  • $\begingroup$ @Carlo Beenakker: thank you for the link, that I missed. Actually I don't fully understant the questions n. 1 and 2, but they're probably related to mine. Questions from 3 to 7 seem more unrelated to my OP. I'm going to read the answer(s). $\endgroup$
    – Qfwfq
    May 15 '18 at 19:01
  • $\begingroup$ It's worth pointing out that the first video in the gallery of videos is actually interactive and quite fun. $\endgroup$ May 15 '18 at 20:07
  • $\begingroup$ Other than the links from my answer I highly recommend the Haskell version which, programming wise is much more clear to understand, but to my defense, on experiments is 500 times slower than my awk contraptions. $\endgroup$ May 15 '18 at 22:32

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).

  • $\begingroup$ Wow an answer from the author. Thank you very much for spending the time for writing it! Especially the last paragraph is new to me (I mean, I didn't get it by very quickly skimming through the online material). $\endgroup$
    – Qfwfq
    May 15 '18 at 22:57
  • 1
    $\begingroup$ (...) I find it quite surprising that sub-riemannian geometry had something to do with computation! Do you think that analogous phenomena could be found in other domains of mathematics (not obviously related to computation)? What are, essentially, the features of sub-riemannian geometry that ultimately lead to the "emergent" structures? $\endgroup$
    – Qfwfq
    May 15 '18 at 23:19
  • 3
    $\begingroup$ Sub-riemannian geometry is fascinating. A SR manifold is metrically a fractal but it is also smooth with respect to a differential calculus discovered by Pierre Pansu. It appears in physics too: non-holonomic manifolds (i.e. bikes on roads) are SR, the unit sphere in a complex Hilbert space is SR, the Heisenberg groups are the equivalent of linear SR spaces, a sort of non-commutative version of a vector space. Nothing from the fundamentals of differential geometry and calculus works like expected. $\endgroup$ May 16 '18 at 7:36
  • 3
    $\begingroup$ I don't know. What is interesting about SR is that it's like hyperbolic geometry for somebody who wants to understand more about the axiom of parallels. In knot theory, topology, physics there's lots of graphical tools based computations. Very high level though. All of them, SR included (which is new and low level) look almost like the same graph rewrites, variously decorated (typed?). So I don't know but I guess chemistry is even more intriguing. Maybe is a trend after the historically first models of computation based on words. $\endgroup$ May 17 '18 at 18:18
  • 1
    $\begingroup$ In case anybody interested, I opened the github repository EM which contains a working draft for an article which treats emergent algebras as a term rewrite system, with the final goal to rigorously connect emergent algebras with chemlambda. I don't know if it will work collaboratively, but I give it a try. $\endgroup$ May 22 '18 at 8: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.