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

Portada
B. Jack Copeland, Carl J. Posy, Oron Shagrir
MIT Press, 30 de gen. 2015 - 376 pàgines
Computer 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.

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

 

Continguts

Computability and Arithmetic
35
About and around Computing over the Reals
55
The ChurchTuring Thesis as a Special Corollary
77
Computability and Constructibility
105
After Gödel
141
Gödels Philosophical Challenge to Turing
183
Interactive Computing and Relativized Computability
203
Why Philosophers Should Care about Computational Complexity
261
Is Quantum Mechanics Falsifiable? A Computational Perspective
329
About the Authors
351
Copyright

Altres edicions - Mostra-ho tot

Computability: Turing, Gödel, Church, and Beyond
B. Jack Copeland,Carl J. Posy,Oron Shagrir
Previsualització limitada - 2013
Computability: Turing, Gödel, Church, and Beyond
B. Jack Copeland,Carl J. Posy,Oron Shagrir
Previsualització limitada - 2013
Computability: Turing, Gödel, Church, and Beyond
B. Jack Copeland,Carl J. Posy,Oron Shagrir
Previsualització no disponible - 2015
Mostra-ho tot »

Frases i termes més freqüents

2-definable a-machine Alan Turing algorithm argument arithmetic axioms Brouwer called Church-Turing thesis Church's thesis classical complexity theory computability theory computable functions computational complexity computer science concept Copeland Davis defined definition Diophantine discussion Entscheidungsproblem equations equivalent example exponential fact Feferman finite number first-order logic formal system formula Gandy given Gödel graph Herbrand-Gödel Hilbert hypothesis induction infinite integers interactive proof intuitionistic Kleene lecture mathematical proof mathematician mean mechanical procedure Merlin mind natural numbers notion of computability NP-complete number theory objects oracle machine paper philosophy physical polynomial possible Post predicate primitive recursive problem proposition proved PSPACE quantum computing quantum mechanics qubits question random real numbers recursion theory recursive functions recursively enumerable relative computability result sequence set theory Shagrir Sieg Soare statement Symbolic Logic theorem tion Turing computable Turing machine Turing test Turing's analysis Undecidable unsolvable verifier Wang

Sobre l'autor (2015)

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.

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.

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.

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.

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.

Hilary Putnam was Walter Beverly Pearson Professor of Mathematical Logic at Harvard University.

Umesh Vazirani is Roger A. Strauch Professor in the Electrical Engineering and Computer Sciences Department at the University of California, Berkeley.

Informació bibliogràfica

TítolComputability: Turing, Gödel, Church, and Beyond
EditorsB. Jack Copeland, Carl J. Posy, Oron Shagrir
Edicióil·lustrada
EditorMIT Press, 2015
ISBN0262527480, 9780262527484
Nre. de pàgines376 pàgines
  
Exporta citacionsBiBTeX EndNote RefMan