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.

Bubbles!

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.

_____________________________________________________

Ouroboros predecessor (IV): how the walker eats

Continues from  Ouroboros predecessor (III): the walking machine .  This time you have to imagine that the walker machine sits on a long enough train track.

The regularity of the train track is corrupted by a bit of food (appearing as a L node connected to a termination node), see the next (BIG) picture. It is at the right of the walker.

You can see (maybe if you click on the image to make it bigger) that the walker ingests the food. The ingested part travels through the walker organism and eventually is expelled as a pair L and A nodes.

 

 

Perhaps, by clever modifications of the walker (and some experiments with its food) one can make a Turing machine.

This would give a direct proof that chemlambda with the  sequential strategy is universal as well. (Well, that’s only of academic interest, to build trust as well, before going to the really nice part, i.e. distrbuted, decentralized, alife computations.)

_____________________________________________

Ouroboros predecessor (III): the walking machine

In the post   Ouroboros predecessor (II): start of the healing process   there is a curious phenomenon happening: there are 3 quasi-identical reduction steps, each involving 8 reductions.

That is because there is a walking machine in those graphs.

Explanations follow.

Recall the reduction strategy:

• at each step we do all the possible (non-conflicting) graph rewrites involving the moves BETA, FAN-IN, DIST, LOC PRUNING, from left to right only. See the  definition of moves post.
• then we do all the COMB moves until there is no COMB move possible (also from left to right only).
• then we repeat.

In the drawings the COMB moves are not figured explicitly.

Let’s come back to the walking machine. You can see it in the following figure.

 

In the upper side of the figure we see one of the graphs from the reduction of the “ouroboros predecessor”, taken fom the last post.

In the lower side there is a part of this graph which contains the walking machine, with the same port names as in the upper side graph.

What I claim is that in a single reduction step the machine “goes to the right” on the train track made by pairs of FO and A nodes. That is why some of the reduction steps from the last post look alike.

One reduction step will involve:

• 8 reduction moves, namely 4 DIST, 2 BETA, 2 FAN-IN
• followed by some COMB moves.

Let’s start afresh, with the walking machine on tracks, with new port names (numbers).

 

For the sake of explanations only, I shall do first the two BETA and the two FAN-IN moves, then will follow the four  DIST moves. There is nothing restrictive here, because the moves are all independent, moreover, according to the reduction strategy, these are all the moves which can be done in this step, and they can be done at once.

OK, what do we see? In the upper side of this figure there is the walking machine on tracks, with a new numbering of ports. We notice some patterns:

• the pair of L and A nodes, i.e. L[1,2,3] A[2,35,1]  which, in the figure, appears over the A node  A[3,4,5]. Remark that A[3,4,5] would make a good pair (i.e. a part of the “track”) with FO[38,4,36], if it would have the ports  “3” and “5”  switched.
• the pattern of 5 red FI and L nodes from the middle upper side of the walking machine
• the 3 green and 2 red nodes which make a kind of a pentagon at the right side of the walking machine
• the 2 DIST right patterns for application node (green) and the 2 DIST right patterns for the lambda node (3 red, one green) which are like 4 train cars on the track.

In the lower part of the figure we see what the graph looks like after the application of the 2 BETA moves and the 2 FAN-IN moves which are possible.

Let’s look closer. In the next figure is taken the graph from the lower part of the previous figure. Beneath it is the same graph, only arranged on the page such that it becomes simpler to see the patterns. Here is this figure:

 

 

Recall that we are working with graphs (called g-patterns, or molecules), not with particular embeddings of the graphs in the plane. The two graphs are the same, only the drawings on the plane are different. Chemlambda does not matter about, nor uses embeddings. This is only for you, the reader, to help you see things better.

OK, what do we see:

• there are some arrows (edges) with 2 names on them, this is because there are Arrow elements which still exist because we have not done yet the COMB moves
• we see that already there is a new pair of A and FO nodes (in green, at the left of the lower graph). At the right of the lower graph we see that there is a missing piece of train track which “magically” appeared at the left.
• then, at the right of the piece of the train track piece which appeared at left, the walking machine already looks like before the moves, in the sense that there is an A node  with “switched” ports, there is a pair of green and red nodes hovering over it,
• moreover the pattern of 5 red nodes is there again, …

… but all these patterns are not the old ones, but new ones!

The 4 train cars made by DIST patterns are missing! Well, they appear again after we do the remaining 4 DIST moves.

In the next figure we see the result of these 4 DIST moves. I did not numbered the new edges which appear.

 

 

I also did the COMB moves, if you look closer you will see that now any arrow either has one or no number on it. The arrows without numbers are those appeared after the DIST moves.

Let’s compare the initial and final graphs, in the next figure.

 

 

We see that indeed, the walking machine went to the right! It did not move, but instead the walking machine dismembered itself and reconstructed itself again.

This is of course like the guns from the Game of Life, but with a big difference: here there is no external grid!

Moreover, the machine destroyed 8 nodes and 16 arrows (by the BETA, FAN-IN and COMB moves) and reconstructed 8 nodes and 16 arrows by the DIST moves. But look, the old arrows and nodes migrated inside and outside of the machine, assembling in the same patterns.

This is like a metabolism…

____________________________________________________________