In the 1930s a series of seminal works published by Alan Turing, Kurt Gödel, Alonzo Church, and others
established the theoretical basis for computability. This work, advancing precise characterizations of
effective, algorithmic computability, was the culmination of intensive investigations into the foundations of
mathematics. In the decades since, the theory of computability has moved to the center of discussions
in philosophy, computer science, and cognitive science. In this volume, distinguished computer scientists,
mathematicians, logicians, and philosophers consider the conceptual foundations of computability
in light of our modern understanding.
Some chapters focus on the pioneering work by Turing, Gödel, and Church, including the Church–Turing
thesis and Gödel’s response to Church’s and Turing’s proposals. Other chapters cover more recent
technical developments, including computability over the reals, Godel’s influence on mathematical
logic and on recursion theory and the impact of work by Turing and Emil Post on our theoretical understanding
of online and interactive computing; and others relate computability and complexity to issues
in the philosophy of mind, the philosophy of science, and the philosophy of mathematics.