# The EM term rewrite system repository

I just opened the GitHub repository EM, which contains work for the EM (emergent algebras) term rewrite system. It is an article (pdflatex), at this moment (22-05-2018) has about 20 pages, about 1/5 of the work done. I welcome and encourage everybody to contribute, review, etc. Maybe, I don’t know, we can produce collaboratively something better than I can do alone. All contributions will be acknowledged, consistent contributions will lead to co-authorship.

Please comment here, for more informal discussions. You can send me a direct mail, you can open issues at the repository and, the best and the most rigorous: pull requests.

There is a lot of accumulated work, there are many questions. This is part of the final goal to unite (articles, proofs, programs) EM with chemlambda.

# Groups are numbers (2). Pattern matching

As in divination, pattern matching. Continues from Groups are numbers (1).

We start from elementary variables, then we define number terms by two operations: substraction and multiplication.

• Variables are terms.
• Substraction (the first line): a is a variable and b is a term, then $a-b$ is a term.
• Multiplication (2nd line): a, b are terms, then $ab$ is a term.

By pattern matching we can prove for example this:

[update: figure replaced, the initial one was wrong by pattern matching only. The difference is that in this correct figure appears “(a-b)d” instead of the wrong “d(a-b)”]

What does it mean? These are just binary trees. Well let’s take a typing convention

where e, x, … are elements of a vector space and the variables are invertible scalars. Moreover take $e = 0$ for simplicity.

Then the previous pattern matching dream says that

$(1-(a-b))c x + (a-b)(c-d) x = (c - (a-b)d)x$

which is true, but from all the irrelevant reasons (vector space, associativity and commutativity  of addition, distributivity, etc):

$(c- ac + bc + ac -ad - bc + bd) x = (c - ad + bd) x = (c - (a-b)d)x$

With the previous typing conventions it reads:

$(c-(a-b))x = (1-b)(c-a)x + b(1- a^{-1})(c-a) x + (bc a^{-1})x$

which is true because the right hand side is:

$((1-b)(c-a) + b(1- a^{-1})(c-a) + bc a^{-1} )x =$

$= (c-a-bc+ab+bc-ab-bca^{-1} +b+bc a^{-1}) x = (c-a+b) x = (c-(a-b))x$

Which is funny because it does not make any sense.

# Groups are numbers (1), the shuffle trick and brackets

What I call the shuffle trick is this rewrite. It involves, at left, a pattern of 3 decorated nodes, with 5 ports (the root and 1, 2, 3, 4). At the right there is almost the same pattern, only that the decorations of the nodes changed and the ports 2, 3 are shuffled.

I have not specified what is the orientation of the edges, nor what the decorations (here the letters “a”, “b”) are. As previously with chemlambda or emergent algebras, these graphs are in the family of trivalent oriented ribbon graphs. You can find them everywhere, in physics, topology, knot theory or interaction graphs. Usually they are defined as a pair of two permutations, A and B, over the set of “half-edges” (which are really half edges). The permutation A has the property that AAA=id and the orbits of A are the nodes of the graph. Translated, this gives a circular order of the edges incident to a node. The permutation B is such that BB=id and the orbits are the unoriented edges. Indeed, an edge is made by to half edges. The orientation of the edges is made by picking one of the half edges which make an edge, or equivalently by replacing the set of two half edges, say half-edge and B(half-edge), by a list of the two half edges.

I prefer though another description of these graphs, by using sticks and rings, or, just the same, by using a partially defined SUCC function (which defines the sticks or rings) and a GLUE permutation with GLUE GLUE = id. That is why I use behind the description of the chemlambda strings and what you can grasp by looking at the needs repository.

With the sticks and rings notation, here is an example of the shuffle trick:

The shuffle trick is very important in chemlambda. It is this one, in a static diagram. You see that the decoration of the nodes are “FO” and “FOE” and that actually, in chemlambda, this is achieved via two rewrites.

More about the chemlambda shuffle trick in the all-in-one illustrated shuffle trick post. where is explain why the shuffle trick is so important for duplication. An animation taken from there is this one, the dynamical version of the previous static picture. [The molecule used is this, you can see it live here.]

But the shuffle trick is relevant to emergent algebras as well. This time we play with oriented binary trees, with nodes which can be white or black, decorated with “a”, “b” from a commutative group. To refresh a bit your memory, here are the rules of the game for emergent algebras, look at the first two columns and ignore the third one (because this is old notation from graphic lambda calculus). An emergent algebra over a set X is a collection of operations indexed with a parameter in a commutative group. We can represent these operations by using oriented trivalent ribbon graphs (left side) or just binary trees (right side), here with leaves at the right and the root at the left.

