Tag Archives: Turing machine

The numberphile microbe and the busy beaver

This is another weirdly named, but contentful post after this one, During an attempt to launch myself into video explanations, I made a post on the numberphile microbe.

The numberphile microbe is the chemlambda version of a multiplication of two Church numbers, in this case 5X5=25. I called the creature evolving in the video a “numberphile microbe” because it really consumes copies of the number 5, metabolizes them and produces eventually 25. In a very careful way, though, which inspired me the following description (but you have to see the video from that post):

“The numberphile microbe loves Church numbers. His strategy is this: never one without the other. When he finds one Church number he looks around for the second one. Then he chains the first to the second and only after that he starts to slowly munch the head of the first. Meanwhile the second Church number watches the hapless first Church number entering, atom by atom, in the numberphile mouth.

Only the last Church number survives, in the form of the numberphile’s tail.”

The  mol file used is times_only.mol.  Yes, allright, is the mol version of the AST of a lambda term.

You can see the numberphile also in this animation, together with a busy beaver Turing machine (the chemlambda version explained here):



In the first half of the animation you see the “numberphile” at the left and the busy beaver as a reddish loop at the right.

What happens is that the lambda term like 5X5 reduces to 25 while in the same time the busy beaver machine works too. In the same time, the Church number 25 in the making already makes the small loop to replicate and to grow bigger and bigger, eventually 25 times bigger.

So that explains the title.

The mol file used is times_only_bb.mol. Open it and see how is it different than the first.

You can see a simulation (js) of Church number applied to a busy beaver here.

And the most important is: during the making of this short movie, no human director was present to stage the act.

Asynchronous and decentralized teleportation of Turing Machines

The idea is that it is possible to copy a computer which executes a program, during execution, and to produce working clones. All this without any control (hence decentralized) and any synchronization.

More than that, the multiple copies are done in the same time as the computers compute.

I think is crazy, there’s nothing like this on the offer. This is a proof of principle.  The post is a light (hopefully) introduction into the subject.

If you look for validation, then go follow the instructions from
and use the file bbdupli.mol
This animation starts with one Turing Machine and ends with three Turing Machines.
Let’s take it slower.
1. Everybody knows what is a TM. Computers are the real thing which resembles most to a TM. There is lot of stuff added, like a screen, keyboard, a designer box, antennas and wires, but essentially a computer has a memory which is like a tape full of bits (0 and 1) and there is a processor which is like a read/write head with an internal state. When the head reads a bit from the tape then the internal state changes, the head writes in the tape and then moves, according to some internal rules.
2. These rules define the TM. Any rule goes, but among them there are rules which make the TM universal. That means that there are well chosen rules such that  if you first put on the tape a string of bits, which is like the OS of the computer, and if you place the head at the beginning of this string, then the TM (which obbeys those clever rules) uploads the OS and then it becomes the TM of your choice.
3. From here it becomes clear that these rules are very important. Everything else is built on them. There are many examples of rules for universal TM, the more or less precise estimate is that for a tape written with bits (0 and 1) the known universal TM need about 20 rules.
4. Just a little bit earlier than the TM invention, lambda calculus has been invented as well, by Alonzo Church. Initially the lambda calculus was a monumental formalism, but after the TM invention there was a variant of it, called untyped lambda beta calculus, which has been proved to be able to compute the same things as a TM can compute.
The untyped lambda beta calculus is famous among the CS nerds and much less known by others (synthetic biologists, I’m looking at you) who think that TM are the natural thing to try to emulate with biology and chemistry, because it is obviously something everybody understands, not like lambda calculus which goes into higher and higher abstractions.
There are exceptions, the most famous in my opinion is the Algorithmic Chemistry (or Alchemy) of Fontana and Buss. They say that lambda calculus is chemistry and that one operation (called application) of LC is like a chemical reaction and the other operation (called abstraction) is like a reactive site. (Then they change their mind, trying to fit types into the story, speaking about chemicals as functions, then they use pi calculus, all very interesting but outside of the local goal of this post. Will come back later to that.)
Such exceptions aside, the general idea is: TM easy, LC hard.That is false and I shall prove it. The side bonus is that I can teleport Turing machines.
5. If we want to compare TM with LC then we have to put them on the same footing, right? This same footing is to take the rules of TM and the reductions of LC as rewrites.
But, from the posts about chemlambda, rewrites are chemical reactions!
So let’s put all in the chemlambda frame.


  • LC is actually much simpler than TM, because it uses only one rewrite which is specific to it (the BETA rewrite) instead of about 20 min for the TM
  • LC and TM are both compatible with the chemical approach a la chemlambda, in the sense that chemlambda can be enhanced by the addition of “bits” (red and green 2 valent nodes), head move (Arrow element) and TM internal states (other 2-valent nodes) and by some “propagation” rewrites, such that chemlambda can now do both TM and LC in the same time!

In the animation you see, at the beginning, something like
a tree made of green fanout (FO) nodes (and yellow FRIN and magenta FROUT leaves) and
– a  small ring of green (2-valent, bit 0) and pale green (a state of a TM). That small ring is a TM tape which is “abstracted”, i.e. connected to a lambda abstraction node, which itself is “applied” (by an application A node) to the fanout tree.

What happens? Eventually there are produced 3 TM (you see 3 tapes) which function independently.

They are actually in different states, because the algorithm which does all this is random (it does a rewrite if a coin has the fancy to drop in the right state).

The algorithm is random (simulation of asynchronous behaviour) and all rewrites are local (simulation of decentralized).

Only a simulation which shows it is perfectly possible. The real thing would be to turn this into a protocol.


Nothing vague in the “no semantics” point of view

I’m a supporter of “no semantics” and I’ll try to convince you that it is nothing vague in it.

