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).