Continues from Birth and death of zipper combinators (I).
In the following is presented another mechanism of birth/death of zipper combinators, which is not using a garbage collecting arrow and termination node.
For any zipper combinator there is a number and a succession o f CLICK, ZIP and LOC PRUNING moves such that
So this time we transform a zipper combinator connected to a termination node into a bunch of loops.
Proof. The first part is identical with the one from the previous post, namely we remark that we can reduce the initial zipper combinator with the exit connected to a termination node into a finite collection of simpler zippers.
This is done by a succession of LOC PRUNING moves for half-zippers.
We shall use then the following succession of moves, in order to “unlock” half-zippers.
If we use this for the zipper combinator then we can transform it into one loop.
The same trick is used for transforming the zipper combinator into two loops.
The zipper combinator is transformed into three loops, starting by the same trick.
The proof is done.
It follows that w can replace garbage collection by ELIM LOOPS, a move which appeared in earlier formulations of chemlambda.
Seen from the birth point of view, if we have enough loops then we can construct any zipper combinator (with the exit arrow connected to a termination node).