Abstract for the Fourth Foresight Conference on Molecular Nanotechnology.

Emergent Computation by Catalytic Reactions

A copy of the full paper is available on the web

Wolfgang Banzhaf (a) Peter Dittrich (b) Hilmar Rauhe

Author to whom correspondence should be directed Department of Computer Science, University of Dortmund, 44221 Dortmund, Germany
phone: +49-231-9700-953
fax: +49-231-9700-959
Informatik Centrum Dortmund (ICD), Dortmund, Germany Max Planck Institut fuer Zuechtungsforschung, Koeln, Germany

Recently, biochemical systems have been shown to possess interesting computational capabilities (Hjelmfelt et al. [1991], Adleman [1994], Arkin and Ross [1994]). In computer science, on the other hand, the chemical computation metaphor (Fontana [1991], Berry and Boudol [1992], Banzhaf [1993]) as part of the emergent computation paradigm is becoming more and more frequently used.

In this contribution we review the state of the art of computation in the chemical metaphor, outline its relevance to nanotechnology and demonstrateits potential for computing at the molecular level. Using computer experiments a simulated reaction system of mathematical objects is set up and its dynamics is studied. Typical problems of computer science, like i. sorting ii. parity checking iii. prime number computationare placed within the context of computation using molecular interactions.

As a specific in depth example we consider the dynamical prime number computation. There, integer numbers are processed in such a way that division reactions take place between randomly selected pairs of numbers. The result of the computation emerges as a macroscopic phenomenon due to many local microscopic reaction events. Here, the collective result is the appearance of prime numbers which cannot be divided any more by other reactants.

We propose a general method for computing with catalysts.The implications of this approach for i. parallel computers based on molecular devices and ii. DNA-RNA-protein information processing are discussed.