Take any formalism. To any term built from this formalism there is an associated syntactic tree. Now, look at the syntactic tree and forget about the formalism. Because it is a tree, it means that no matter how you choose to decorate its leaves, you can progress from the leaves to the root by decorating each edge. At each node of the tree you follow a decoration rule which says: take the decorations of the input edges and use them to decorate the output edge. If you suppose that the formalism is one which uses operations of bounded arity then you can say the following thing: strictly by following rules of decoration which are local (you need to know only at most N edge decorations in order to decorate another edge) you can arrive to decorate all the tree. Al the graph! And the meaning of the graph has something to do with this decoration. Actually the formalism turns out to be not about graphs (trees), but about static decorations which appear at the root of the syntactic tree.
But, you see, these static decorations are global effects of local rules of decoration. Here enters the semantic police. Thou shall accept only trees whose roots accept decorations from a given language. Hard problems ensue, which are heavily loaded with semantics.
Now, let’s pass from trees to other graphs.
The same phenomenon (there is a static global decoration emerged from local rules of decoration) for any DAG (directed acyclic graph). It is telling that people LOVE DAGs, so much so they go to the extreme of excluding from their thinking other graphs. These are the ones who put everything in a functional frame.
Nothing wrong with this!
Decorated graphs have a long tradition in mathematics, think for example at knot theory.
In knot theory the knot diagram is a graph (with 4-valent nodes) which surely is not acyclic! However, one of the fundamental objects associated to a knot is the algebraic object called “quandle”, which is generated from the edges of the graph, with certain relations coming from the edges. It is of course a very hard, fully loaded semantically problem to try to identify the knot from the associated quandle.
The difference from the syntactic trees is that the graph does not admit a static global decoration, generically. That is why the associated algebraic object, the quandle, is generated by (and not equal to) the set of edges.

There are beautiful problems related to the global objects generated by local rules. They are also difficult, because of the global aspect. It is perhaps as difficult to find an algorithm which builds an isomorphism between  two graphs which have the same associated family of decorations, as it is to  find a decentralized algorithm for graph reduction of a distributed syntactic tree.

But these kind of problems do not cover all the interesting problems.

What if this global semantic point of view makes things harder than they really are?

Just suppose you are a genius who found such an algorithm, by amazing, mind bending mathematical insights.

Your brilliant algorithm, because it is an algorithm, can be executed by a Turing Machine.

Or Turing machines are purely local. The head of the machine has only local access to the tape, at any given moment (Forget about indirection, I’ll come back to this in a moment.). The number of states of the machines is finite and the number of rules is finite.

This means that the brilliant work served to edit out the global from the problem!

