## Computability: Turing, Gödel, Church, and BeyondComputer scientists, mathematicians, and philosophers discuss the conceptual foundations of the notion of computability as well as recent theoretical developments. 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.ContributorsScott 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 |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 Turing versus Gödel on Computability and the Mind | 1 |

2 Computability and Arithmetic | 35 |

3 About and around Computing over the Reals | 55 |

4 The ChurchTuring Thesis as a Special Corollary of Gödels Completeness Theorem | 77 |

5 Computability and Constructibility | 105 |

6 After Gödel | 141 |

7 The Open Texture of Computability | 153 |

8 Gödels Philosophical Challenge to Turing | 183 |

9 Interactive Computing and Relativized Computability | 203 |

10 Why Philosophers Should Care about Computational Complexity | 261 |

11 Is Quantum Mechanics Falsifiable? A Computational Perspective on the Foundations of Quantum Mechanics | 329 |

About the Authors | 351 |

355 | |

### Other editions - View all

Computability: Turing, Gödel, Church, and Beyond B. Jack Copeland,Carl J. Posy,Oron Shagrir Limited preview - 2013 |

Computability: Turing, Gödel, Church, and Beyond B. Jack Copeland,Carl J. Posy,Oron Shagrir No preview available - 2015 |

### Common terms and phrases

a-machine Alan Turing algorithm argument arithmetic axioms Brouwer calculable functions called Church-Turing thesis Church’s thesis classical complexity theory computability theory computable functions computational complexity computer science concept Copeland Davis defined deﬁnition Diophantine effectively calculable Entscheidungsproblem equivalent example exponential fact Feferman ﬁnite finite number first-order logic formal system formula function f Gandy given Godel graph h-definable Herbrand-Godel Hilbert hypothesis infinite integers interactive proof intuition intuitionistic Kant’s Kleene lecture mathematical proof Mathematical Society mathematician mean mechanical procedure mind natural numbers NP-complete objects oracle machine Oxford paper Peano arithmetic philosophy physical polynomial Post’s predicate primitive recursive problem proposition proved PSPACE quantum computing quantum mechanics qubits question random real numbers recursion theory recursive functions recursively enumerable reﬂect relative computability result sequence Shagrir Sieg Soare Symbolic Logic theorem tion Turing computable Turing machine Turing test Turing’s Turing’s analysis Undecidable University Press unsolvable Wang