Category Archives: chemlambda

Experimental generation of anharmonic lambda calculus (I)

UPDATE: This is from yesterday 15.10.2019. It gives the possible RHS of DIST rewrites in a more precise way, compatible with the 6 nodes: A, FI, D (port 2 “in”) and L, FO, FOE (port 2 “out”) (each node has port 1 “in” and port 3 “out”). Moreover which can be decorated with generic dilations which satisfy em-convex. It turns out that there are exactly two possibilities for each rewrite. However, there are fewer than 3^36 rewrite systems which are potentially interesting, because many of these rewrites inhibit others.

For example all the rewrites used in  the working version of kali are there (with the exception of those involving the node FO, there is a separate treatment for this node; also I ignore for the moment the rewrites invoving T and I take for granted the 3 beta-like rewrites, which are not generated by the rhs.js script, because they are not DIST rewrites).The version I have today shortens the list a lot and soon enough will be merged into a more explorable version of kali.

______

How many rewrites are possible in anharmonic lambda and how do they relate one with the other? Is there a way to discover experimentally the best collection of rewrites? I think it is and that’s what I’m doing right now.

Let me explain.

Suppose we start by the anharmonic group, isomorphic with S(3), or why not we start with S(4), with an eye into the relation it has with projective geometry. But basically we want to associate to every element of the group (call it G) a trivalent node with named ports “1”, “2” and “3”, such that we can decorate the edges of a graph made by such nodes by “terms” which are somehow relevant with respect to the geometric nature of the group G (either S(3) as the anharmonic group, or S(4) as it appears in projective geometry). For the moment how we do that, or why are we doing it, or even what that has to do with lambda calculus are irrelevant questions.

There are two big possibilities further.

Either we work with graphs with undirected edges, but we restrict the patterns which trigger rewrites at pairs of nodes connected via the ports “3”, i.e. at pairs of nodes linked by an edge which connects the port “3” of on enode with the port “3” of the other. For example this is the case in Interaction Combinators. The advantage is that there will never be conflicting rewrites.

Or we work with graphs with directed edges, we attach orientations to ports (say ports “1” is always “in”, i.e. the orientation point to the node, the port “3” is always “out” and the port “2” may be “in” or “out”, depending on the node type) and we ask that any edge connects a port which is “in” with a port which is “out”. Then we look for patterns which trigger rewrites ahich are made by a pair of nodes linked by an edge which connects a port “3” with a port “1”. This is like in chemlambda. The advantage here is opposite: we allow conflicting rewrites.

So in either case we think about rewrites which have as LHS (left hand side) a pair of nodes, as explained, and as RHS (right hand side) either no node (actually two edges), like in the case of the beta rewrite, or 4 nodes. The pattern of 4 nodes should be like in Interaction Combinators (say like GAMMA-DELTA rewrites) or like the DIST rewrites in chemlambda.

If I take the second case, namely graphs with oriented edges, as explained. how many different rewrites are possible? More precisely, denote a node with a “+” if the port “2” is “in” and with a “-” if the port “2” is out. Then, how many rewrites from 2 nodes to 4 nodes, in the pattern DIST, are possible?

Doing it by hand is dangerous, so we better do it with a program. >We are looking for patterns of 4 nodes arranged like in DIST rewrites, each node being a “+” or a “-” node, with oriented edges, so that the 4 half edges (or external ports)  have the same orientation as the corresponding ones of the  LHS pattern made of 2 nodes (“+” or “-“). How many are they?

There are 4 cases, depending on the LHS nodes, which we denote by “+,+”, “-,-“, “+,-” and “-,+”.

I was surprised to learn from programs that theer are 386=16X23 possible RHS patterns, divided into 80=16X5, 80=16X5, 112=16X7 and 96=16X6 patterns.

While I can understand the 16X part, the 5,5,7,6 are strange to me. The 16X appears from the fact that for a node “+” we can permute the “1”,”2″ ports without changing the edges orientations, and similarly for a node “-” we can permute the “2” “3” ports with the same (lack of) effect.

Now let’s get further. We look now at the nodes which are decorated with elements of the group G, or say the group G acts somehow on the set of node types which has as many elements as G. We look for rewrites from LHS to RHS such that the decoration of the external ports does not change during the rewrites. This imposes strong restrictions on the choice of nodes (and it means something geometrically as well).

Not any possible rewrite can be accepted though. For example we reject rewrites with the property that the RHS contains a copy of the LHS. So each rewrite has associated a collection of rewrites which are inhibited by it. This will place restrictions on the collections of rewrites which we may choose for our calculus.

We reject also rewrites whose RHS contain a copy of the LHS of a rewrite we like, like the beta rewrite.

We reject rewrites which have the RHS made such that the external ports will all be “2”, because such a pattern will last forever during further rewrites.

Still when we look at what is left we see that we have about |G|X|G| LHS patterns  and much more RHS choices, so there will still be many possible calculi.

We may look for symmetries, related to the action of G on the node types and we may ask: which is the most (or a most) symmetric collection and which will be a least symmetric (but maximal in number)?

Or we may say that the human mind is feeble and let the collections compete, by reducing a family of graphs. Take lambda calculus and some tests and let the possible collections compete. Take emergent algebras and some tests and do the same. Or even look for collections more fit for certain chosen tests from lambda calculus or others.

Who will win?

Anharmonic lambda calculus (II)

Some news after the anouncement of kali, or anharmonic lambda calculus. I use again two pages, which are updated in tandem:

 

At the moment I write this post the github.io version is more recent. I think the termination rewrites are better than before.

