The B,C,K,W system
is a variant of combinatory logic that takes as primitive the combinators B, C, K, and W. This system was discovered by Haskell Curry in his doctoral thesis Grundlagen der kombinatorischen Logik, whose results are set out in Curry (1930).
In this post, I shall explain which are the correspondents of the B, C, K, W, combinators in the formalism of the chemical concrete machine, then I shall prove that they are multipliers. In a future post I shall prove that their correspondents in the chemical machine make the machine Turing complete.
Remark: In a sense, this was already established, by using the S, K , I combinators, in the post Local FAN-IN eliminates global FAN-OUT (I) . You only have to pass from the black and white drawing conventions of graphic lambda calculus to the drawings coloured with red and green of the chemical concrete machine, and then use the result which says that combinatory logic can be implemented in graphic lambda calculus with global FAN-OUT. All in all this gives that in the chemical concrete machine the combinatory logic can be implemented without any global move.
However, I think is more instructive to see first why other combinators than S, K, I are multipliers (which is a reformulation of the result mentioned in the remark).
Here are the four “molecules” which represent the combinators B, C, K, W. (Via the red-green vs black-white change of notation, they can be deduced from their expressions in lambda calculus by the algorithm described here . )
Now, let’s prove that they are multipliers! The proofs for B and C are very much alike, therefore I put here only the proof that B is a multiplier:
By the conventions of the chemical concrete machine, I mention here the enzymes which are involved in the reactions, instead of writing the moves, like in the graphic lambda calculus.
The proof that K is a multiplier is the following:
Notice how, in both cases, the reactions seem feasible, in the sense that there are no cases, they can be accomplished by a linear process: pour some DIST enzymes, then some FAN-IN, for B, or DIST, LOC PRUNING and then FAN-IN, for K. More than that, remark that the order of reactions do not matter, i.e. they can be accomplished by pouring all the needed enzymes at the same moment.
For the W combinator (molecule), things get a bit more complex, as was the case for the combinator S:
There is a reaction (or move) which needs explanations. I called it DISENTANGLE (CO-ASSOC) reaction. It is this:
It can clearly be done by a controlled succession of CO-ASSOC moves (reactions). From the point of view of the feasibility in the real world (provided a real implementation of the chemical concrete machine will appear), it seems hard to control the exact order of applications of CO-ASSOC moves which gives the DISENTANGLE move as an effect. So, probably, we shall need a “disentangle enzyme” dedicated to this.
As an alternative, remark that for proving that W is a multiplier we need an application of the DISENTANGLE composite move, described in the next figure:
For practical (or theoretical as well) purposes, it is enough to take this as a move. If you are lost and don’t understand what is the correspondent of this move in lambda calculus, is like this: for any term , if you apply a FAN-OUT gate to then you obtain two . (Recall that’s practically invisible in lambda calculus, because there is no FAN-OUT, instead all variables have names and the pattern matching works by some magic outside that formalism.)
In other words, what would get rid of needing a controlled sequence of CO-ASSOC reactions for multiplying the molecule W is this: assume that the molecule which is connected to the “y” essential molecule (i.e. to the input of a FAN-OUT gate) is a “propagator”. Propagators are defined in the next figure:
Propagators are different from multipliers, because they are molecules with one selected input and one selected output which “propagate along a FAN-OUT gate”, while multipliers are multiplied by a FAN-OUT gate. Propagators can serve in fact as labels, or names, which propagate along a tree of FAN-OUT gates.