Y again: conflict!

We proved in    arXiv:1403.8046 [cs.AI]  ( link to the published  article) that in chemlambda the molecule which represents the Y combinator is a gun which shoots pairs of FO and A nodes. See there the sequence of reductions which was considered.

This time  let’s not care about staying in lambda calculus and let’s take the simplest reduction strategy, to see what happens.

We posit in the frame of g-patterns from the expository posts  part I  and part II (definition of g-patterns) and part III (definition of moves) and part IV (g-patterns for lambda terms 1st part) and part V (g-patterns for lambda terms 2nd part) and part VI (about self-multiplication of g-patterns)  and part VII (an example of reduction) .

We take the following reduction strategy:

  • we start with a g-pattern and we reduce it sequentially
  • at each step we identify first all the LEFT patterns from the following moves: beta, DIST, FAN-IN,
  • we do the moves from LEFT to RIGHT
  • we identify and do all possible COMB moves from LEFT to RIGHT
  • repeat until no move available OR until conflict.

What’s conflict? We shall see one.

Mind that this is a very stupid and simplistic strategy, which does not guarantee that if we start with a g-pattern which represents a lambda term then we stop by having a g-pattern of a lambda term.

It does have it’s advantages, though.

OK, so let us start with the g-pattern of Y applied to something. 

In general, with g-patterns we can say many things. As any combinator molecule, when represented by a g-pattern, the Y combinator has only one free port, let’s call it “b”. Thus Y appears as a g-pattern which we denote by Y[b].

Suppose we want to tart the reduction from Y applied to something. This means that we shall start with the g-pattern

A[b,a,out] Y[b]


Look what happens when we apply the mentioned strategy.

(Advice: big picture, click on it to see it clearly and to travel along it.)



Here is a conflict: at one step we have two LEFT patterns, in this case

L[o,p,i] A[i,p,v]   , which is good for a beta move


A[i.p.v] FO[v,q,a1]  , which is good for a DIST move.

The patterns contain a common graphical element, in this case A[i,p,v], which will be deleted during the respective moves.

CONCLUSION: with this strategy we have a gun which shoots one pair of FO and A nodes, but then it got wrecked.

What to do then?

The human way is to apply

When in trouble or in doubt

Run in circles, scream and shout

for a moment, then acknowledge that this is a stupid reduction strategy, then find some qualities of this strategy, then propose another which has those qualities but works better, then reformulate the whole problem and give it an unexpected turn.

The AI way is to wait for somebody to change the reduction strategy.



3 thoughts on “Y again: conflict!”

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