There is still some work on the exact choice of rewrites, among the many possible which are compatible with the underlying geometric structure. But you can see by looking at kali24.js that there is some connection between the nodes and the anharmonic group.

All this will be explained when I’ll arrive to the most satisfying version.

I added to the lambda calculus examples some more, not lambda calculus ones. Among them the much discussed 10-node quine and also the most amazing molecule I discovered until now. It appears in the menu as “10 nodes sometimes becomes quine from [graph A-L-FI-FOE 540213]” and please do reload it often and let it unfold. For an archived video see this one. It is a graph which basically shatters the notion that a quine is enough, conceptually, to describe life. More simply put, it can evolve in so many ways, among them in a chemlambda quine way, but not uniquely. Amazing.

You can see it also on the menu of the find a quine page. There the graphs look more compact and you can see more of the overall structure, but less the detailed linking of nodes.

Coming back to kali24, the chunk which I need to explain first is what does it have to do with em-convex. That is an enriched lambda calculus which describes my work on emergent algebras. It ends with the proof that in the presence of an axiom called “convex”,  we end up with usual vector spaces over terms of type N (in the paper) and that also the term of type N have an em calculus themselves, which is a way of saying that we recover on them a structure which is like the Riemann sphere.

What is not proved are two things: (1) is  there is a graphical rewrite system which can reproduce the proofs of em-convex, under the algorithm of rewrites used with chemlambda? (2) can we dispense of the lambda calculus part (the abstraction and application operations) and redo everything only with the pure em calculus?

Back to earth now, just for the fun, don’t you think that a geometrical model  of lambda calculus on the Riemann sphere would be nice?

Kali: anharmonic lambda calculus

You can play with some examples of lambda terms (SKK, Y combinator, Omega combinator, Ackermann(2,2), some duplications of terms, lists, Church numbers multiplications). It is important to try several times, because the reduction algorithm uses randomness in an essential way! This justifies the “reload” button, the “start” which does the reduction for you (randomly), the “step” which choses a random reduction step and shows it to you. Or you may even use the mouse to reduce the graphs.

It may look kind of alike the other chemlambda reductions, but a bit different too, because the nodes are only apparently the usual ones (lambdas, applications, fanins and fanouts), in reality they are dilations, or homotheties, if you like, in a linear space.

I mean literary, that’s what they are.

That is why the name: anharmonic lambda calculus. I show you lambda terms because you are interested into those, but as well I could show you emergent (actually em-convex) reductions which have apparently nothing to do with lambda calculus.

But they are the same.

Here is my usual example Ackermann(2,2), you’ll notice that there are more colors than precedently:

kali24-ackermann-2-2

The reason is that what you look at is called “kali24”, which for the moment uses 7 trivalent nodes, out of 24 possible from projective space considerations.

I will fiddle with it, probably I’ll make a full 24 nodes versions (of which lambda calculus alone would use only a part), there is still work to do, but I write all the time about the connections with geometry and what you look at does something very weird, with geometry.

Details will come. Relevant links:

  • kali24, the last version
  • kali, the initial version with 6 nodes, which almost works
  • em-convex, the dilations enhanced lambda calculus which can be also done with kali
  • and perhaps you would enjoy the pages to play and learn.

One more thing: when all fiddling will end, the next goal would be to go to the first interesting noncommutative example, the Heisenberg group. Its geometry, as a noncommutative linear space (in the sense of emergent algebras, because in the usual sense it is not a linear space), is different but worthy of investigation. The same treatment can be applied to it and it would be interesting to see what kind of lambda calculus is implied, in particular. As this approach is a machine of producing calculi, I have no preference towards the outcome, what can it be? Probably not quite a known variant of lambda, quantum or noncommutative, because the generalization does not come from a traditional treatment [update: which generalizes from a too particular example].

Divination table for anharmonic lambda

UPDATE: Second version, better: kali24.

UPDATE: first version to play here. Needs fiddling though, the termination rewrites not yet clear and it may need to pass to the full projective 24 nodes version, but I hope not. Anyway, it is surprisingly fit, seen that the background has absolutely nothing to do with lambda calculus.

The ambition is to use it for anharmonic chemlambda but IC style seems simpler.

I stare at this to generate the right choice of rewrites

zhexa

and it is much to say, but maybe you can figure it out from some links:

anharmonic group

em

shuffle trick

The life of a 10-nodes quine, short video

I’m working on an article on the 10-nodes quine (see here and here previous posts) and I have to prepare some figures, well rather js simulations of relevant phenomena.

I thought I’ll made a screencast for this work in progress and put it in the internet archive:

https://archive.org/details/the-life-of-a-10-nodes-quine

UPDATE: I found, by playing, an even more, apparently, assymetrical variant of chemlambda, but also I found a bug in the js version, which is, fortunately, not manifesting in any of the cases from the menu of this page.  For the moment is not completely clear for me if the more, apparently, assymetrical variant behaves so much better, when I reduce lambda terms, because of the bug. I think not. Will tell after I fix the thing. Is something unexpected, not in my current program, but exciting, at least because either way is beneficial: I found a bug or I found a bounty.

Cryptocurrency for life

Biological life is a billions years old experiment. The latest social experiments, capitalism and communism, are much more recent. Cryptocurrencies experiments are a really new response to the failures of those social experiments.

We don’t really understand biological life starting from it’s computational principles. As well, we don’t understand in depth decentralized computation which is at the basis of many cryptocurrencies experiments.

My point is that we try to solve the same problem, so that we shall be able to evolve socially at a human time scale. Not in hundred thousands years, in decades instead.

Therefore it would be only natural if the active people in the cryptocurrency realm would dedicate significant financial support to the problem of life.