See Chemlambda, universality and self-multiplication for multiplication, distribution or propagation phenomena.
In this post we shall see how zipper combinators die or are born, depending on the sense of reading the moves. This can happen in several ways, one of them explained in this post.
This can also be seen as the statement: we can do garbage collection in chemlambda, GLC or zipper logic.
Zipper combinators. The set of zipper combinators is the smallest set of zipper graphs with the properties:
- it contains the S, K, I zipper graphs defined in the next figure
- for any natural number and for any zipper combinators, the zipper graph obtained by connecting the out arrows of the zipper combinators to the in arrows of the half-zipper is a zipper combinator.
- any zipper graph which is obtained by applying a zipper logic move to a zipper combinator is a zipper combinator.
I want to prove that for any zipper combinator , there is a number and a succession of LOCAL PRUNING, CLICK and ZIP moves such that:
Proof. Becauseof the LOC PRUNING move satisfied by $latex (+)$ half-zippers, it follows that by a finite number of these moves we can achieve the effect described in the next figure, for any zipper combinator (of course, the number of these moves depends on ):
It is left to prove that the free arrow ending with a termination node can “eat”, one by one, all the zipper combinators.
For the combinator, it happens like this:
The case of the combinator is described next:
The combinator is absorbed by the following succession of moves:
The proof is done.
We can read all backwards, by saying that an arrow connected to a termination node can give birth to any zipper combinator, with the out arrow connected to a termination node.