(image taken from this post).   (Image changed)

In this post we’ll use Reidemeister moves (they are related to the true Reidemeister moves).

(Emergent algebras have one more property, but for this we need to have an uniform structure on X, because we need to take limits wrt the parameter which are uniform wrt the leaves… not needed here for the moment.)

Further I’ll use the representation with binary trees, i.e. I’ll not draw the orientation of the edges, recall: from the leaves, at right, to the root, at left.

By using the Reidemester 2 move twice, we can make the following version of a shuffle trick (in the figure below the orientation of the edges is from right to left, or from the leaves 1, 2, 3, 4 to the root)

Encircled is a graph which quantifies the difference between the left and right sides of the original shuffle trick. So if we want to have a real shuffle trick in emergent algebras, then we would like this graph to transform to an edge, i.e. the following rewrite

If this rewrite is possible in an emergent algebra, then we’d have a shuffle trick for it. Conversely, if the shuffle trick would be valid, then the graph from the left would transform to the one from the right by that shuffle trick and two Reidemeister 2 moves.

But look closer at this graph: reading from right to left, it looks like a bracket, or commutator in a group. It has the form $b^{-1} a^{-1} b a$, or almost!

This is because we can prove that indeed it is an approximate version of the commutator and that the shuffle trick in emergent algebras is possible only in a commutative case. We shall apply this further for chemlambda, to show that it is in a sense valid in a commutative frame. Also, we can work non-commutatively as well, the first example being the Heisenberg group. Lot of fun!

# Open Access Movies

Dear Netflix, Dear Hollywood, Dear Cannes Competition, etc etc etc

Dear artists,

You face tough times.  Your audiences are bigger than you ever imagined.  Your movies, your creations are now very easy to access, by anybody, from everywhere. But you can’t monetize this as much as you want. The artists can’t be paid enough, the producers can’t profit enough. There is no respect left for your noble profession. A screaming idiot with a video camera is more popular than a well thought, well funded movie with a dream cast.

There is a solution which I humbly suggest. Take the exemple from academic scientists. They are an absolute disaster as concerns the communication talent, but, reluctantly, you may grant them some intellectual capacities, even if used in the most weird way and to their least profit.

They invented Gold Open Access and I believe that it is a great idea for your business.

You have to recognize the problem, which is that you can no longer ensure a good profit from selling your movies. The audience will follow the cheapest path and will not pay you. That’s the sad truth.

But, what about the movie makers? They have money.

People from the audience is always seeking for the best movies. Give them the best movies for free!

You are the gatekeepers. Dissemination of movies is trivial. Make the movie makers pay!

You are the ones which can select the best movies. From the thousands of movies made each year, only a hundred of them are among the best, for a global audience.

Therefore, artists, if you want to work in the best, then you have to be in the cast of the best 100 movies of the year. Then you’re good and with some chance (there are lots and lots of artists, you know) you’ll have the chance to be in the cast of next year’s best movies.

Producers, why don’t you use your connection with politicians and convince them to take money from taxes and give them to you, in a competition alike to the various research grant competions in the academic world.

Producers can always split the money with the dissemination channels. They will be both part of the juries which decide which movie takes more funding and part of the juries which decide which movie is transmitted by Netflix, which one will deserve to be called  a Hollywood production or, in the case of Europeans, in the list of movies from the next Cannes competition.

In this way the producers make profit before the movie is stolen by the content pirates.

In this way the dissemination channels (Netflix, etc) have the best movies to show, vetted by respected professionals, and already paid by the various competition budgets.

In this way politicians can always massage as they want their message to the populace. And finance future campains.

So the great idea, borrowed from the intelligent academic research community, is to make the creators compete and pay for the honor to be in the first 100 best creators, with the money from taxes, taxes taken from the audience who sees the movie for free.

# Groups are numbers (0)

I am very happy because today I arrived to finish a thread of work concerning computing and space. In future posts, with great pleasure I’ll take the time to explain that, with this post serving as an impresionistic introduction.

