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

banzhaf@ls11.informatik.uni-dortmund.de

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.

- Adleman [1994]: L.M. Adleman, Molecular Computation of Solutions to Combinatorial Problems, Science, 266 (1994) 1021
- Arkin and Ross [1994]: A. Arkin and J. Ross, Computational Functions in Biochemical Reaction Networks, Biophys. J., 67 (1994) 560
- Banzhaf [1993]: W. Banzhaf, Self-replicating sequences of binary numbers -- Foundations I and II: General and Strings of Length N = 4, Biol. Cybern. 69 (1993) 269
- Berry and Boudol [1992]: G. Berry and G. Boudol, The chemical abstract machine, Theor. Computer Science 96 (1992) 217
- Fontana [1991]: W. Fontana, Algorithmic Chemistry, in: Artificial Life II: Proceedings of the 2nd ALife Workshop, (C.G. Langton et al., eds.), Addison Wesley, Reading, MA, 1991, 159-209
- Hjelmfelt et al. [1991]: A. Hjelmfelt, E.D. Weinberger and J. Ross,Chemical implementation of neural networks and Turing machines Proc. Natl. Acad. Sci. USA, 88 (1991) 10983