Computability : Turing, Gödel, Church, and beyond / edited by Jack Copeland, Carl Posy, and Oron Shagrir.

Format:

Book

Contributor:

Copeland, B. Jack, 1950- editor.

Posy, Carl J., editor.

Shagrir, Oron, 1961- editor.

Language:

English

Subjects (All):

Computational complexity.

Mathematics--Philosophy.

Mathematics.

Physical Description:

1 online resource

Place of Publication:

Cambridge, Massachusetts : The MIT Press, [2013]

System Details:

text file

Summary:

"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."

Contents:

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

2 Computability and Arithmetic / Martin Davis Davis, Martin 35

3 About and around Computing over the Reals / Solomon Feferman Feferman, Solomon 55

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

5 Computability and Constructibility / Carl J. Posy Posy, Carl J. 105

6 After Gödel / Hilary Putnam Putnam, Hilary 141

7 The Open Texture of Computability / Stewart Shapiro Shapiro, Stewart 153

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

9 Interactive Computing and Relativized Computability / Robert Irving Soare Soare, Robert Irving 203

10 Why Philosophers Should Care about Computational Complexity / Scott Aaronson Aaronson, Scott 261

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

Notes:

OCLC-licensed vendor bibliographic record.

ISBN:

9781461931843

1461931843

0262312670

9780262312677

9780262312660

0262312662

1299688004

9781299688001

9780262312684

0262312689

OCLC:

849928726

Access Restriction:

Restricted for use by site license.