Eight years ago I was obsessing about approximate symmetric spaces. I had one tool, emergent algebras, but not the right computation side of it. I was making a lot of drawings, using links, claiming that there has to be a computational content which is deeply hidden not in the topology of space, but in the infinitesimal calculus. I reproduce here one of the drawings, made during a time spent at the IHES, in April 2010. I was talking with people who asked me to explain with words, not drawings, I was starting to feel that category theory does not give me the right tools, I was browsing Kauffman’s “Knots and Physics” in search for hints. (Later we collaborated about chemlambda, but knots are not quite enough, too.)

This a link which describes what I thought that is a good definition for an approximate symmetric space. It uses conventions later explained in Computing with space, but the reason I reproduce it here is that, at the moment I thought it is totally crazy. It is organic, like if it’s alive, looked like a creature to me.

There was an article about approximate symmetric spaces later, but not with such figures. Completely unexpected, these days I had to check something from my notes back then and I found the drawing. After the experience with chemlambda I totally understand the organic feeling, and also why it does resemble to the “ouroboros” molecules, which are related to Church encoding of numbers and to the predecessor.

Because, akin to the Church encoding in lambda calculus, there is an encoding in emergent algebras, which makes these indeed universal, so that a group (to simplify) encodes numbers.

And it is also related to the Gleason-Yamabe theorem discussed here previously. That’s a bonus!

# Quines in chemlambda (2)

Motivated by this comment I made on HN, reproduced further, I thought about making a  all-in-one page of links concerning various experiments with quines in chemlambda. There are too many for one post though. In the Library of chemlambda molecules about 1/5 of the molecules are, or involve quines.

[EDIT: see the first post Quines in chemlambda from 2014]

If you want to see some easy to read (I hope) explanations, go to the list of posts of the chemlambda collection and search for “quine”. Mind that there are  several other posts which do not have the word “quine” in the title, but do have quine-relevant content, like those about biological imortality, or about senescence, or about “microbes”.

There’s a book to be written about, with animated pages. Or a movie, with uniformised style simulations. Call me if you want to start a project.

Here is the comment which motivated this post.

on “autocatalitic quines”. The Introduction section explains very nice the history of uses of quines in artificial life.

There are some weird parts though in all this, namely that we may think about different life properties in terms of quines:

1) Metabolism, where you take one program, consume it and produce the same program

2) Replication, where you take one program, consume it and produce two copies.

3) Death

I thought about this a lot during my chemlambda alife project, where I have a notion of a quine which might be interesting, seen the turn of these comments.

A chemlambda molecule is a particular trivalent graph (imagine a set of real molecules, the graphs don’t have to be connected), chemical reactions are rewrites, like in reality, when if there is a certain pattern detected (by an enzyme, say) then the patern is rewritten.

There are two extremes in the class of possible algorithms. One extreme is the deterministic one, where rewrites are done whenever possible, in the order of preference from a list, so that the possible conflicting patterns are always solved in the same way. The other extreme is the purely random one, where patterns are randomly detected and then executed or not acording to a coin toss.

Now, a quine in this world is by definition a graph which has a periodic evolution under the deterministic algorithm.

The interesting thing is that a quine, under the random algorithm, has some nice properties, among them that it has a metabolism, can self-replicate and it can also die.

Here is how a quine dies. Simple situation. Take a chemlambda quine of period 1. Suppose that there are two types of rewrites, the (+) one which turns a pattern of 2 nodes into a pattern of 4 nodes, the other (-) which turns a pattern of 2 nodes into a pattern of 0 nodes (by gluing the 4 remaining dangling links in the graph).

Then each (+) rewrite gives you 4 possible new patterns (one/node) and each (-) rewrite gives you 2 possible new patterns (because you glued two links). Mind that you may get 0 new patterns after a (+) or (-) rewrite, but if you think that a node has an equal chance to be in a (+) pattern or in a (-) pattern, then there is twice as possible that a new pattern comes from a (+) rewrite than from a (-) rewrite.

Suppose that in the list of preferences you always put the (+) type in front of the (-) one. It looks that in this way graphs will tend to grow, right? No!

In a quine of period 1 the number of (+) patterns = number of (-) patterns.

Hence, if you use the random algorithm, the non execution of a (+) rewrite is twice more probable to affect future available rewrites than the non-execution of a (-) rewrite.

In experiments, I noticed lots of quines which die (there are no more rewrites available after a time), some which seem immortal, and no example of a quine which thrives.”

I’m fine. I still exist and my life is better. I write this after several years of experiments with Open Science in social media. I still keep a presence with Google because I don’t want to delete the chemlambda collection. But in no way am I satisfied with this.

