Distributed GLC, discussion (II)

Continues from   Distributed GLC, discussion (I) , and contains further notes about the distributed computing model with GLC actors from GLC actors, artificial chemical connectomes, topological issues and knots , arXiv:1312.4333, written with Louis Kauffman .

The first part of this post concerns more explanations about the fact that we don’t need to use signal passing through gates in this model. This has been explained in  Distributed GLC, discussion (I) ,  here I want to insist by saying that an implication of this is that evaluation (in the sense used for  expressions, terms, etc, from lambda calculus) is not needed for computation!

This has been already mentioned in an older post  I-don’t-always advantage of the chemical concrete machine . I borrow from it some parts:

WHEN_FAN_OUT

Indeed, usually a FAN-OUT gate is something which has a variable as an input and two copies of it as an output. That is why FAN-OUT gates are not available in any model of computation, like for example in quantum computing.

But if you don’t use variable (names) and there’s nothing circulating through the wires of your computer model, then you can use the FAN-OUT gate, without  impunity, with the condition to have something which replaces the FAN-OUT behaviour, without it’s bad sides.  Consider graph rewriting systems for your new computer.

This is done in the chemical concrete machine, with the help of DIST enzymes and associated moves (chemical reactions). (“DIST” comes from distributivity.)

Btw, maybe is good to write few words about the common things and differences between GLC and chemlambda.

  • they are both graph rewriting systems
  • the graphs they are using are the same, based on 4 trivalent nodes and one univalent one, only the drawing convention is different
  • they are Turing universal, because both contain combinatory logic and untyped lambda calculus (without eta reduction!)
  • but lambda calculus is just one part of the things they can both do!
  • most of the graph rewrites (moves) are the same
  • but there are some moves which are different: the FAN-IN move from chemlambda applies to a node which is called here “fan-in”, replacing the emergent algebra moves which apply to the node \varepsilon from GLC. Also the GLOBAL FAN-OUT move from GLC is replaced by DIST moves in chemlambda
  • therefore chemlambda has only local moves, while GLC has also some global moves
  • moreover, the replacement of the GLOBAL FAN-OUT by DIST moves does make them different formalisms.

I hope that until now it is clear that lambda calculus is one sector (i.e. one part) of GLC and chemlambda and that, explicitely, both GLC and chemlambda can do other things than lambda calculus.

Mind you that I am not claiming that lambda calculus can’t do everything that GLC or chemlambda can (actually I simply think that this is a bad formulated statement). What is proved is that GLC and chemlambda can be applied to several formalisms, the contrary implications are to be proved (but this is part of a larger discussion, like the one concerning the Actor Model of Hewitt compared with the Turing Machine, and so on, I don’t want to enter into this).

Now I am going to borrow something from an older post, in order to show you in a very short way that indeed, GLC and chemlambda are different.

The following pictures are taken from the post Metabolism of loops (a chemical reaction network in the chemical concrete machine)

chem_eval_4

With the drawing conventions from chemlambda, but using only the GLC moves, we see in the upper side of this figure, the graph associated to the combinator \Omega = (\lambda x . (xx)) (\lambda x . (xx)). In lambda calculus, we may go forever trying to reduce this. The figure shows the same, we turn in place after the application of a graphic beta move, followed by a GLOBAL FAN-OUT.

This is the situation in GLC. Now let’s do the same in chemlambda:

chem_eval_2

There are multiple ways to perform moves, some of them can be done in parallel. There is no effort here to recast this into a GLC actors version, this is simply a drawing which tries to convey what can happen by applying moves, starting from the graph of \Omega.

But, rather amazingly, there is a way to get out the loop of moves, look at the lower part of the figure. Because of the DIST and FAN-IN moves, we went out from the lambda calculus sector. We can “reduce” the \Omega combinator to a pair of loops and a weird fan-out node with one exit arrow connected to it’s input arrow.

______________________

Advertisements

One thought on “Distributed GLC, discussion (II)”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s