When priority matters

I continue with the analysis of chemlambda with the very simple sequential strategy. In this post I want to show you that priority really matters, by using an old example from the Metabolism of loops.

The goal is to see how the g-pattern of the combinator

(Lx.xx) (Lx.xx)

reduces in chemlambda with the sequential strategy.

See the 1st part and 2nd part of the description of the conversion of lambda terms into g-patterns.

The simple sequential strategy is the following: at each reduction step do the following:

  • if no LEFT patterns of the moves BETA, DIST, FAN-IN are present in the g-pattern, then stop, else
  • identify the LEFT patterns of the moves BETA, DIST, FAN-IN. If there is a graphical element which is part of two distinct patterns then apply a PRIORITY  CHOICE
  • apply the moves from LEFT to RIGHT
  • apply the COMB moves until no Arrow element is present
    can be eliminated
  • repeat.

The PRIORITY CHOICE means a predefined choice between doing one of the two moves in conflict.

In this post it will be about the priority between BETA and DIST moves.

Mind that the PRIORITY CHOICE is fixed before the start of the computation.

However, in the following I shall mention the choice when it will be needed.

OK, so let’s start with the g-pattern which represents the well known combinator (Lx.xx) (Lx.xx).  Is clear that as a lambda term it has no normal form,  because it transforms into itself by a beta reduction (so is a sort of a quine, if quines would have an interesting definition in lambda calculus).

As previously, you shall see that we depart quickly from the lambda calculus realm, and we go to some straightforward directions, nevertheless.

The first figure describes the first reduction step.



The g-pattern obtained after this first step is the one which appears as the starting point of the Metabolism of loops post.

The 2nd step is described in the next picture:



Technically we are already outside lambda calculus, because of the fanin node FI[15,12,6].  (We don’t split the computation into pure reduction and pure self-multiplication.)

Let’s see the 3rd step.



Look well at the g-pattern which we get after the 3rd step, you’ll see it again, maybe!

The 4th step is the one which will prepare the path to conflict.



In the 5th step we have conflict:



The 5th step finishes in a different manner, depending on the PRIORITY CHOICE (which is fixed from the beginning of the computation).

Let’s suppose that we choose DIST over BETA. Then the 5th step looks like this:



Wow, the g-pattern after the 5th step is the same as the g-pattern after the 3rd step, with a loop graphical element added.

This means that further the computation will look alike the 4th step, then 5th step again (with the same priority choice, which is fixed!). A new loop will be generated and the computation will never stop, producing an endless string of loops.


Now, let’s see what happens if the PRIORITY CHOICE is BETA over DIST.

Then the 5th step looks like this:



The 5th step produced 2 loops and the shortest ouroboros, a fanout node with one out port connected to the in port, namely FO[13,1,13].

The computation then stops!


So, depending on the priority choice, we have either a computation which produces bubbles without end, or a computation which stops.

It is logical. Indeed, if the priority choice is DIST over BETA, this induces the choice of increasing the number of nodes of the g-pattern. From here, it may happen, as it is the case in this example, that a cyclic behaviour is induces.

On the other side, the priority choice BETA over DIST decreases the number of nodes, thus increasing the chances for a computation which stops eventually.

Both choices are good, it depends on what we want to do with them. If we want to compute with graphs resembling chemlambda quines, because they look like living organisms with a metabolism, then the choice DIST over BETA is a good one.

If we want to have a computation which stops (dies, would say a biologist) then BETA over DIST seems better.



2 thoughts on “When priority matters”

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