Tag Archives: ouroboros

Lambda calculus inspires experiments with chemlambda

In the now deleted chemlambda collection I told several stories about how lambda calculus can bring inspiration for experiments with chemlambda. I select for this post a sequence of such experiments. For previous related posts here see this tag and this post.

Let’s go directly to the visuals.

Already in chemlambda v1 I remarked the interesting behaviour of the graph (or molecule) which is obtained from the lambda term of the predecessor applied to a Church number.  With the deterministic greedy algorithm of reductions, after the first stages of reduction there is a repeating pattern of  reduction, (almost) up to the end. The predecessor applied to the Church number molecule looks almost like a closed loop made of pairs A-FO (because that’s how a Church number appears in chemlambda), except a small region which contains the graph of the predecessor, or what it becomes after few rewrites.

In chemlambda v2 we have two kinds of fanouts: FO and FOE.  The end result of the reduction of the same molecule, under the same algorithm, is different: where in chemlambda v1 we had FO nodes (at the end of the reduction), now we have FOE nodes. Other wise there’s the same phenomenon.

Here is it, with black and white visuals

pred

Made by recording of this live (js) demo.

1. What happens if we start not from the initial graph, but from the graph after a short number of rewrites? We have just to cut the “out” root of the initial graph, and some nodes from it’s neighbourhood and glue back, so that we obtain a repeating pattern walking on a circular train track.

Here is it, this time with the random reduction algorithm:

bigpred_train-opt

I previously called this graph an “ouroboros”. Or a walker.

2. That is interesting, it looks like a creature (can keep it’s “presence”) which walks in a single direction in a 1-dimensional world.  What could be the mechanism?

Penrose comes to mind, so in the next animation I also use a short demonstration from a movie by Penrose.

bigpred_penrose-opt

 

3. Let’s go back to the lambda calculus side and recall that the algorithm for the translation of a lambda term to a chemlambda molecule is the same as the one from GLC, i.e the one from Section 3 here. There is a freedom in this algorithm, namely that trees of FO nodes can be rewired as we wish. From one side this is normal for GLC and chemlambda v1,  which have the CO-COMM and CO-ASSOC rewrites

convention_3

In chemlambda v2 we don’t have these rewrites at all, which means that in principle two diferent molecules,  obtained from the same lambda term, which differ only by the rewiring of the FO nodes may reduce differently.

In our case it would be interesting to see if the same is true for the FOE nodes as well. For example, remark that the closed loop, excepting the walker, is made by a tree of FOE nodes, a very simple one. What happens if we perturb this tree, say by permuting some of the leaves of the tree, i.e. by rewiring the connections between FOE and A nodes.

bigpred_train_perm-opt

The “creature” survives and now it walks in a world which is no longer 1 dimensional.

Let’s play more: two permutations, this time let’s not glue the ends of the loop:

bigpred_train_egg

It looks like a signal transduction from the first glob to the second. Can we make it more visible, say by making invisible the old nodes and visible the new ones? Also let’s fade the links by making them very large and almost transparent.

bigpred_train_egg_mist_blue

Signal transduction! (recall that we don’t have a proof that indeed two molecules from the same lambda term, but with rewired FO trees reduce to the same molecule, actually this is false! and true only for a class of lambda terms. The math of this is both fascinating and somehow useless, unless we either use chemlambda in practice or we build chemlambda-like molecular computers.)

4.  Another way to rewire the tree of FOE nodes is to transform it into another tree with the same leaves.

bigpred_tree-opt

 

5. Wait, if we understand how exactly this works, then we realize that we don’t really need this topology, it should also work for topologies like generalized Petersen graphs, for example for a dodecahedron.

dodecahedron_walker

 

This is a walker creature which walks in a dodecaheral “world”.

6. Can the creature eat? If we put something on it’s track, see if it eats it and if it modifies the track, while keeping it’s shape.

walker_bit-opt

So the creature seems to have a metabolism.

We can use this for remodeling the world of the creature. Look what happens after many passes of the creature:

walker_bit_new

 

