Computational Primitives
Molecular combinatory programs are supramolecular structures in the form of binary trees. The interior nodes of the tree (which we call 
nodes) represent the application of a function to its argument, the function and its argument being represented by the two daughters of the 
node. The leaf nodes are molecular groups that function as primitive operations and data.
One of the remarkable theorems of combinatory logic is that two simple substitution operations are sufficient for implementing any program (Turing-computable function). One of these operations is called 
and is described by the substitution rule:
(1)Here 
and 
represent arbitrary binary trees and 
represents a leaf of type 
; parentheses group the subtrees of an interior node (an 
node). The interpretation of the rule is that wherever a subtree of the form 
is found in the network, it may be replaced by 
. This reaction is depicted in Figure 1, which also illustrates its similarity to a molecular substitution reaction. The effect of the operation is to delete 
from the network. The 
group and 
subtree are released as waste products, which may be recycled in later reactions.
The second primitive operation is described by the rule:
(2)This rule may be interpreted in two ways, either as copying the subtree 
or as creating two links to a shared copy of 
(thus creating a graph that is not a tree). It can be proved that both interpretations produce the same computational result, but they have different effects when used for nanostructure assembly. For this reason we need both variants of the operation, which we denote 
(replicating) and 
(sharing). The molecular implementations of the two are very similar (see Figure 2). If 
(a sharing node), then we have two links to a shared copy of 
:
The structure created by this operator shares a single copy of 
; the notations 
and 
refer to two links to a “Y-connector” (called a 
node), which links to the original copy of 
. (Subsequent computations may rearrange the locations of the two links.) The principal purpose of the 
operation is to synthesize non-tree-structured supramolecular networks.
On the other hand, if 
(a replication node), then other substitution reactions will begin the replication of 
, so that eventually the two links will go to two independent copies of 
:
Here 
refers to a new copy of the structure 
, which is created by the primitive replication (
) operation. It can be shown that computation can proceed in parallel with replication without affecting the results of the process (a consequence of the Church-Rosser theorem) .
Although 
and 
are sufficient for all computation, they cannot (even with 
) create cyclic structures, for which we use an additional primitive operation 
, which creates a self-referential link through a 
-node. It is defined (MacLennan, 2002c):
(3)The operation creates an elementary cycle, which may be expanded by computation in the combinator tree 
(Figure 3). Examples of the use of both 
and 
are given below.
Figure 3. combinator primitive substitution operation. Arrows indicate link direction; note resulting elementary cycle between 
- and 
-groups.