A Formal Model of Universal Algorithmic Assembly and Molecular Computation

A Formal Model of Universal Algorithmic Assembly and Molecular Computation

Bruce MacLennan (University of Tennessee - Knoxville, USA)
Copyright: © 2010 |Pages: 14
DOI: 10.4018/jnmc.2010070104


In this paper, the author describes a systematic and general approach to nanostructure synthesis and control through autonomous molecular combinatory computing. Combinatory computing is based on simple network (graph) substitution operations, deriving from combinatory logic (Curry, Feys, & Craig, 1958), which are sufficient for any computation. When these operations are implemented by autonomous molecular processes, they provide a means for computing within supramolecular networks, which may be used to assemble these networks or control their behavior. Further, the Church-Rosser Theorem (Curry, Feys, & Craig, 1958) proves that substitutions may be performed in any order or in parallel without affecting the computational result; this is a very advantageous property for autonomous molecular computation. In addition to the theoretical foundations of molecular combinatory computing, the author discusses possible molecular implementations as well as accomplishments in the (simulated) synthesis of membranes, channels, nanotubes, and other nanostructures.
Article Preview

Combinatory Computing

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:


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.

Figure 1.

combinator substitution operation. , , and represent any networks (graphs)

The second primitive operation is described by the rule:


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 :

Figure 2.

and combinator substitution operations. for and for . Note the reversed orientation of the rightmost group

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):


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.

Complete Article List

Search this Journal:
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing