The construction of molecular-scale machines requires novel paradigms for their programming. Here, we assume a scenario of distributed devices that process in-formation by chemical reactions and that communicate by exchanging molecules. Programming such a distributed system requires specifing reaction rules as well as exchange rules. Here, we present an approach that helps to guide the manual construction of distributed chemical programs. We show how chemical organization theory can assist a programmer in predicting the behavior of the program. The basic idea is that a computation should be understood as a movement between chemical organizations, which are closed and self-maintaining sets of molecular species. When sticking to that design principle, fine-tuning of kinetic laws becomes less important. We demonstrate the approach by a novel chemical program that solves the maximal independent set problem on a distributed system without any central control—a typical situation in ad-hoc networks. We show that the computational result, which emerges from many local reaction events, can be explained in terms of chemical organizations, which assures robustness and low sensitivity to the choice of kinetic parameters.
TopIntroduction
Nanotechnology and molecular computation are a great match since those share the same scale medium: nanoscale molecules. Under the achievements of nanotechnology, lots of examples including logic gates using multiple nanotube transistors (Bachtold, Hadley, Nakanishi, & Dekkerdagger, 2001) have been reported. Wide varieties of nanoparticle applications (Salata, 2004), for example, ultrasensitive biosensors (Wang, 2005) using gold nanoparticles coupled with enzymes (Willner, Basnar, & Willner, 2007), attribute to nanotechnological techniques of manipulating nano-scale objects. Synthesizing molecular machinery out of DNA molecules seems promising (Bath & Turberfield, 2007) even though the lack of stiffness of biomolecules in comparison with ‘dry’ nanotechnology materials has been argued (Merkle, 2000) to be the drawback. Despite the rapid development of nanotechnology, wet-lab experiments are commonly exercised to operate the boolean logics (de Silva & Uchiyama, 2007).
DNA computing demonstrated by Adleman (1994) already addressed that limitation of imperative computation paradigms by utilizing particular operation modes of DNA molecules. Assuming DNA as data carrier, up to 
bytes can be saved and operated simultaneously within one liter of liquid providing a storage density of 
(Păun, Rozenberg, & Salomaa, 1998). One Joule allows up to
molecular operations on DNA (Pisanti, 1998). This highly parallelized operation on DNA strands with high data density is the key characteristics of the DNA computation approach. The significance, we note here, is that the computation model is in concert with computation medium.
In the nano-scale world, molecules are regarded to constitute a medium, and chemical reactions play an important role in biological information processing principles (Küppers, 1990). Employing molecules and reaction rules as a metaphor, thus, novel computation paradigms have been explored (Banâtre & Mètayer, 1986; Păun, 2002; Banâtre, Fradet, & Redenac, 2004; Tschudin, 2003; Berry & Boudo, 1992). Essentially, those chemical computing models refer the elementary units as molecules, and the operations are described in the form of reactions among those molecules. Given the inputs of the computation as the initial configuration of reaction vessels or reactors, the outputs emerge from local interactions in accordance with the given reaction rules (Banzhaf, Dittrich, & Rauhe, 1996). In these chemical computing models, programming corresponds to designing the reaction rules at the microscopic levels, and the desired computational result emerges at the macroscopic levels as a global systems’ state. The relation between those two levels is highly non-linear, and thus the question for effective programming techniques arises. It seems scarcely possible in this context to predict the macro behavior from the micro rules because of the parallel operations of the reaction rules that are possibly tangled in a complex manner. A common approach to this difficulty is to find a mapping from a known computation model like a Turing machine or a finite state automaton (Păun, 2002; Rothemund, 1996).