automaton continuously updating its
rules. Along the same lines, it has been
recently suggested that the universe is
a quantum computer that computes itself and its own behavior.
natural sciences: ours to Discover
Science advances in ever-widening circles of knowledge. Sometimes it meticulously crawls. Other times it leaps to a
new dimension of understanding and,
in the process, it reinvents itself. As the
natural sciences are rapidly absorbing
ideas of information processing, and
the meaning of computation is changing as it embraces concepts from the
natural sciences, we have the rare privilege to take part in several such metamorphoses.
At this moment we and our natural
scientist fellows are awash in wave after
gigantic wave of experimental, especially biological, data. Just underneath this
tumultuous surface lie ingenious algorithms waiting to be designed, elegant
theorems waiting to be proven, natural
laws waiting to be discovered that will
put order into chaos. For, as Spinoza
wrote, “nothing happens in nature that
does not follow from her laws.”
Conversely, as this review shows,
there is an abundance of natural phenomena that can inspire computing
paradigms, alternative physical substrates on which to implement computations, while viewing various natural
processes as computations has become
more and more essential, desirable,
and inevitable. All these developments
are challenging our assumptions about
computation, and indeed, our very definition of it.
In these times brimming with excitement, our task is nothing less than
to discover a new, broader, notion of
computation, and to understand the
world around us in terms of information processing.
Let us step up to this challenge. Let
us befriend our fellow the biologist, our
fellow the chemist, our fellow the physicist, and let us together explore this
new world. Let us, as computers in the
future will, embrace uncertainty. Let us
dare to ask afresh: “What is computation?”, “What is complexity?”, “What
are the axioms that define life?”
Let us relax our hardened ways of
thinking and, with deference to our scientific forebears, let us begin anew.
The upper-bound placed on the number of references was a real limitation
for this review, since the literature on
natural computing is vast. For a more
complete list of references the reader
is referred to the full version of this article at www.csd.uwo.ca/˜lila/Natural-Computing-Review.pdf.
Almost each of the areas we mentioned here has an extensive scientific literature as well as a number of
specialized journals and book series.
There are also journals and book series aimed at the general natural computing community, among them the
journals Natural Computing, Springer,
Theoretical Computer Science, Series C:
Theory of Natural Computing, Elsevier,
the Natural Computing book series,
Springer, and the upcoming Handbook
of Natural Computing (G. Rozenberg, T.
Bäck, J. Kok, editors, Springer).
We gratefully acknowledge comments
on early drafts of this paper by T. Bäck,
D. Bentley, G. Brassard, D. Corne, M.
Hirvensalo, J. Kari, P. Krishna, H. Lipson, R. Mercer, A. Salomaa, K. Sims, H.
Spaink, J. Timmis, C. Torras, S. Watt,
This work was supported by NSERC
Discovery Grant and Canada Research
Chair Award to L.K., and NSF grant
0622112 to G.R.
1. Abelson, H., Allen, D., Coore, D., Hanson, C., Homsy, G.,
Knight Jr., T., Nagpal, R., Rauch, E., Sussman, G., and
Weiss, R. Amorphous computing. Commun. ACM 43, 5
(May 2000), 74–82.
2. Adleman, L. Molecular computation of solutions
to combinatorial problems. Science 266 (1994),
3. Andrianantoandro, E., Basu, S., Karig, D., and Weiss,
R. Synthetic biology: new engineering rules for an
emerging discipline. Molecular Systems Biology 2
4. Angeleska, A., Jonoska, N., Saito, M., and Landweber,
L. RNA-guided DNA assembly. J. Theoretical Biology
248 (2007), 706–720.
5. Arbib, M., editor. The Handbook of Brain Theory and
Neural Networks. MIT Press, 2003.
6. Bäck, T., Fogel, D., and Michalewicz, Z., editors.
Handbook of Evolutionary Computation. IOP
Publishing, U. K., 1997.
7. Barry, P. Life from scratch: learning to make synthetic
cells. Science News, 173, 2 (2008), 27.
8. Bath, J. and Turberfield, A. DNA nanomachines.
Nature Nanotechnology 2 (May 2007), 275–284
9. Brooks, R. Artificial life: From robot dreams to reality.
Nature 406 (2000), 945–947.
10. Cardelli, L. Machines of systems biology. Bulletin of
the EATCS 93 (2007), 176–204.
11. Dasgupta, D. editor. Artificial Immune Systems and
Their Applications. Springer, 1998.
12. de Castro, L. and Timmis, J. Artificial Immune
Systems: A New Computational Intelligence
Approach. Springer, 2002.
13. De Jong, K. Evolutionary Computation: A Unified
Approach. MIT Press, 2006.
14. Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D., and
Rozenberg, G. Computation in Living Cells: Gene
Assembly in Ciliates. Springer, 2004.
15. Endy, D. Foundations for engineering biology. Nature
438 (2005), 449–453.
16. Engelbrecht, A. Fundamentals of Computational
Swarm Intelligence. Wiley and Sons, 2005.
17. Forster, A. and Church, G. Towards synthesis of a
minimal cell. Molecular Systems Biology 2, 45 (Aug.
18. Fox Keller, E. and Harel, D. Beyond the gene. PLoS
ONE 2, 11 (2007), e1231.
19. Hirvensalo, M. Quantum Computing, 2nd Ed. Springer,
20. Istrail, S., De-Leon, B-T., and Davidson, E. The
regulatory genome and the computer. Developmental
Biology 310 (2007), 187–195.
21. Kari, L. DNA computing—the arrival of biological
mathematics. The Math. Intelligencer 19, 2 (1997),
22. Koza, J. Genetic Programming: On the Programming of
Computers by Means of Natural Selection. MI T Press,
23. Landweber, L. and Kari, L. The evolution of cellular
computing: Nature’s solution to a computational
problem. Biosystems 52, 1/3 (1999), 3–13.
24. Langton, C., editor. Artificial Life. Addison- Wesley
25. Lipson, H. and Pollack, J. Automatic design and
manufacture of robotic lifeforms. Nature 406, (2000),
26. Paun, G. Membrane Computing: An Introduction.
27. Paun, G., Rozenberg, G., and Salomaa, A. DNA
Computing: New Computing Paradigms. Springer,
28. Prescott, D., Ehrenfeucht, A., and Rozenberg, G.
Template guided recombination for IES elimination
and unscrambling of genes in stichotrichous ciliates. J.
Theoretical Biology 222, 3 (2003), 323–330.
29. Prusinkiewicz, P. and Lindenmayer, A. The Algorithmic
Beauty of Plants. Springer, 1990.
30. Reif, J. and LaBean, T. Autonomous programmable
biomolecular devices using self-assembled DNA
nanostructures. Commun. ACM 50, 9 (Sept. 2007),
31. Rojas, R. Neural Networks: A Systematic Introduction.
32. Rothemund, P., Papadakis, N., and Winfree, E.
Algorithmic self-assembly of DNA Sierpinski triangles.
PLoS Biology 2, 12 (Dec. 2004).
33. Rozenberg, G. Computer science, informatics and
natural computing—personal reflections. In New
Computational Paradigms: Changing Conceptions of
What Is Computable. Springer, 2008, 373–379.
34. Rozenberg, G. and Salomaa, A. The Mathematical
Theory of L Systems. Academic Press, 1980.
35. Seeman, N. Nanotechnology and the double helix.
Scientific American Reports, 17, 3 (2007), 30–39.
36. Sims, K. Evolving 3D morphology and behavior by
competition. In Proceedings of Artificial Life IV. MIT
Press, 1994, 28–39.
37. Smith, H., Hutchison III, C., Pfannkoch, C., and Venter,
C. Generating a synthetic genome by whole genome
assembly: fX174 bacteriophage from synthetic
oligonucleotides. PNAS 100, 26 (2003), 15440–15445.
38. Stepney, S. et al. Journeys in non-classical
computation I: A grand challenge for computing
research. Int. J. Parallel, Emergent and Distributed
Systems 20, 1 (2005), 5–19.
39. von Neumann, J. The Computer and the Brain. Yale
University Press, 1958.
40. von Neumann, J. Theory of Self-Reproducing
Automata. U. Illinois Press, 1966. Edited and
completed by A. W. Burks.
Lila Kari ( email@example.com) is Professor and Canada
Research Chair in Biocomputing in the Department of
Computer Science at the University of Western Ontario,
Grzegorz Rozenberg ( firstname.lastname@example.org) is Professor
at the Leiden Institute of Advanced Computer Science,
Leiden University, Leiden, The Netherlands, and Adjunct
Professor in the Department of Computer Science at the
University of Colorado at Boulder, USA.
© 2008 ACM 0001-0782/08/1000 $5.00