Y again: conclusion!

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.



As g-pattern, it looks like this (see this post  and this post for the conversion of lambda terms into g-patterns):

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


FO[a,c,d] A[c,d,b]

Now, this means that the Y combinator g-pattern may be safely replaced in computations by


FO[a,c,d] A[c,d,b]

or, in graphical version, by



But this is outside lambda calculus.

So what?

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:

Of course, the dream is to go much, much further. Why? Because of  the List of Ayes/Noes of the artificial chemistry chemlambda.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s