This post continues from GLC actors, what are for and why are interesting? , which introduced the article GLC actors, artificial chemical connectomes, topological issues and knots , arXiv:1312.4333, written with Louis Kauffman. The article describes a common project of the authors and members of ProvenSecure Solutions, especially until now and in no particular order Stephen P. King, Rao Bhamidipati, Jim Whitescarver, Ken Williams, Keayi Cora, Paul Dube, Allen Francom, Arek Mateusiak, Roman Anderson.
There are three main ideas which are behind GLC actors distributed computing. In this post I want to write in more detail about the first one.
The model is not based on signals circulating through wires, passing through gates.
There is nothing flowing through the arrows of a GLC graph! A stumbling block in the path of absorbing this idea is that Graphic lambda calculus (i.e. GLC) does have a sector which is equivalent with untyped lambda calculus (without eta reduction). The post Conversion of lambda calculus terms into graphs describes an algorithm for associating a GLC graph to a lambda calculus term. The starting point of the algorithm is the syntactic tree of the term.
The syntactic tree is something which is aptly described as a graph with arrows and nodes, such that through the arrows (or wires) flow variables or terms and with the nodes (application and abstraction) which are like gates which take as inputs variables or terms, process them and spill on the output terms.
To see a graph in this way is equivalent to decorating it’s arrows according to the following rules:
After all, the graphs obtained this way are very much resembling to the lambda graphs studied by Wadsworth and Lamping, the differences being small, among them that these graphs are an oriented version of the lambda graphs and also there is something “wrong” with the orientations of arrows of the abstraction node (one input, two outputs, thus not the graph of an operation). Even the graphic beta move is very much like the beta reduction as described by Lamping.
But this is misleading. GLC graphs cover much more than lambda graphs, i.e. the lambda calculus sector of GLC contains only a part of all GLC graphs. Moreover, the graphic beta moves applies everywhere, not only on (the equivalent of) lambda graphs.
A graph which represents a lambda calculus term can be seen as a fancy version of a syntactic tree, thus we may imagine that the graph is made by wires and gates, with signals (variables or terms) which flow in the direction indicated by the arrows.
But there are plenty of other GLC graphs which can’t be seen like this. Look for example at the following figure (which appears as figure 3 in arXiv:1312.4333 )
If you try to see the graph from (a), left hand side, as one with signals circulating through gates, then you are in trouble, can you see why? (something about infinite loops and fixed points) You may try to decorate it as explained in the first figure of the post, but you will not succeed without introducing spurious relations between the terms used for decoration. The same remark applies to the graph from (b), right hand side.
The same remark applies to the graph from the upper part of the following figure, taken from the post Packing and unpacking arrows in graphic lambda calculus .
(In this old figure, at the end I use “elimination of loops”, i.e. loops without nodes can be erased or added.)
The thing is that we don’t even need to think in terms of flows of signals.
This is related to something mentioned in a previous post, Model of computation vs programming language in molecular computing, which is about a discussion on a G+ post by John Baez, which may have looked a bit strange. In fact, what I wrote there was with GLC in mind, see this:
6. Among the specifications for a “programming language for chemistry” are the following: [ … ]
- (b) purely syntactic (in particular no names management, nor input-output signalling),
- (c) (maybe an aspect of (b), but not sure) no use of evaluation in computation (strategy).
Let me come back to the fact that you can’t decorate any graph in GLC according to the rules from the first figure of the post. You may say, well, then let’s concentrate only on those GLC graphs which can be decorated, after all we can decorate all GLC graphs which represent lambda calculus terms.
That would be a big mistake. (This is a beaten path, moreover.) Because there is no local check on a graph which would allow to decide if the said graph can be decorated. It would be therefore in contradiction with the second idea, the one of “locality”. The contradiction would be so severe, that it would destroy the GLC calculus.
Recall that the only reason for that big mistake would be that you want to keep your image about signals flowing through arrows and gates. Just a bad thinking habit.