Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing

At the turning of the millennium, a switch in computing technology is forecasted and looked for. Two main directions of research, both based on quite unconventional ideas are most promising - quantum computing and molecular computing. In the last few years, both of these methods have been intensely investigated. The present book is the first "friendly" presentation of basic ideas in these exciting areas. The style is rigorous, but without entering into excessive technicalities. Equal attention is paid to the main practical results reported so far and the main theoretical developments. The book is written for the educated layman and is self-contained, including all the necessary facts from mathematics, computer science, biology and quantum mechanics.

The theory and technology of computation has rested for more than 50 years on the Turing-machine model, which leads to many intractable problems. Are there any alternatives? Two main directions of research, both based on quite unconventional ideas, are most promising: quantum computing and molecular computing, especially using DNA.

The book presents the main practical results reported so far and the main theoretical developments. In the DNA computing coverage, the authors discuss Adleman's famous experiment, with subsequent variants as well as many theoretical models: sticker systems and Watson-Crick automata, insertion-deletion systems, splicing systems and the idea of "computing by carving". A special feature is the chapter about P systems, computing models based on membrane structures whose theory has only recently emerged. In the quantum realm, the authors present the elementary theory, the logic of quantum computation as well as some important applications to cryptography, teleportation, error correction and randomness.

The book is self-contained, including all the necessary facts from mathematics, computer science, biology and quantum mechanics, It provides a lucid and critical introduction for graduates and advanced undergraduates.