7. What if we combine the “worlds” of two creatures, identical otherwise. Will they survive the encounter, will they interact or will they pass one through the other like solitons?

bigpred_bif

 

Well, they survive. Why?

8. What happens if we shorten the track of the walker, as much as possible? We obtain a graph wit the following property: after one (or a finite give number of) step of the greedy deterministic algorithm we obtain an isomorphic graph. A quine! chemlambda quine.

At first, it looks that we obtained a 28 nodes quine. After some analysis we see that we can reduce this quine to a 20 nodes quine. A 20-quine.

Here is the first observation of the 20-quine under the random algorithm

20_quine_50steps

According to this train of thoughts, a chemlambda quine is a graph which has a periodic evolution under the greedy deterministic algorithm, with the list of priority of rewrites set to DIST rewrites (which add nodes)  with greater priority than beta and FI-FOE rewrites (which subtract ndoes), and which does not have termination nodes (because it leads to some trivial quines).

These quines are interesting under the random reduction algorithm, which transform them into mortal living creatures with a metabolism.

____________

So this is an example of how lambda calculus can inspire chemlambda experiments, as well as interesting mathematical questions.

Walker eating bits and a comment on the social side of research

This post has two parts: the first part presents an experiment and the second part is a comment on the social side of research today.

Part 1: walker eating bits.  In this post I introduced the walker, which has been also mentioned in the previous post.

I made several experiments with the walker, I shall start by describing the most recent one, and then I shall recall (i.e. links to posts and vids) the ones before.

I use the chemlambda gui which is available for download from here.

What I did: first I took the walker and made it walk on a trail which is generated on the fly by a pair A-FOE of nodes. I knew previously that such a pair A-FOE generates a trail of A and FO nodes, because this is the basic behaviour of the Y combinator in chemlambda. See the illustration of this (but in an older version, which uses only one type of fanout nodes, the FO) here.  Part of it was described in the pen-and-paper version in the ALIFE14 article with Louis Kauffman.

OK, if you want to see how the walker walks on the trail then you have to download first the gui and then use the gui with the file walker.mol.

Then I modified the experiment in order to feed the walker with a bit.

A bit is a pair of A-FO nodes, which has the property that it is a propagator. See here the illustration of this fact.

For this I had to modify the mol file, which I did. The new mol file is walker_eating_bit.mol .

The purpose of the experiment is to see what happens when the walker is fed with a bit. Will it preserve its shape and spill out a residue on the trail? Or will it change and degenerate to a molecule which is no longer able to walk?

The answer is shown in the following two screenshots. The first one presents the initial molecule described by the walker_eating_bit.mol.

walker_eating_bit_step0
At the extreme right you see the pair A-FOE which is generating the trail (A is the green big node with two smaller yellow ones and a small blue one and the FOE is the big yellow node with two smaller blue ones and a small yellow one). If you feel lost in the notation, then look a bit at the description in the visual tutorial.

In the middle you see the walker molecule. At the right there is the end of the trail. The walker walks from left to right, but because the trail is generated from right to left, this is seen as if the walker stays in place and the trail at its left gets longer and longer.

OK. Now, I added the bit, I said. The bit is that other pair of two green nodes, at the right of the figure, immediately at the left of the A-FOE pair from the extreme right.

The walker is going to eat this pair. What happens?

I spare you the details and I show you the result of 8 reduction steps in the next figure.

walker_eating_bit_step8

You see that the walker already passed over the bit, processed it and spat it as a pair A-FOE. Then the walker continued to walk some more steps, keeping its initial shape.

GREAT! The walker has a metabolism.

Previous experiments.  If you take the walker on the trail and you glue the ends of the trail then you get a walker tchoo-tchoo going on a circular trail. But wait, due to symmetries, this looks as a molecule which stays the same after each reduction step. Meaning this is a chemlambda quine. I called such a quine an ouroboros. In the post Quines in chemlambda you see such an ouroboros obtained from a walker which walk on a circular train track  made of only one pair.

