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.

 

metaloop_1

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:

 

metaloop_2

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.

 

metaloop_3

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.

 

metaloop_4

In the 5th step we have conflict:

 

metaloop_5

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:

 

metaloop_6_d

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.

Bubbles!

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

Then the 5th step looks like this:

 

metaloop_6_b

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.

_____________________________________________________

Advertisements

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