Computability ― Turing, Godel, Church, and Beyond

In the 1930s a series of seminal works published by Alan Turing, Kurt Godel, AlonzoChurch, and others established the theoretical basis for computability. This work, advancing precisecharacterizations of effective, algorithmic computability, was the culmination of intensiveinvestigations into the foundations of mathematics. In the decades since, the theory ofcomputability has moved to the center of discussions in philosophy, computer science, and cognitivescience. In this volume, distinguished computer scientists, mathematicians, logicians, andphilosophers consider the conceptual foundations of computability in light of our modernunderstanding. Some chapters focus on the pioneering work by Turing, Godel, and Church, includingthe Church-Turing thesis and Godel's response to Church's and Turing's proposals. Other chapterscover more recent technical developments, including computability over the reals, Godel's influenceon mathematical logic and on recursion theory and the impact of work by Turing and Emil Post on ourtheoretical understanding of online and interactive computing; and others relate computability andcomplexity to issues in the philosophy of mind, the philosophy of science, and the philosophy ofmathematics.

Contributors:Scott Aaronson, Dorit Aharonov, B.Jack Copeland, Martin Davis, Solomon Feferman, Saul Kripke, Carl J. Posy, Hilary Putnam, OronShagrir, Stewart Shapiro, Wilfried Sieg, Robert I. Soare, Umesh V. Vazirani