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?

  • 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. – Sylvain JULIEN May 15 at 15:56
  • 4
    it would seem that the 7 questions & answers listed here cover much of the ground in the OP. – Carlo Beenakker May 15 at 18:21
  • @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). – Qfwfq May 15 at 19:01
  • It's worth pointing out that the first video in the gallery of videos is actually interactive and quite fun. – James Smith May 15 at 20:07
  • 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. – Marius Buliga May 15 at 22:32
up vote 11 down vote accepted

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

  • 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). – Qfwfq May 15 at 22:57
  • So, chemlambda has a set of local rules (that can be chosen to be random or deterministic) that, given a molecule, produce another molecule until eventually the process halts. And this formalism is Turing complete: can perform any computation. Also it is a simplified formalism that resembles (but is not identical to) certain structures that appear in sub-riemannian geometry and amount to a graph rewriting system but are not known to be Turing complete. (...) – Qfwfq May 15 at 23:14
  • 1
    (...) 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? – Qfwfq May 15 at 23:19
  • 2
    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. – Marius Buliga May 16 at 7:36
  • 3
    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. – Marius Buliga May 17 at 18:18

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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