Computability: Turing, G?del, Church, and Beyond

Computability: Turing, G?del, Church, and Beyond




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.


Product Details

ISBN-13: 9780262018999
Publisher: MIT Press
Publication date: 06/30/2013
Pages: 376
Product dimensions: 7.20(w) x 9.20(h) x 0.50(d)
Age Range: 18 Years

About the Author

B. Jack Copeland is Professor of Philosophy at the University of Canterbury, New Zealand, Director of the Turing Archive for the History of Computing, and Honorary Research Professor of Philosophy at the University of Queensland, Australia.

Carl J. Posy is Professor of Philosophy and Member of the Centers for the Study of Rationality and for Language, Logic, and Cognition at the Hebrew University of Jerusalem.

Oron Shagrir is Professor of Philosophy and Former Chair of the Cognitive Science Department at the Hebrew University of Jerusalem. He is currently the vice rector of the Hebrew University.

Table of Contents

Introduction: The 1930s Revolution vii

1 Turing versus Gödel on Computability and the Mind B. Jack Copeland Oron Shagrir 1

2 Computability and Arithmetic Martin Davis 35

3 About and around Computing over the Reals Solomon Feferman 55

4 The Church-Turing "Thesis" as a Special Corollary of Gödel's Completeness Theorem Saul A. Kripke 77

5 Computability and Constructibility Carl J. Posy 105

6 After Gödel Hilary Putnam 141

7 The Open Texture of Computability Stewart Shapiro 153

8 Gödel's Philosophical Challenge (to Turing) Wilfried Sieg 183

9 Interactive Computing and Relativized Computability Robert Irving Soare 203

10 Why Philosophers Should Care about Computational Complexity Scott Aaronson 261

11 Is Quantum Mechanics Falsifiable? A Computational Perspective on the Foundations of Quantum Mechanics Dorit Aharonov Umesh V. Vazirani 329

About the Authors 351

Index 355

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews

Computability: Turing, G?del, Church, and Beyond 5 out of 5 based on 0 ratings. 1 reviews.
jax2009 More than 1 year ago
This is a wonderful book, and a lot more important than the title suggests. The modest title, "Computability" represents the academic convention for talking about, "What the heck, really, is a computer?" The book, like computation itself, addresses mathematical, philosophical, and pragmatic issues. The origins of the modern computer, by pretty much all accounts, are Turing's 1936 paper, "On Computable Numbers", but no scientific breakthroughs are really isolated. Church was Turing's thesis advisor and had just published his own paper on the matter of computability, and both Church and Turing were writing in the years just after Godel had published his groundbreaking papers on the incompleteness of computability. This book brings together this history in significantly new perspective, based on the recent publication of Godel's collected papers. It comes out more than ever in favor of Turing as the one who really captured the mechanical argument about what can and cannot be "computed". If you studied this in school twenty years ago or more, read this book for an update, especially the opening paper by Copeland and Shagrir. If you are approaching this for the first time, get the newest version here. And in either case stay tuned, in my opinion, because I think there is some motion in the academic understanding of the question, and this book opens as many issues as it closes. The paper by Aaronson on computational complexity is another that shows the frontier on this question, whether your concern is what can be computed in the real world, what might be computed in a larger theoretical sense, these being two different domains, and finally what effect, if any, the new-ish idea of "quantum computing" might have on the question (there is a separate paper on quantum computing as well). So update your CS degree or amaze your philosophical friends, read this book! These are original papers, by the way, Copeland has written widely about Turing and computation, and many of the other authors are very distinguished, including Putnam and Kripke, Martin Davis and Solomon Feferman - the list of authors is really enough to sell the book, if you are in the field. One note, several of the papers were apparently written using an outline format to facilitate creativity and output, and this sometime shows through as a degree of repetitiveness internal to individual papers. And a final note about the cover which lists the three editors' names over three pictures, and I hope everyone realizes the names do not match the pictures of Turing, Godel, and Church!