The book series Theory and Applications of Computability is published by Springer
in cooperation with the Association Computability in Europe.
Books published in this series will be of interest to the research community and graduate students, with a
unique focus on issues of computability. The perspective of the series is multidisciplinary, recapturing the
spirit of Turing by linking theoretical and real-world concerns from computer science, mathematics, biology,
physics, and the philosophy of science.
The series includes research monographs, advanced and graduate texts, and books that offer an original
and informative view of computability and computational paradigms.
Peter Hertling (Eds.)
Handbook of Computability and Complexity in Analysis
1st Edition., 2021, XXIV, 426 p. 23 illus.
Hardcover, ISBN 978-3-030-59233-2
Computable analysis is the modern theory of computability and complexity in analysis that arose out of Turing's seminal work in the 1930s.
This was motivated by questions such as: which real numbers and real number functions are computable,
and which mathematical tasks in analysis can be solved by algorithmic means?
Nowadays this theory has many different facets that embrace topics from computability theory, algorithmic randomness, computational complexity,
dynamical systems, fractals, and analog computers, up to logic, descriptive set theory, constructivism, and reverse mathematics.
In recent decades computable analysis has invaded many branches of analysis, and researchers have studied computability and complexity questions
arising from real and complex analysis, functional analysis, and the theory of differential equations, up to (geometric) measure theory and topology.
This handbook represents the first coherent cross-section through most active research topics on the more theoretical side of the field.
It contains 11 chapters grouped into parts on computability in analysis; complexity, dynamics, and randomness; and constructivity, logic,
and descriptive complexity. All chapters are written by leading experts working at the cutting edge of the respective topic.
Researchers and graduate students in the areas of theoretical computer science and mathematical logic will find systematic introductions
into many branches of computable analysis, and a wealth of information and references that will help them to navigate the modern research
literature in this field.
S. Barry Cooper,
Mariya Soskova (Eds.)
Journeys Beyond the Turing Barrier
1st Edition., 2017, X, 292 p. 10 illus.
Hardcover, ISBN 978-3-319-43667-8
This book questions the relevance of computation to the physical universe. Our theories deliver computational descriptions,
but the gaps and discontinuities in our grasp suggest a need for continued discourse between researchers from different disciplines,
and this book is unique in its focus on the mathematical theory of incomputability and its relevance for the real world.
The core of the book consists of thirteen chapters in five parts on extended models of computation; the search for natural
examples of incomputable objects; mind, matter, and computation; the nature of information, complexity, and randomness;
and the mathematics of emergence and morphogenesis.
This book will be of interest to researchers in the areas of theoretical computer science, mathematical logic, and philosophy.
Robert I. Soare
Theory and Applications
1st Edition., 2016, XXXVI, 263 p. 4 illus.
Hardcover, ISBN 978-3-642-31932-7
Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine.
This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute.
This book presents classical computability theory from Turing and Post to current results and methods,
and their use in studying the information content of algebraic structures, models, and their relation to Peano arithmetic.
The author presents the subject as an art to be practiced, and an art in the aesthetic sense of inherent beauty which
all mathematicians recognize in their subject.
Higher Order Computability
1st Edition., 2015, X, 575 p. 2 illus.
Hardcover, ISBN 978-3-662-47991-9
This book offers a self-contained exposition of the theory of computability in a higher-order context,
where 'computable operations' may themselves be passed as arguments to other computable operations.
The subject originated in the 1950s with the work of Kleene, Kreisel and others, and has since expanded
in many different directions under the influence of workers from both mathematical logic and computer science.
The ideas of higher-order computability have proved valuable both for elucidating the constructive content
of logical systems, and for investigating the expressive power of various higher-order programming languages.
Douglas S. Bridges,
Luminiţa Simona Vîţă
Apartness and Uniformity
A Constructive Development
1st Edition., 2011, XIV, 198 p. 3 illus.
Hardcover, ISBN 978-3-642-22414-0
Largely an exposition of the authors' own research, this is the first
book dealing with the apartness approach to constructive topology, and
is a valuable addition to the literature on constructive mathematics and
on topology in computer science. It is aimed at graduate students and
advanced researchers in theoretical computer science, mathematics, and
logic who are interested in constructive/algorithmic aspects of
Rodney G. Downey,
Denis R. Hirschfeldt
Algorithmic Randomness and Complexity
1st Edition., 2010, XXVIII, 855 p. 8 illus.
Hardcover, ISBN 978-0-387-95567-4
This is the first comprehensive treatment of this important field, designed to be both a
reference tool for experts and a guide for newcomers. It surveys a broad section of work
in the area, and presents most of its major results and techniques in depth. It will be of
interest to researchers and students in computability theory, algorithmic information theory,
and theoretical computer science.
This book has received the Shoenfield Prize 2016, which is awarded by the Association for Symbolic
Logic for outstanding expository writing in the field of logic.
Founding Editors: P. Bonizzoni, V. Brattka, S.B. Cooper, E. Mayordomo
Series Advisory Board
- Samson Abramsky (Oxford, UK)
- Eric Allender (Rutgers, New Jersey, USA)
- Klaus Ambos-Spies (Heidelberg, Germany)
- Giorgio Ausiello (Rome, Italy)
- Jeremy Avigad (Carnegie Mellon, Pittsburgh, USA)
- Samuel R. Buss (California, San Diego, USA)
- Rodney G. Downey (Wellington, New Zealand)
- Sergei S. Goncharov (Novosibirsk, Russia)
- Peter Jeavons (Oxford, UK)
- Nataša Jonoska (South Florida, Tampa, USA)
- Ulrich Kohlenbach (Darmstadt, Germany)
- Ming Li (Waterloo, Canada)
- Wolfgang Maass (Graz, Austria)
- Grzegorz Rozenberg (Leiden, The Netherlands and Colorado, USA)
- Alan Selman (Buffalo, New York, USA)
- Wilfried Sieg (Carnegie Mellon, Pittsburgh, USA)
- Jan van Leeuwen (Utrecht, The Netherlands)
- Klaus Weihrauch (Hagen, Germany)
- Philip Welch (Bristol, UK)
Formal or informal book proposals can be
sent directly to members of the editorial board
(contact details are on the linked web pages above).