C.S. Calude, J. Casti, M.J. Dinneen (eds.). *Unconventional Models
of Computation, *Springer-Verlag, Singapore, 1998, viii + 426 pp. ISBN:
981-3083-69-7. US$ 59 softcover.

For over fifty years, the Turing machine model of computation has defined what it means to "compute'' something. This definition has led to a dichotomy between "hard'' and "easy" computational problems, culminating in the famous P ?= NP conjecture, asserting that the hard problems really are hard. Essentially all the theoretical results in the modern theory of algorithms rest on this Turing model. But there are alternatives...

In recent years, researchers have looked at natural processes in the
physical and biological world as motivation for constructing new models
of computation holding out the hope of breaking the "Turing barrier.''
The quantum phenomenon of interference has led to one such model, as has
the process of folding of DNA strands in a living cell. In addition, refinements
to the Turing view of computing have led to other, so-called "super-Turing''
models, that allow one to compute in ways that transcend Turing's original
scheme. Real-number models have also been proposed, in which computation
is carried out over a continuous number field like the real or complex
numbers, thereby mimicking more closely the models of the natural sciences.
In this meeting, all the foregoing non-Turing models are explored with
an eye toward understanding the *true *limits of computation, thereby
shedding light on the basic question of the limits to scientific knowledge.

This book covers recent research into unconventional methods of computing for disciplines in computer science, mathematics, biology, physics and philosophy. Subjects include: nonconventional computational methods, DNA computation, quantum computation, and beyond Turing computability, new methods of discrete computation, theoretical and conceptual new computational paradigms, and practical knowledge on new computing technologies.

*Contents: *Invited papers: Practical Implementation of DNA Computations
(M. Amos et al); An Overview of Quantum Computing (A. Ekert & C. Macchiavello);
Implementing Quantum Logic and Communication via Cavity QED (H. J. Kimble);
Unconventional Quantum Computing Devices (S. Lloyd); Finite-Dimensional
Analog Computers: Flows, Maps, and Recurrent Neural Networks (C. Moore);
Paradigms for Biomolecular Computation (J. H. Reif); Turing, Watson-Crick
and Lindenmayer. Aspects of DNA Complementarity (A. Salomaa). Contributed
papers: Explicitly Constructing Universal Extended H Systems (G. Alford);
Unconventional Approaches for Biologically Inspired Computing (M. H. butler
et al.); Deterministic Incomplete Automata: Simulation, Universality and
Complementarity (E. Calude & M. Lipponen); Even Turing Machines Can
Compute Uncomputable Functions (B. J. Copeland); Reversibility in Optimally
Scalable Computer Architectures (M. Frank et al.); A Scalable Reversible
Computer in Silicon (M. Frank et al.); Molecular Computations on Circular
and Linear Strings (R. Freund & V. Mihalache); Genetic Algorithms for
Optimization on a Quantum Computer (Y. Z. Ge et al.); Ergodic Learning
Algorithms (K. Gustafson); Embedding Cellular Automata into Reversible
Ones (P. Hertling); Cellular Gate Technology (T. F. Knight, Jr. & G.
J. Sussman); Splicing on Routes: A Framework of DNA Computation (A. Matsueda);
Spatiotemporal Evolution of Quantum Entangled pure States in Quantum Computing
Solid Block Circuits (H. Matsueda); Cobinators and Processing-In-Memory:
An Unconventional Basis for Avoiding the Memory Wall (L. Narayanaswamy
& P. M. Kogge); The Minimum DNA Computation Model and Its Computational
Power (M. Ogihara & A. Ray); Distributed Architectures in DNA Computing
Based on Splicing: Limiting the Size of Components (G. Paun); Resonance
Scattering and Design of Quantum Gates (B. Pavlov et al.); Self-Similar
Sets as Satisfiable Boolean Expressions (Y. Sato et al.); The Church-Turing
Thesis as a Guiding Principle for Physics (K. Svozil); Designing Reversible
Memory (G. Vieri et al.); Quantitative Computation by Hilbert Machines
(H. Wiklicky).