In the post Y again: conflict! I took the most obvious reduction strategy (sequential) and applied it to the reduction of the “Y combinator applied to something”. The reduction ended in conflict between two moves which compete for the same g-pattern.
Then, in the post Y again:compete! I took in parallel the two possible outcomes of the conflict. The contenders have been branded as fast shooting cowboys, offering a show.
Surprisingly, both possible paths of reduction ended in a very simple version of the Y combinator.
Only that the very simple version is not one coming from lambda calculus!
Indeed, let’s recall who is the Y combinator, seen a g-pattern in chemlambda.
In lambda calculus the Y combinator is
Lx.( (Ly.(x(yy)) (Ly.(x(yy)) )
As a molecule, it looks like this.
L[a,x,o] A[b,c,a] FO[x,y,z]
L[e,d,b] FO[d,f,g] A[f,g,h] A[y,h,e]
L[j,i,c] FO[i,l,m] A[l,m,k] A[z,k,j]
Applied to something means we add to this g-pattern the following:
with the meaning that Y applies to whatever links to the port “p”. (But mind that in chemlambda there is no variable or term passing or evaluation! so this is a way to speak in the lambda calculus realm, only).
The two mentioned posts about Y again led to the conclusion that the g-pattern “Y applied to something” behaves (eventually, after several reductions) as the far more simple g-pattern:
A[o,p,u] (i.e. “applied to something at port “p”)
Now, this means that the Y combinator g-pattern may be safely replaced in computations by
or, in graphical version, by
But this is outside lambda calculus.
It is far simpler than the Y combinator from lambda calculus.
The same happens with other lambda terms and reductions.(see for example the post Actors for the Ackermann machine, for another example. Incidentally, the analysis of the Ackermann machine, i.e. the graph which behaves like the Ackermann function, gave me the idea of using the actor model with GLC. This evolved into arXiv:1312.4333.).
This shows the fact that chemlambda, even with the dumbest sequential reduction strategy (ok, enhanced in obvious ways so it solves conflicts), can do more with less fuss than lambda calculus.
By looking on the net (recall that I’m a mathematician, therefore excuse my ignorance in CS well known people, I’m working on this), I can’t but wonder what chemlambda would give in relation with, for example:
- the Reduceron of the Plasma group
- other graph reduction machines
- and even with the various Krivine machines.
Of course, the dream is to go much, much further. Why? Because of the List of Ayes/Noes of the artificial chemistry chemlambda.