If you are not content with TM, because of indirection, then look no further than to chemlambda (if you wish combined with TM, like in
http://chorasimilarity.github.io/chemlambda-gui/dynamic/turingchem.html , if you love TM ) which is definitely local and Turing universal. It works by the brilliant algorithm: do all the rewrites which you can do, nevermind the global meaning of those.

Oh, wait, what about a living cell, does it have a way to manage the semantics of the correct global chemical reactions networks which ARE the cell?

What about a brain, made of many neural cells, glia cells and whatnot? By the homunculus fallacy, it can’t have static, external, globally selected functions and terms (aka semantic).

On the other side, of course that the researcher who studies the cell, or the brain, or the mathematician who finds the brilliant algorithm, they are all using heavy semantic machinery.


Not that the cell or the brain need the story in order for them to live.

In the animated gif there is a chemlambda molecule called the 28 quine, which satisfies the definition of life in the sense that it randomly replenish its atoms, by approximately keeping its global shape (thus it has a metabolism). It does this under the algorithm: do all rewrites you can do, but you can do a rewrite only if a random coin flip accepts it.

Most of the atoms of the molecule are related to operations (application and abstraction) from lambda calculus.

I modified a bit a script (sorry, not in the repo this one) so that whenever possible the edges of this graph which MAY be part of a syntactic tree of a lambda term turn to GOLD while the others are dark grey.

They mean nothing, there’s no semantics, because for once the golden graphs are not DAGs, and because the computation consists into rewrites of graphs which don’t preserve well the “correct” decorations before the rewrite.

There’s no semantics, but there are still some interesting questions to explore, the main being: how life works?



Louis Kauffman reply to this:

Dear Marius,
There is no such thing as no-semantics. Every system that YOU deal with is described by you and observed by you with some language that you use. At the very least the system is interpreted in terms of its own actions and this is semantics. But your point is well-taken about not using more semantic overlay than is needed for any given situation. And certainly there are systems like our biology that do not use the higher level descriptions that we have managed to observe. In doing mathematics it is often the case that one must find the least semantics and just the right syntax to explore a given problem. Then work freely and see what comes.
Then describe what happened and as a result see more. The description reenters the syntactic space and becomes ‘uninterpreted’ by which I mean  open to other interactions and interpretations. It is very important! One cannot work at just one level. You will notice that I am arguing both for and against your position!
Lou Kauffman
My reply:
Dear Louis,
Thanks! Looks that we agree in some respects: “And certainly there are systems like our biology that do not use the higher level descriptions that we have managed to observe.” Not in others; this is the base of any interesting dialogue.
Then I made another post
Related to the “no semantics” earlier g+ post [*], here is a passage from Rodney Brooks “Intelligence without representation”

“It is only the observer of the Creature who imputes a central representation or central control. The Creature itself has none; it is a collection of competing behaviors.  Out of the local chaos of their interactions there emerges, in the eye of an observer, a coherent pattern of behavior. There is no central purposeful locus of control. Minsky [10] gives a similar account of how human behavior is generated.  […]
… we are not claiming that chaos is a necessary ingredient of intelligent behavior.  Indeed, we advocate careful engineering of all the interactions within the system.  […]
We do claim however, that there need be no  explicit representation of either the world or the intentions of the system to generate intelligent behaviors for a Creature. Without such explicit representations, and when viewed locally, the interactions may indeed seem chaotic and without purpose.
I claim there is more than this, however. Even at a local  level we do not have traditional AI representations. We never use tokens which have any semantics that can be attached to them. The best that can be said in our implementation is that one number is passed from a process to another. But it is only by looking at the state of both the first and second processes that that number can be given any interpretation at all. An extremist might say that we really do have representations, but that they are just implicit. With an appropriate mapping of the complete system and its state to another domain, we could define a representation that these numbers and topological  connections between processes somehow encode.
However we are not happy with calling such things a representation. They differ from standard  representations in too many ways.  There are no variables (e.g. see [1] for a more  thorough treatment of this) that need instantiation in reasoning processes. There are no rules which need to be selected through pattern matching. There are no choices to be made. To a large extent the state of the world determines the action of the Creature. Simon  [14] noted that the complexity of behavior of a  system was not necessarily inherent in the complexity of the creature, but Perhaps in the complexity of the environment. He made this  analysis in his description of an Ant wandering the beach, but ignored its implications in the next paragraph when he talked about humans. We hypothesize (following Agre and Chapman) that much of even human level activity is similarly a reflection of the world through very simple mechanisms without detailed representations.”

This brings to mind also this quote from the end of Vehicle 3 section from V. Braintenberg book Vehicles: Experiments in Synthetic Psychology:

“But, you will say, this is ridiculous: knowledge implies a flow of information from the environment into a living being ar at least into something like a living being. There was no such transmission of information here. We were just playing with sensors, motors and connections: the properties that happened to emerge may look like knowledge but really are not. We should be careful with such words.”

Louis Kauffman reply to this post:
Dear Marius,
It is interesting that some people (yourself it would seem) get comfort from the thought that there is no central pattern.
I think that we might ask Cookie and Parabel about this.
Cookie and Parabel and sentient text strings, always coming in and out of nothing at all.
Well guys what do you think about the statement of MInsky?

Cookie. Well this is an interesting text string. It asserts that there is no central locus of control. I can assert the same thing! In fact I have just done so in these strings of mine.
the strings themselves are just adjacencies of little possible distinctions, and only “add up” under the work of an observer.
Parabel. But Cookie, who or what is this observer?
Cookie. Oh you taught me all about that Parabel. The observer is imaginary, just a reference for our text strings so that things work out grammatically. The observer is a fill-in.
We make all these otherwise empty references.
Parabel. I am not satisfied with that. Are you saying that all this texture of strings of text is occurring without any observation? No interpreter, no observer?
Cookie. Just us Parabel and we are not observers, we are text strings. We are just concatenations of little distinctions falling into possible patterns that could be interpreted by an observer if there were such an entity as an observer?
Parabel. Are you saying that we observe ourselves without there being an observer? Are you saying that there is observation without observation?
Cookie. Sure. We are just these strings. Any notion that we can actually read or observe is just a literary fantasy.
Parabel. You mean that while there may be an illusion of a ‘reader of this page’ it can be seen that the ‘reader’ is just more text string, more construction from nothing?
Cookie. Exactly. The reader is an illusion and we are illusory as well.
Parabel. I am not!
Cookie. Precisely, you are not!
Parabel. This goes too far. I think that Minsky is saying that observers can observe, yes. But they do not have control.
Cookie. Observers seem to have a little control. They can look here or here or here …
Parabel. Yes, but no ultimate control. An observer is just a kind of reference that points to its own processes. This sentence observes itself.
Cookie. So you say that observation is just self-reference occurring in the text strings?
Parabel. That is all it amounts to. Of course the illusion is generated by a peculiar distinction that occurs where part of the text string is divided away and named the “observer” and “it” seems to be ‘reading’ the other part of the text. The part that reads often has a complex description that makes it ‘look’ like it is not just another text string.
Cookie. Even text strings is just a way of putting it. We are expressions in imaginary distinctions emanated from nothing at all and returning to nothing at all. We are what distinctions would be if there could be distinctions.
Parabel. Well that says very little.
Cookie. Actually there is very little to say.
Parabel. I don’t get this ‘local chaos’ stuff. Minsky is just talking about the inchoate realm before distinctions are drawn.
Cookie. lakfdjl
Parabel. Are you becoming inchoate?
Cookie. &Y*
Parabel. Y


My reply:
Dear Louis, I see that the Minsky reference in the beginning of the quote triggered a reaction. But recall that Minsky appears in a quote by Brooks, which itself appears in a post by Marius, which is a follow up of an older post. That’s where my interest is. This post only gathers evidence that what I call “no semantics” is an idea which is not new, essentially.
So let me go back to the main idea, which is that there are positive advances which can be made under the constraint to never use global notions, semantics being one of them.
As for the story about Cookie and Parabel, why is it framed into text strings universe and discusses about  a “central locus of control”? I can easily imagine Cookie and Parabel having a discussion before writing was invented, say for example in a cave which much later will be discovered by modern humans in Lascaux.
I don’t believe that there is a central locus of control. I do believe that semantics is a mean to tell the story, any story, as if there is a central locus of control. There is no “central” and there is very little “control”.
This is not a negative stance, it is a call for understanding life phenomena from points of view which are not ideologically loaded by “control” and “central”. I am amazed by the life variety, beauty and vastness, and I feel limited by the semantics point of view. I see in a string of text thousands of years of cultural conventions taken for granted, I can’t forget that a string of text becomes so to me only after a massive processing which “semantics” people take as granted as well, that during this discussion most of me is doing far less trivial stuff, like collaborating and fighting with billions of other beings in my gut, breathing, seeing, hearing, moving my fingers. I don’t forget that the string of text is recreated by my brain 5 times per second.
And what is an “illusion”?
A third post
In the last post https://plus.google.com/+MariusBuliga/posts/K28auYf69iy I gave two quotes, one from Brooks “Intelligence without representation” (where he quotes Minsky en passage, but contains much more than this brief Minsky quote) and the other from Braitenberg “Vehicles: Experiments in Synthetic Psychology”.
Here is another quote, from a reputed cognitive science specialist, who convinced me about the need for a no semantics point of view with his article “Brain a geometry engine”.
The following quote is by Jan Koenderink “Visual awareness”

“What does it mean to be “visually aware”? One thing, due to Franz Brentano (1838-1917), is that all awareness is awareness of something. […]
The mainstream account of what happens in such a generic case is this: the scene in front of you really exists (as a physical object) even in the absence of awareness. Moreover, it causes your awareness. In this (currently dominant) view the awareness is a visual representation of the scene in front of you. To the degree that this representation happens to be isomorphic with the scene in front of you the awareness is veridical. The goal of visual awareness is to present you with veridical representations. Biological evolution optimizes veridicality, because veridicality implies fitness.  Human visual awareness is generally close to veridical. Animals (perhaps with exception of the higher primates) do not approach this level, as shown by ethological studies.
JUST FOR THE RECORD these silly and incoherent notions are not something I ascribe to!
But it neatly sums up the mainstream view of the matter as I read it.
The mainstream account is incoherent, and may actually be regarded as unscientific. Notice that it implies an externalist and objectivist God’s Eye view (the scene really exists and physics tells how), that it evidently misinterprets evolution (for fitness does not imply veridicality at all), and that it is embarrassing in its anthropocentricity. All this should appear to you as in the worst of taste if you call yourself a scientist.”  [p. 2-3]

[Remark: all these quotes appear in previous posts at chorasimilarity]


A comparison of two models of computation: chemlambda and Turing machines

The purpose is to understand clearly what is this story about. The most simple stuff, OK? in order to feel it in familiar situations.

Chemlambda is a collection of rules about rewritings done on pieces of files in a certain format. Without an algorithm which tells which rewrite to use, where and when,  chemlambda does nothing.

In the sophisticated version of the Distributed GLC proposal, this algorithmic part uses the Actor Model idea. Too complicated!, Let’s go simpler!

The simplest algorithm for using the collection of rewrites from chemlambda is the following:
  1. take a file (in the format called “mol”, see later)
  2. look for all patterns in the file which can be used for rewrites
  3. if there are different patterns which overlap, then pick a side (by using an ordering or graph rewrites, like the precedence rules in arithmetic)
  4. apply all the rewrites at once
  5. repeat (either until there is no rewrite possible, or a given number of times, or forever)
 To spice things just a bit, consider the next simple algorithm, which is like the one described, only that we add at step 2:
  •  for every identified pattern flip a coin to decide to keep it or ignore it further in the algorithm
The reason  is that  randomness is the simplest way to say: who knows if I can do this rewrite when I want, or maybe I have in my computer only a part of the file, or maybe I have to know that a friend has a half of the pattern and I have the other, so I have to talk with him first, then agree to make together the rewrite. Who knows? Flip a coin then.

Now, proven facts.

Chemlambda with the stupid deterministic algorithm is Turing universal. Which means that implicitly this is a model of computation. Everything is prescribed from the top to the bottom. Is on the par with a Turing machine, or with a RAND model.

Chemlambda with the random stupid model seems to be also Turing universal, but I don’t have yet a proof for this. There is a reason for the fact that it is as powerful as the stupid deterministic model, but I won’t go there.

So the right image to have is that chemlambda with the  described algorithm can do anything any computer can.

The first question is, how? For example how compares chemlambda with a Turing machine? If it is at this basic level then it means it is incomprehensible, because we humans can’t make sense of a scroll of bytecode, unless we are highly trained in this very specialised task.

All computers do the same thing: they crunch machine code. No matter which high language you use to write a program, it is then compiled and eventually there is a machine code which is executed, and that is the level we speak.

It does not matter which language you use, eventually all is machine code. There is a huge architectural tower and we are on the top of it, but in the basement all looks the same. The tower is here for us to be easy to use the superb machine. But it is not needed otherwise, it is only for our comfort.

This is very puzzling when we look at chemlambda because it is claimed that chemlambda has something to do with lambda calculus, or lambda calculus is the prototype of a functional programming language. So it appears that chemlamdba should be associated with higher meaning and clever thinking, and abstraction of the abstraction of the abstraction.

No, from the point of view of the programmer.

Yes, from the point of view of the machine.

In order to compare chemlambda with a TM we have to put it in the same terms. So you can easily put a TM in terms of a rewrite system, such that it works with the same stupid deterministic algorithm. http://chorasimilarity.github.io/chemlambda-gui/dynamic/turingchem.html

It is not yet put there, but the conclusion is obvious: chemlambda can do lambda calculus with one rewrite, while an Universal Turing Machine needs about 20 rewrites to do what TM do.

Wait, what about distributivity, propagation, the fanin, all the other rewrites?
They are common, they just form a mechanism for signal transduction and duplication!
Chemlambda is much simpler than TM.

So you can use directly chemlambda, at this metal level, to perform lambda calculus. Is explained here

And I highly recommend  to try to play with it by following the instructions.

You need a linux system, or any system where you have sh and awk.


2. unzip it and go to the directory “dynamic”
3. open a shell and write:  bash moving_random_metabo.sh
4. you will get a prompt and a list of files with the extension .mol , write the name of one of them, in the form file.mol
5. you get file.html. Open it with a browser with js enabled. For reasons I don’t understand, it works much better in safari, chromium, chrome than in firefox.

When you look at the result of the computation you see an animation, which is the equivalent of seeing a TM head running here and there on a tape. It does not make much sense at first, but you can convince that it works and get a feeling about how it does it.

Once you get this feeling I will be very glad to discuss more!

Recall that all this is related  to the most stupid algorithm. But I believe it helps a lot to understand how to build on it.

Busy beaver’s random church

The demo linked here would surely look impossible.

One computer, WHILE IT WORKS, is multiplied into 3 computers which  continue to work, each of them. This feat is done without any higher control and there are never conflicts which appear. All computers work asynchronously (mimicked here by randomness). Moreover, eventually they arrive to read and write on the same tape.

There are no calls, nothing you have seen before.Everything is local, no matter how you slice it into separated parts.


Turing Machines, chemlambda style (I)

UPDATE: First animation and a more detailed version here. There will be many additions, as well as programs available from the gh-pages of the repo.

Once again: why do chemists try to reproduce silicon computers? Because that’s the movie.

    At first sight they look very different. Therefore, if we want to compare them, we have to reformulate them in ways which are similar. Rewrite systems are appropriate here.
    The Turing Machine (TM) is a model of computation which is well-known as being a formalisation of what a computer is. It is a machine which has some internal states (from a set S), has a head which read/writes symbols (from a set A) on a tape. The tape is seen as an infinite word made of letters from A. The set A has a special letter (call it “b” from blank) and the infinite words which describe tapes have to be such that all but a finite number of letters of that word are different from “b”. Imagine an infinite, in both directions, tape which has written symbols on it, such that “b” represents an empty space. The tape has only a finite part of it filled with letters from A, others than the blank letter.
    The action of the machine depends on the internal state and on the symbol read by the head. It is therefore a function of the internal state of the machine (element of S), the letter from the tape which is read (element of A), and outputs a letter from the alphabet A (which is written in the case where previously was the letter which has been read, changes its internal state, and the head moves one step along the tape, to the left (L) or right (R), or does not move at all (N).
    The TM can be seen as a rewrite system.
    For example, one could see a TM as follows. (Pedantically this is seen as a multi-headed TM without internal states; the only interest in this distinction is that it raises the question if there is really any meaning into discerning internal states from the tape symbols.) We start from a set (or type) of internal states S. Such states are denoted by A, B, C (thus exhibiting their type by the type of the font used). There are 3 special symbols: < is the symbol of the beginning of a list (i.e. word), > is the symbol of the end of a list (word) and M is the special symbol for the head move (or of the type associated to head moves). There is an alphabet A of external states (i.e. tape symbols), with b (the blank) being in A.
    A tape is then a finite word (list) of one of the forms < w A w’ > , < w M A w’ > , < w A M w’ >, where A is an internal state and w and w’ are finite words written with the alphabet A, which can be empty words as well.
    A rewrite replaces a left pattern (LT) by a right pattern (RT), and there are denoted as LT – – > RT . Here LT and RT are sub-words of the tape word. It supposed that all rewrites are context independent, i.e. LT is replaced by RT regardless of the place where LT appears in the tape word. The rewrite is called “local” if the lengths (i.e. number of letters) of LT and RT are bounded a priori.
    A TM is given as a list of Turing instructions, which have the form (current internal state, tape letter read, new internal state, tape letter write, move of the tape). In terms as explained here, all this can be expressed via local rewrites.

  • Rewrites which introduce blanks at the extremities of the written tape:
    • < A   – – >   < b A
    • A >   – – >   A b >
  • Rewrites which describe how the head moves:
    • A M a   – – >   a A
    • a M A   – – >   A a
  • Turing instructions rewrites:
    • a A c   – – >   d B M c   , for the Turing instruction (A, a, B, d, R)
    • a A c   – – >   d M B c   , for the Turing instruction (A, a, B, d, L)
    • a A c   – – >   d B c   , for the Turing instruction (A, a, B, d, N)
    Together with the algorithm “at each step apply all the rewrites which are possible, else stop” we obtain the deterministic TM model of computation. For any initial tape word, the algorithm explains what the TM does to that tape. < don’t forget to link that to a part of the Cartesian method “to be sure that I made an exhaustive enumeration” which is clearly going down today > Other algorithms are of course possible. Before mentioning some very simple variants of the basic algorithm, let’s see when it works.
    If we start from a tape word as defined here, there is never a conflict of rewrites. This means that there is never the case that two LT from two different rewrites overlap. It might be the case though, if we formulate some rewrites a bit differently. For example, suppose that the Turing rewrites are modified to:
  • a A   – – >   d B M   , for the Turing instruction (A, a, B, d, R)
  • a A   – – >   d M B   , for the Turing instruction (A, a, B, d, L)
    Therefore, the LT of the Turing rewrites is no longer of the form “a A c”, but of the form “a A”. Then it may enter in conflict with the other rewrites, like in the cases:

  • a A M c where two overlapping rewrites are possible
    • Turing rewrite: a A M c   – – >   d M B M c &nbsp which will later produce two possibilities for the head moves rewrites, due to the string M B M
    • head moves rewrite: a A M c   – – >   a c A &nbsp which then produces a LT for a Turing rewrite for c A, instead of the previous Turing rewrite for a A
  • a A > where one may apply a Turing rewrite on a A, or a blank rewrite on A >
    The list is non exhaustive. Let’s turn back to the initial formulation to the Turing rewrites and instead let’s change the definition of a tape word. For example, suppose we allow multiple TM heads on the same tape, more precisely suppose that we accept initial tape words of the form < w1 A w2 B w3 C … wN >. Then we shall surely encounter conflicts between head moves rewrites for patterns as a A M B c.
    The most simple solution for solving these conflicts is to introduce a priority of rewrites. For example we may impose that blank rewrites take precedence over head moves rewrites, which take precedence over Turing rewrites. More such structure can be imposed (like some head moves rewrites have precedence over others). Even new rewrites may be introduced, for example rewrites which allow multiple TMs on the same tape to switch place.
    Let’s see an example: the 2-symbols, 3-states

busy beaver machine

    . Following the conventions from this work, the tape letters (i.e. the alphabet A) are “b” and “1”, the internal states are A, B, C, HALT. (The state HALT may get special treatment, but this is not mandatory). The rewrites are:

  • Rewrites which introduce blanks at the extremities of the written tape:
    • < X   – – >   < b X   for every internal state X
    • A >   – – >   A b >   for every internal state X
  • Rewrites which describe how the head moves:
    • X M a   – – >   a X   , for every internal state X and every tape letter a
    • a M X   – – >   X a   , for every internal state X and every tape letter a
  • Turing instructions rewrites:
    • b A c   – – >   1 B M c   , for every tape letter c
    • b B c   – – >   b C M c   , for every tape letter c
    • b C c   – – >   1 M C c   , for every tape letter c
    • 1 A c   – – >   1 HALT M c   , for every tape letter c
    • 1 B c   – – >   1 B M c   , for every tape letter c
    • 1 C c   – – >   1 M A c   , for every tape letter c
    We can enhance this by adding the priority of rewrites, for example in the previous list, any rewrite has priority over the rewrites written below it. In this way we may relax the definition of the initial tape word and allow for multiple heads on the same tape. Or for multiple tapes.
    Suppose we put the machine to work with an infinite tape with all symbols being blanks. This corresponds to the tape word < A >. Further are the steps of the computation:
  • < A >   – – >   < b A >
  • <b A >   – – >   < b A b >
  • < b A b >   – – >   < 1 B M b >
  • < 1 B M b >   – – >   < 1 b B >
  • < 1 b B >   – – >   < 1 b B b >
  • < 1 b B b >   – – >   < 1 b C M b >
  • < 1 b C M b >   – – >   < 1 b b C >
  • < 1 b b C >   – – >   < 1 b b C b >
  • < 1 b b C b >   – – >   < 1 b 1 M C b >
  • < 1 b 1 M C b >   – – >   < 1 b C 1 b >
  • < 1 b C 1 b >   – – >   < 1 1 M C 1 b >
  • < 1 1 M C 1 b >   – – >   < 1 C 1 1 b >
  • < 1 C 1 1 b >   – – >   < 1 M A 1 1 b >
  • < 1 M A 1 1 b >   – – >   < A 1 1 1 b >
  • < A 1 1 1 b >   – – >   < b A 1 1 1 b >
  • < b A 1 1 1 b >   – – >   < 1 B M 1 1 1 b >
  • <1 B M 1 1 1 b >   – – >   < 1 1 B 1 1 b >
  • < 1 1 B 1 1 b >   – – >   < 1 1 B M 1 1 b >
  • < 1 1 B M 1 1 b >   – – >   < 1 1 1 B 1 b >
  • < 1 1 1 B 1 b >   – – >   < 1 1 1 B M 1 b >
  • < 1 1 1 B M 1 b >   – – >   < 1 1 1 1 B b >
  • < 1 1 1 1 B b >   – – >   < 1 1 1 1 B M b >
  • < 1 1 1 1 B M b >   – – >   < 1 1 1 1 b B >
  • < 1 1 1 1 b B >   – – >   < 1 1 1 1 b B b >
  • < 1 1 1 1 b B b >   – – >   < 1 1 1 1 b C M b >
  • < 1 1 1 1 b C M b >   – – >   < 1 1 1 1 b b C >
  • < 1 1 1 1 b b C >   – – >   < 1 1 1 1 b b C b >
  • < 1 1 1 1 b b C b >   – – >   < 1 1 1 1 b 1 M C b >
  • < 1 1 1 1 b 1 M C b >   – – >   < 1 1 1 1 b C 1 b >
  • < 1 1 1 1 b C 1 b >   – – >   < 1 1 1 1 1 M C 1 b >
  • < 1 1 1 1 1 M C 1 b >   – – >   < 1 1 1 1 C 1 1 b >
  • < 1 1 1 1 C 1 1 b >   – – >   < 1 1 1 1 M A 1 1 b >
  • < 1 1 1 1 M A 1 1 b >   – – >   < 1 1 1 A 1 1 1 b >
  • < 1 1 1 A 1 1 1 b >   – – >   < 1 1 1 HALT M 1 1 1 b >
  • < 1 1 1 HALT M 1 1 1 b >   – – >   < 1 1 1 1 HALT 1 1 b >
    At this stage there are no possible rewrites. Otherwise said, the computation stops. Remark that the priority of rewrites imposed a path of the rewrites applications. Also, at each step there was only one rewrite possible, even if the algorithm does not ask for this.
    More possibilities appear if we see the tape words as graphs. In this case we pass from rewrites to graph rewrites. Here is a proposal for this.
    I shall use the same kind of notation as in

chemlambda: the mol format

    . It goes like this, explained for the busy beaver TM example. We have 9 symbols, which can be seen as nodes in a graph:

  • < which is a node with one “out” port. Use the notation FRIN out
  • > which is a node with one “in” port. Use the notation FROUT in
  • b, 1, A, B, C, HALT, M which are nodes with one “in” and one”out” port. Use a notation Name of node in out
    The rule is to connect “in” ports with “out” ports, in order to obtain a tape word. Or a tape graph, with many busy beavers on it. (TO BE CONTINUED…)

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


Chemical concrete machine not algorithmic self-assembly of DNA, nor Turing machine

This post is partially a request for references, partially a place for possible discussions, in the comments, and partially a place for clarifications of the previous post Why build a chemical concrete machine, and how? .

I started to read Erik Winfree’s thesis Algorithmic self-assembly of DNA and, to my joy, I see that at least at the knowledge level of 1998, what I propose is different. Here is a short brief of what I got from Winfree’s thesis  (along with my excuses for not representing things correctly and for misattributions) :

  • Adleman, Lipton, propose a model of DNA computing which uses exponential space, i.e. all the candidates for a solution of a combinatorial problem, each one represented by a strand of DNA, which are then filtered by a sequence of physical, or chemical manipulations of test tubes, of one of the types: separate (a tube into two others, according to the value of the variable at “i” position), merge (two tubes into one), detect. Variants (not due to Adleman, Lipton, Karp) are to add an amplify operation (like a FAN-OUT with variables) which transform a tube into two copies of it. Or (Boneh), instead of amplify, an append operation which adds a new variable with a give value.  All these models have variables and are based on the mechanism of selection of the solution from an exponential sea of candidates.
  • Hagiya, single-strand DNA computation, using a mechanism called “whiplash PCR”, which I don’t understand yet, but which has the computational power of a GOTO program. Has variables.
  • Winfree, single-strand DNA computation, but in 2D, where he proposes a “materialization” of a block cellular automaton (BCA) which has Turing universality. Has variables, tries to make a Turing machine.


In the post   Why build a chemical concrete machine, and how?   I mentioned Turing machines, but this is obviously wrong, as can be seen by looking at the previous post A chemical concrete machine for lambda calculus. I don’t want to have a ” syringe with 10^9 nano geometrical turing machines”, no, that’s misleading, what I call a chemical concrete machine works with lambda calculus terms (among other graphs, more geometrical, from graphic lambda calculus), which are reduced by chemical reactions (using for example the graphic beta move enzyme). That’s different.


At page 29 of Winfree’s thesis, there’s a picture illustrating various reactions and results of reactions between DNA strands.  I find interesting the Holliday junction, (image taken from the wiki page)

472px-Holliday_Junctionbecause it’s relation to crossings in knot diagrams. Recall that in the \lambda-TANGLE sector of the graphic lambda calculus, the graphic beta move appears as a SPLICE move.

Compare with these images from 3D crossings in graphic lambda calculus:





As that’s an exploratory post, kind of note to self, but open to anybody, take a look at this short course

[Updates will follow here]

Local FAN-IN eliminates global FAN-OUT (I)

For being able to build  a chemical concrete machine (see the posts  A chemical concrete machine for lambda calculus  and  Why build a chemical concrete machine, and how?) we have to prove that  universal computation can be attained with only local moves in graphic lambda calculus. Or, the lambda calculus sector of the graphic lambda calculus, which gives universality to graphic lambda calculus, uses the global FAN-OUT move (see theorem 3.1 (d)  arXiv:1305.5786 [cs.LO]. Similarly, we see in proposition 3.2 (d), which describes the way combinatory logic appears in graphic lambda calculus, that again global FAN-OUT is used.

I want to describe a way to eliminate the global FAN-OUT move from combinatory logic (as appears in graphic lambda calculus via the algorithm described here ).


There are reasons to dislike global moves in relation to B-type neural networks (see the last post    Pair of synapses, one controlling the other (B-type NN part III) ). Similar concerns can be found in the series of posts which has as the most recent one Dictionary from emergent algebra to graphic lambda calculus (III) .

In this first post I shall introduce a local FAN-IN move and two distributivity moves and I shall prove that they eliminate the need for using global FAN-OUT in combinatory logic. In the next post I shall prove that we can eliminate two other moves (so that the total number of moves of graphic lambda calculus stays the same as before) and moreover we can recover from distributivity and local FAN-OUT moves the missing oriented Reidemeister moves from the \lambda-TANGLE sector.


Definition. The local FAN-IN move is described in the next figure and it can be applied for any \varepsilon \not = 1.



  • as you see, in the move appears a dilation gate, what can this has to do with combinatory logic? As I explained previously, the properties of the gates are coming through the moves they are involved in, and not from their name. I could have introduced a new gate, with two inputs and one output, call this new gate “fan-in gate” and use it in the FAN-IN move. However, wait until the next post to see that there are other advantages, besides the economy of gates available, in using a dilation gate as a fan-in.
  • the FAN-IN move resembles to the packing arrows trick which is used extensively in the neural networks posts.  This suggests to use as a  fan-in gate


the green triangle gate and as fan-out gate the red triangle gate. This would eliminate the \Upsilon gate from the formalism, but is not clear to me how this replacement would interfere with the rest of the moves.

  • the FAN-IN move resembles with the dual of the graphic beta move, but is not the same (recall that until now I have not accepted the dual of the graphic beta move in the list of the moves of graphic lambda calculus, although there are strong reasons to do so):



which is needed in the emergent algebra sector in order to make the dictionary to work (and related as well to the goal of non using global FAN-OUT in that sector).  This latter move is in fact a distributivity move (see further), but we are free to choose different moves in different sectors of the graphic lambda calculus,

  • I know it is surprising that until now there was nothing about evaluation strategies in graphic lambda calculus, the reason being that because there are no variables then there is noting to evaluate. However, the situation is not so simple, at some point, for example in the chemical concrete machine or for neural networks, some criterion for choosing the order of moves will be needed. But it is an important point to notice that replacing global FAN-OUT (which could be seen as a remnant of having variables and evaluating them) by local FAN-IN has nothing to to with evaluation strategies.


Definition: The distributivity moves (related to the application and lambda abstraction gates) are the following:




  • the first distributivity move is straighforward, an application gate is just doubled and two fan-out moves establish the right connections. We see here why the “mystery move” can be seen as a kind of distributivity move,
  • the second distributivity move is where we need a fan-in gate (and where we use a dilation gate instead): because of th orientation of the arrows, after we double the lambda abstraction gates, we need to collect two arrows into one!


Combinatory logic terms appear in graphic lambda calculus as  trees made by application gates, with leaves one of the combinators S, K, I (seen as graphs in GRAPH.  I want to show the following. [UPDATE: made some corrections.]

Theorem.   We can replace the global FAN-OUT move with a sequence of local FAN-IN ,  DIST, CO-COMM and local pruning moves, every time the global FAN-OUT move is applied to a term made by SKI combinators.

Proof.  First, remark that a sequence of  DIST moves for the application gate allows to reduce the problem of replacing global FAN-OUT moves for any combinator to the problem of replacing it for S, K, and I. This is because the DIST move for the application gate allows to do the FAN-OUT of trees of application gates:


Now we have to prove that we can perform global FAN-OUT for I , K, S combinators.  For the combinator I the proof is the following:


For the combinator K we shall also use a local pruning move:


Finally, the proof for the combinator S is the following:


Now we are going to use 3 DIST moves, followed by the switch of arrows explained in   Local FAN-IN eliminates GLOBAL FAN-OUT (II) , which is applied in the dashed green ellipse from the next figure:


And we are done.

UPDATE: At close inspection, it turns out that we don’t need to do switch (macro) moves. Instead, if we go back at the point we were before the last figure,  we may use  first CO-ASSOC and then perform the three FAN-IN moves .

Can you turn Nalebinding into a Turing machine?

Is Nalebinding (suitable to use as) another ancient Turing machine? In a previous series of posts I argued that the three Moirai (aka the Fates) have this capability, see:

From wikipedia page about Nalebinding:

“Nålebinding (Danish: literally “binding with a needle” or “needle-binding”, also naalbinding, nålbinding or naalebinding) is a fabric creation technique predating both knitting and crochet. Also known in English as “knotless netting,” “knotless knitting,” [1] or “single needle knitting,” the technique is distinct from crochet in that it involves passing the full length of the working thread through each loop, unlike crochet where the work is formed only of loops, never involving the free end.”

“Nålebinding works well with short pieces of yarn; based on this, scholars believe that the technique may be ancient, as long continuous lengths of yarn are not necessary. The term “nålebinding” was introduced in the 1970s.[1]

The oldest known samples of single-needle knitting include the color-patterned sandal socks of the Coptic Christians of Egypt (4th century CE), and hats and shawls from the Paracas and Nazca cultures in Peru, dated between 300 BCE and 300 CE.[2][3]

Here is a pair of ancient egyptian socks (courtesy this wiki page) made by the nalebinding technique.


OK, so this is an ancient technique which bears a recent Danish name. I googled for math related to nalebinding and I got some links pointing to hyperbolic surfaces and other nice math visualisations (try to  google for your pleasure), but actually I am afraid of giving the said links because nalebinding has a huge fan base which might get attracted to this post by inadvertence. This post is not, I repeat NOT about the nalebinding hobby.

According to what I could grasp from this very interesting page, there exists a scientific notation for nalebinding stitches which was introduced in the article (cite from the said page):

Hansen, Egon H. “Nalebinding: definition and description.” Textiles in Northern Archaeology: NESAT III Textile Symposium in York 6-9 May 1987, ed. Penelope Walton and John P. Wild, pp. 21-27. London: Archetype Publications, 1990.

Presents a notational system for describing nålebinding stitches that is based on the course the thread takes in traversing each stitch. No historical information included, but lots of technical plates of interlacement variants.

[I need a copy of this article. I could not reach it until now, please, could anybody send me a pdf?]

I think Nalebinding could be turned into a Turing machine. Here comes the more technical part.  Indeed, in graphic lambda calculus the main move is the graphic beta move (which corresponds to beta reduction in lambda calculus).


Or, this graphic beta move can be put into the form of a braiding move. First we define the crossing macro:


then we re-write the graphic beta move as:


Once untyped lambda calculus is put into nalebinding notation, at least in principle is possible to construct a Turing machine. In practice, it might be more feasible to directly construct one.

Anybody raising the (nalebinded) glove?

The three Moirai, continued

UPDATE:  The problem of connecting two gates, as explained in this post, is equivalent with the oriented Reidemeister move R2c, itself equivalent with R3a, for the untyped lambda calculus crossing macro. Therefore we cannot, in graphic lambda calculus, without the dual of the graphic beta move, at least, solve the problem of gate connections.


In the post “Ancient Turing machines (I): the three Moirai” I explained how Clotho, Atropos and Lachesis may build together a Lisp-like based Turing machine, in terms of the graphic lambda calculus.

Clotho creates new thread by inserting FAN-OUT gates (the move CREA), Atropos cuts the thread (the move GARB) and Lachesis performs graphic beta reduction. Either they have an infinite reservoir of loops, or Lachesis may also use the Reidemeister move R1a. (We discussed about oriented Reidemeister moves in the post “Generating set of Reidemeister moves for graphic lambda crossings”  ; the names of the moves are those from the paper    by Michael Polyak  “Minimal generating sets of Reidemeister moves“, only that I use the letter “R” from “Reidemeister” instead of “\Omega” used by Polyak.)

There is something missing, though, namely how to connect gates, once created. I shall explain this further. After that I shall finish with a reminder of the real goal of these posts, essentially mentioned in my comment of the last post.

Recall that the three Moirai know how to create the lambda abstraction gate, the application gate, the FAN-OUT gate and the termination gate, now the question is how they connect two gates, once they have them. In the next figure is given a solution for this.

So, the problem is this: we have two threads, marked 1-2 and 3-4, we want to obtain a thread from 1 to 4. For this we add a loop and Lachesis performs a graphic beta move (alternatively, without adding a loop, Lachesis does a R1a move). Lachesis continues by doing a second graphic beta move, as indicated in the figure. Finally, she performs a number of beta moves  equivalent with the oriented Reidemeister move R2c (see the  mentioned Polyak’s paper for notation). I have not counted how many moves are needed for R2c , but the number can be inferred from the generation of the move R2c from the moves R1a, R1b, R2a, R3a.

Now the construction is finished, let us leave the Moirai to do their job.
Finally, I shall recall my real goal, which I have never forgot. The real goal is to pass from understanding of the power of this lambda calculus sector of graphic lambda calculus to the real deal, called “computing with space”, namely to understand space from a computational perspective, not as a given receptacle, but as a small list of procedures along with some impossible to verify assertions (like that we may rescale indefinitely space), see “emergent algebras”, which can always be eliminated a posteriori, by a kind of finitization procedure.

Ancient Turing machines (I): the three Moirai

This is a first post about interpreting the Turing machine in ancient terms (I have at least another interpretation in mind, which I shall explain later).

It’s your choice to interpret it as a tongue-in-cheek or verbatim. Here are the facts.


Go to the tutorial “Introduction to graphic lambda calculus” if you want to understand the graphic conventions and the moves.



1. The three Moirai, cite from their wiki page:

In Greek mythology, the Moirai (Ancient Greek: Μοῖραι, “apportioners”, Latinized as Moerae)—often known in English as the Fates—were the white-robed incarnations of destiny (Roman equivalent: Parcae, euphemistically the “sparing ones”, or Fata; also equivalent to the Germanic Norns). Their number became fixed at three: Clotho (spinner), Lachesis (allotter) and Atropos (unturnable). […]

  • Clotho (play /ˈklθ/, Greek Κλωθώ [klɔːˈtʰɔː] – “spinner”) spun the thread of life from her distaff onto her spindle. Her Roman equivalent was Nona, (the ‘Ninth’), who was originally a goddess called upon in the ninth month of pregnancy.
  • Lachesis (play /ˈlækɨsɪs/, Greek Λάχεσις [ˈlakʰesis] – “allotter” or drawer of lots) measured the thread of life allotted to each person with her measuring rod. Her Roman equivalent was Decima (the ‘Tenth’).
  • Atropos (play /ˈætrəpɒs/, Greek Ἄτροπος [ˈatropos] – “inexorable” or “inevitable”, literally “unturning”,[16] sometimes called Aisa) was the cutter of the thread of life. She chose the manner of each person’s death; and when their time was come, she cut their life-thread with “her abhorred shears”.[17] Her Roman equivalent was Morta (‘Death’).

2. Let’s interpret their activity as something equivalent to a Turing machine. I shall use untyped lambda calculus, which has the same computational power as Turing machines. Better, I choose to work with graphic lambda calculus (tag archive , first paper), which has a sector equivalent with untyped lambda calculus.

The challenge is to arrive to generate all graphs in GRAPHby using the three Moirai, specifically by formalizing their activity in terms of graphic lambda.

The following figure contains this, let’s contemplate it and then pass to explanations.

CLOTHO   is creating the thread, namely the new move called “CREA” (from “creation”):

Basically she introduces a FAN-OUT gate into the thread. In order to make this gate to function as FAN-OUT, she also needs  from the graphic lambda calculus the moves CO-COMM (which allows her to permute the outputs) and CO-ASSOC (which allows her to not care about the order of application of a cascade of FAN_OUT gates).

ATROPOS cuts the thread, namely she is performing a move which I shall call “GARB” (from “garbage”), which is a new move introduced in graphic lambda calculus:

She picks from the moves of graphic lambda calculus LOCAL PRUNING and ELIMINATION OF LOOPS, which are kind of her style.

LACHESIS  is doing only one move, the graphic beta, described here (and see the paper) as a braiding move, when seen in knot diagrams macro. (She might actually be able to do also the oriented Reidemeister 1a move, see further.)

This is a graphic form of \beta reduction, so you may say that LACHESIS  is performing something akin to \beta reduction.

3. How does it work? The Moirai have a thread to start from. Their first goal is to produce the gates. They can easily  have two gates, one appearing after GARB, the other appearing after CREA. They still need the application gate (corresponding to the application operation in lambda calculus) and the lambda abstraction gate.

They also need to have enough threads to play with. Here are two ways of getting them. The first one is using only GARB and CREA moves. The dashed green curves represent the input and the output of their activities. The dashed red curves indicate where the moves are applied.

Another way of producing two threads from one, more specifically producing a new thread and also keeping the old one, uses also LOCAL PRUNING:

If the Moirai have only one thread and no loop, then we have to add to LACHESIS’s competences the three Reidemeister moves, or at least the Reidemeister 1a move:

Then LACHESIS may use her graphic beta move in order to get a thread and a loop.  ATROPOS has to refrain to use her ELIMINATION OF LOOPS for later!

Now the three Moirai are ready to produce the application and lambda abstraction gates. CLOTHO and LACHESIS  start with two threads (which they already have), in order to get to an intermediary step.

From here, with some help from ATROPOS, they  get a lambda gate and an application gate.

From here the Moirai have to be very clever and patient in order to construct the graphs which correspond to the lambda calculus terms needed for something equivalent of a Turing machine. They have to be clever because they want to construct graphs in GRAPH from the lambda calculus sector, and for this they have to cleverly use loops in order to satisfy, at the end, the global conditions which graphs from the lambda calculus sector satisfy (that is, basically, the condition that whatever exits from the right hand side exit of a lambda gate, has to either end in garbage, or to continue until it enters by the input of the said lambda gate).

Their work could be made easier if they learn a bit of LISP and they follow the indications of  this paper.

That’s it.

We are left with three, very vague questions:

1. Could it be that the Moirai take some shorcuts through the maze of constructing a Turing machine and instead, thread our fates in an equivalent (or more general?) way, but using less sophisticated building blocks?

2. As they spun the destiny of the Universe, they do it in a computable fashion?

3. Could the Moirai build Moirai? (I find this hard to believe, by looking at the GLOBAL CONDITIONS they have to achieve by pure wisdom.)