In this post I want to prove that only with arrow molecules and enzyme moves we can generate all we need for the chemical concrete machine, by using the minimal (?) formalism from Chemical concrete machine, short list of gates and moves . This is done with the help of ideas from the old post Ancient Turing machines (I): the three Moirai, which contains a discussion about generating moves for graphic lambda calculus.
In the post Local FAN-IN eliminates GLOBAL FAN-OUT (II) , at the end, I prove a switch move from CO-COMM and FAN-IN moves. In the next figure, I call this move (which is, recall, a “macro move”, made by a succession of three moves) SWITCH. In the same figure appears a move CREA’. The name is justified by the resemblance with the CREA move proposed in Ancient Turing machines (I): the three Moirai .
Before giving the proof of CREA’, let me remark that from these macro moves, together with the ones selected in the post Chemical concrete machine, short list of gates and moves , we can recover all the generating moves of the three Moirai described in the ancient Turing machine post. For example, CREA’ , used for a triple of arrows, gives both the Clotho’s CREA original move and the Atropos GARB move.
Here is the proof of CREA’:
From a bag of arrows at our discretion, this move gives us fan-out gates and termination gates. Moreover, it is pleasant to see that, as the SWITCH move is a consequence of CO-COMM and FAN-IN, the CREA’ move is a consequence of CO-ASSOC and FAN-IN.
We need the other three trivalent gates, let’s see how we can obtain them (generate them from arrows, by using moves, recall that moves are enzymes, in the world of the chemical concrete machine).
The fan-in gate is generated like this (we already generated termination gates):
The lambda abstraction and application gates can be generated by using the graphic beta move and a SWITCH move.
Now we have all the gates we need and we can proceed to constructing whatever combinator we want from them, mainly by using SWITCH moves. One elegant way for doing this would be to construct zippers first, by using the graphic beta moves, then construct the S,K,I combinators from zippers, as indicated in Combinators and zippers.
Probably, the real chemical concrete machine will function with terms (molecules) created by some more natural chemistry tricks, but it is pleasant to see that in principle we can also construct what we need, before passing to the “computation” part, only by using arrows and moves.