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…






4 thoughts on “Ouroboros predecessor (III): the walking 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