UPDATE: I deleted my Medium account, it was just another Twitter sht.

UPDATE 2: The fight of legacy media against FB is so stupid. But amusing. May be useful, like an infection with a gut parasite which makes the immune system able to kill a more dangerous viral invection. When this is done, the gut parasite is easy to get rid of…

I explained what I think is wrong with corporate social media, from the point of view of a researcher who wants to share scientific content and discuss about it. For example in thie Twitter “moment” which no longer exists. (I think very few people saw it because it was hidden by Twitter 🙂 )

Dissatisfied with the careless treatment of scientific data, precious data, by corporate social media, in this “moment” I explain that I tried, probably successfully, to socially hack Google Plus. It worked, reasons here.

The other reason for which social media is not good for Open Science is that successful collaborations via said media are very rare. Most of the interactions have almost no scientific value. It is an endless stream of hot air bubbles coming from a school of bored goldfishes.

The reason is not that people [who are willing to interact via social media] are stupid. Don’t believe this shallow explanation. I think this is because of the frame of mind cultivated by social media. People there consume, they don’t build. They are encouraged to click, not to reason. They have to do everything as quick as possible. Why? they don’t know. I imagine though that [some hackers excepted] there is not much rational thought in the brains of a casino client.

There are therefore two reasons which make social media bad for use for Open Science:

• bad, disrespectful treatment of scientific data, despite low volume and high density
• bad medium for rational interaction, despite being presented as an enhanced one.

I’ll go to a liitle bit of detail concerning Facebook and Twitter, because until now I wrote mainly about my experience with Google.

Facebook. I tried several times to use Facebook for the same purpose. But I failed, because of a complete lack of a chance for visibility. Even the 10s animations from real simulations were badly presented in FB (hence tehnical reasons). Moreover the algorithms were clearly not in favor for the kind of posts I made on Google Plus. But I have to admit that there was a matter of chance that Google had this idea of collections, plus the superior technical possibilities, which made the chemlambda collection to be very visible.

Twitter. I had a presence on Twitter since, I think, 2011. I intentionally kept a low count of people I followed, varying and keeping only those who posted interesting tweets. However, it was clear for me since a long time that there is heavy censorship, or call it editing, same, on what I see and what my followers see.

From time to time I made or consumed political tweets. I am free to do this, as far as I know, and I am a grownup whose youth was spent under heavy thought police, so allow me to be furious to see the new thought police enforced exactly by those whom I admire in principle.

Going back to Google, the same thing happened btw, here is a  clear case where I was allowed a rare glimpse over the algorithmic wall, where I and my interlocutor saw each comment censored by Google in the other’ worldview:

Story here.

People are more and more furious now (i.e. 2 years after), especially about Facebook and Cambridge Analitica. But let’s ignore politics and go back to using social media for science.

Well, corporate social media does not care about this. Moreover, censorship (aka algorithmic editing) can have very bad consequences for scientific communication, like: inhibition of better scientific ideas in order to protect a worse technical solution which brings money, or straight scientific theft, when a big data company obtains for free good scientific ideas.

OK, what about the Invisible College?

I think we really are on the brink of a scientific revolution. We do have technical means to interact scientifically. Most of the scientists who ever eisted on Earth are alive. Rational, educated thought and brain power, from professionals of many fields, from inquisitive minds, from creative freaks, these are in an unprecedented quantity. Add computing power to that mix, add the holy Internet. Here we are, ready to pass to a new level.

If you look back to the last scientific revolution, then one of the places where it happened was in a precursor group of the Royal Society of London called The Invisible College.

What a great idea!

Look, these people really were like us. In a past post I shared the front page of a famous book by Newton (appeared posthumously) where you can recognize the same ideas as today.

I am sure that there are others members, most of them perhaps future ones, of the Invisible College of the 21st century, where we have to solve the problems: how to treat scientific information fairly, among us, the members, and how to interact rationally and thoughtfully. Long term.

Because social media failed us. Because who cares about politics?

Here, there are lots of good names from that period, like the related “College for the Promoting of Physico-Mathematical Experimental Learning” from 1660, but my liking goes to the Invisible college.

I end with two invitations for more private discussions

but I fully encourage to discuss here as well, if you want.

## computing with space | open notebook

MolView

computing with space | open notebook

MaidSafe

The World's First Autonomous Data Network

Voxel-Engine

An experimental 3d voxel rendering algorithm

Gödel's Lost Letter and P=NP

a personal view of the theory of computation