The Y combinator in graphic lambda calculus and in the chemical concrete machine

A simpler computation than the one with the Ackermann machine concerns the Y combinator.  Seen as a chemical reaction network, it looks like this for graphic lambda calculus. In the figure “A” is any graph in GRAPH which has only one exit arrow, for example a combinator graph.

ycombi_2

One might prefer to not use the GLOBAL FAN-OUT move. That’s possible, by passing to the chemical concrete machine formalism. The chemical reaction network is a bit different. (Notice the move PROP+, which is a composite move defined in the post Chemical concrete machine, detailed (VI). )

ycombi_3

Lots of interesting things happen, among them we notice the appearance of  stacks of “elementary units from the last post. so in the chemical concrete machine version of the behaviour of the Y combinator, the machine counts the number of times A should be replicated, if known (that’s a kind of lazy evaluation, if evaluation would make sense in this formalism).

___________________________

Advertisements

One thought on “The Y combinator in graphic lambda calculus and in the chemical concrete machine”

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