This one looks like a bit, but wait, what’s the other one, a hobbit?

I shall use chemlambda in this post. To make it more readable for those who are used with GLC, I shall change the notations  from chemlambda, as described in the first figure.


The node \phi  is the fan-in node, which replaces the dilation node from GLC.

There is a particular small graph which behaves like a bit, a bit. Look:


The (composite) move PROP has been used before. Let me recall that PROP is needed for making the graph of the combinator W to self-replicate. There is a whole discussion about whether is reasonable to have all moves reversible. The conclusion, for chemlambda, is that if we want chemlambda to be Turing universal, then we need only the “+” moves, supplemented by the PROP+ move. Of course that chemlambda is TURING universal if we can use all moves, but using PROP+ instead of using FAN-IN-  seems like a reasonable idea.

In this second figure we see that the “bit” from the left of the first graph, when grafted to the “in” arrow of a fan-out node, comes out by the out arrows of the fan-out node. Behaves like a bit, only that there is only an appearance of a “signal” which circulates through the “wires” (i.e. arrows).

There is another reason to call it a bit, namely that the same pair fan-out node — application node appears in the Church encoding of the naturals, as seen in GLC or chemlambda. More precisely, the natural 3, for example, has 3 such pairs, the natural n (when n is not 0) has n such pairs.  (see Figure 22, p. 14, arXiv:1312.4333)

This “bit” circulates as well through an application node, as explained in the following figure:


A strange thing happens if we graft it to the right out arrow of a lambda abstraction node.


Wait! What’s that at the left out arrow … of the fan-out node? A co-bit? A hobbit?

First, let us notice that this time we used only “+” moves, that’s very good. Then, it looks like that we lost the lambda node, which transformed magically into a fan-out node, and the bit transformed into the hobbit.

Hobbit, or better co-bit? The next figure show that a hobbit and a bit annihilate and produce a loop.

propagator_4Is the hobbit a co-bit?



2 thoughts on “This one looks like a bit, but wait, what’s the other one, a hobbit?”

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s