New Computational Paradigms: Changing Conceptions of What is Computable

S.B. Cooper · Benedikt Löwe · Andrea Sorbi

Nov 2007 · Springer Science & Business Media

About this ebook

In recent years, classical computability has expanded beyond its original scope to address issues related to computability and complexity in algebra, analysis, and physics. The deep interconnection between "computation" and "proof" has originated much of the most significant work in constructive mathematics and mathematical logic of the last 70 years. Moreover, the increasingly compelling necessity to deal with computability in the real world (such as computing on continuous data, biological computing, and physical models) has brought focus to new paradigms of computation that are based on biological and physical models. These models address questions of efficiency in a radically new way and even threaten to move the so-called Turing barrier, i.e. the line between the decidable and the un-decidable.

This book examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. The book opens with an introduction by Andrew Hodges, the Turing biographer, who analyzes the pioneering work that anticipated recent developments concerning computation’s allegedly new paradigms. The remaining material covers traditional topics in computability theory such as relative computability, theory of numberings, and domain theory, in addition to topics on the relationships between proof theory, computability, and complexity theory. New paradigms of computation arising from biology and quantum physics are also discussed, as well as the computability of the real numbers and its related issues.

This book is suitable for researchers and graduate students in mathematics, philosophy, and computer science with a special interest in logic and foundational issues. Most useful to graduate students are the survey papers on computable analysis and biological computing. Logicians and theoretical physicists will also benefit from this book.

Ratings and reviews

This book is comprised of proofs of neo-Turing theories of logic and mathematics in technically advanced publications from the Computability in Europe (CiE) conference in 2005. It advocates the dynamic turn of interactions between observers and systems, and eachother socially. Conversation is computation. Turing’s boss in 1948, Darwin’s grandson, dismissed his paper on “intelligent machines” as merely “a schoolboy essay” so it was not published for two decades. It turned out to be a manifesto for at least AI, connectionism, and neural computing and was accompanied by another discussing evolutionary computing. Turing machines, the basis for modern computers, were derived as a model of computation. The computable analysis problem was to decide what was computable and how long to expect it to take. Applications include wireless mobile nets, neural nets, analog computers, topological spaces, graphics and hardware. There are machines that do not fall into these classes, e.g. algebraic calculations done by planar mechanisms such as rigid bars joined by rotatable rivets, or viewing an eternity in finite time using relativity equations. Information processing is emphasized, e.g. regulatory genomes. Biological computing has new operations such as splicing, crossover and point mutations and annealing, which demonstrate parallelism, reversibility, nondeterminism, energy efficiency, self-healing and evolution. Membrane computing structures have local reaction rules for evolving objects in multisets, e.g. DNA software. Computational models can be classified by space and time, discrete and continuous in each case. The authors look at how nature, or what the universe, computes. Additional directions are pursued including continuous time computations, derivatives of continuous functions and infinite time computation. There are about thirty international contributors beside the three editors. The format combines twenty papers in four parts. New paradigms were expected to follow.