I previously fed the walker with a node L and a termination node T, see this post for pen and paper description and this video for a more visual description, where the train track is made circular as described previously.

That’s it with the first part.

Part 2: the telling silence of the expert. The expert is no lamb in academia. He or she fiercely protect the small field of expertise where is king or queen. As you know if you read this open notebook, I have the habit of changing the research fields from time to time. This time, I entered into the the radar of artificial chemistry and graph rewriting systems, with an interest in computation. Naturally I tried to consult as many as possible experts in these fields. Here is the one and only contribution from the category theory church.  Yes, simply having a better theory does not trump racism and turf protection.  But fortunately not everything can be solved by good PR only. As it becomes more and more clear, the effect of promotion of mediocrity in academia, which was consistently followed  since the ’70, has devastating effects on the academia itself. Now we have become producers of standardised units of research, and the rest is just the monkey business about who’s on top. Gone is the the trust in science, gone are the funds, but hey, for some the establishment will still provide a good retirement.

The positive side of this big story, where I only offer concrete, punctual examples, is that the avalanche which was facilitated by the open science movement (due to the existence of the net) will change forever the academia in particular. Not into a perfect realm, because there are no such items in the real world catalogue. But the production of scientific research in the old ways of churches and you scratch my back and I’ll scratch yours is now exposed to more eyes than before and soon enough we shall witness a phenomenon similar to the one happened more than 100 years ago in art, where ossified academic art sunk into oblivion and an explosion of creativity ensued, simply because of the exposure of academic painting along with alternative (and, mixed with garbage, much more creative artists) works in the historical impressionist revolution.

______________________________________________

 

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.

 

pred_round_9

 

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.

 

pred_round_4

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).

 

pred_round_5

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:

 

pred_round_6

 

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.

 

pred_round_7

 

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.

 

pred_round_8

 

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…

____________________________________________________________

 

 

 

Ouroboros predecessor (II): start of the healing process

Let’s continue from the place we stopped in  Ouroboros predecessor, another chemlambda reduction .  After the first reduction stage which involves 6 rewrites, we see that the signal is given for the start of the healing process.

 

pred_round_2

The signal for the healing is given by the beta reduction

L[59,59,23]  A[23,27,14] –beta–>

Arrow[59,14] Arrow[27,59]

The COMB moves are not figured. But they go like this in this case:

Arrow [59,14] Arrow[27,59] –COMB–>

Arrow[27,14]

and then

A[52,54,27] Arrow[27,14] –COMB–>

A[52,54,27]

In the third graph we see the element:

A[19,54,27]

which comes from yet another COMB move

A[52,54,27] Arrow[19,52] –COMB–>

A[19,54,27]

where the Arrow[19,52] comes from the FAN-IN move

FI[6,19,2] FO[2,52,53] –FAN-IN–>

Arrow[6,53] Arrow[19,52]

There are 8 rewrites per reduction step, starting from the 2nd figure. The repeating patterns are:

  • a train of 4 DIST patterns which travel along the external (in our arbitrary embedding in the plane)  ring of FO elements.
  • a “healing” pair which appears first time in the 3rd figure as A[30,50,31] L[31,30, 19]. This healing pair is consumed (by a beta move) each time, but is recreated. In the 4th figure we see it again as A[47,69,46] L[46,47,29], in the 5th figure appears a A[67,89,65] L[65,67,42]. It has the role to switch in the right position the ports of an A element, to form pairs A and FO which heal back the graph.
  • FI nodes in such a pattern so that at any step of the reduction only two FAN-IN moves are possible, one coming from a newly created DIST pattern, the other coming from an older FI node.

The number of nodes, from the 2nd to the 5th figure is the same.

What will happen next?

__________________________________________________________

Ouroboros predecessor, another chemlambda reduction

Well, let’s see if I learned a trick from the predecessor function from the post Answer to “what reduction is this?”.

I make an ouroboros from something like the Pred 8:

 

pred_round

 

We’re in the middle of the computation, what will give eventually, can you guess?

Next time!

__________________________________________________________