In this Book

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, Gödel'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. Contributors:Scott Aaronson, Dorit Aharonov, B. Jack Copeland, Martin Davis, Solomon Feferman, Saul Kripke, Carl J. Posy, Hilary Putnam, Oron Shagrir, Stewart Shapiro, Wilfried Sieg, Robert I. Soare, Umesh V. Vazirani

Table of Contents

  1. Cover
  2. restricted access Download |
  1. Title Page, Copyright
  2. pp. i-iv
  3. restricted access Download |
  1. Contents
  2. pp. v-vi
  3. restricted access Download |
  1. Introduction: The 1930s Revolution
  2. pp. vi-x
  3. restricted access Download |
  1. 1. Turing versus Gödel on Computability and the Mind
  2. B. Jack Copeland and Oron Shagrir
  3. pp. 12-45
  4. restricted access Download |
  1. 2. Computability and Arithmetic
  2. Martin Davis
  3. pp. 46-65
  4. restricted access Download |
  1. 3. About and around Computing over the Reals
  2. Solomon Feferman
  3. pp. 66-87
  4. restricted access Download |
  1. 4. The Church-Turing “Thesis” as a Special Corollary of Gödel’s Completeness Theorem
  2. Saul A. Kripke
  3. pp. 88-115
  4. restricted access Download |
  1. 5. Computability and Constructibility
  2. Carl J. Posy
  3. pp. 116-151
  4. restricted access Download |
  1. 6. After Gödel
  2. Hilary Putnam
  3. pp. 152-163
  4. restricted access Download |
  1. 7. The Open Texture of Computability
  2. Stewart Shapiro
  3. pp. 164-193
  4. restricted access Download |
  1. 8. Gödel’s Philosophical Challenge (to Turing)
  2. Wilfried Sieg
  3. pp. 194-213
  4. restricted access Download |
  1. 9. Interactive Computing and Relativized Computability
  2. Robert Irving Soare
  3. pp. 214-271
  4. restricted access Download |
  1. 10. Why Philosophers Should Care about Computational Complexity
  2. Scott Aaronson
  3. pp. 272-339
  4. restricted access Download |
  1. 11. Is Quantum Mechanics Falsifiable? A Computational Perspective on the Foundations of Quantum Mechanics
  2. Dorit Aharonov and Umesh V. Vazirani
  3. pp. 340-361
  4. restricted access Download |
  1. About the Authors
  2. pp. 362-365
  3. restricted access Download |
  1. Index
  2. pp. 366-373
  3. restricted access Download |

Additional Information

Related ISBN
MARC Record
Launched on MUSE
Open Access
Back To Top

This website uses cookies to ensure you get the best experience on our website. Without cookies your experience may not be seamless.