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 “” 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.

About these ads