What do you think?
Rate this book
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. 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
376 pages, Unknown Binding
First published January 1, 2013
7 people are currently reading
186 people want to read
About the author
B. Jack Copeland
13 books12 followersBrian Jack Copeland is Professor of Philosophy at the University of Canterbury, Christchurch, New Zealand and author of books on computing pioneer Alan Turing.
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 3 of 3 reviews
June 15, 2020
A collection of papers without even the common courtesy of some extended commentaries, and only the briefest of introductions. Which I consider to be misleading.
Many of them are way too specialized and technical for anyone not already in the relevant niche - for that paper!! So a bit of a disappointment in that respect. I certainly couldn't follow them. They belong in (and are in) journals and it is either dishonest or inept to include them in a seemingly more general, more accessible book that interested readers are going to pay actual money for!!
However,
despite that hiccup the topic is of immense importance and many of the papers are well written, extremely interesting and historically illuminating. What is this general notion of 'computable' defined by Turing and others? What about non-computability, incompleteness (Godel) and undecidability (Church and Turing)? What are the implications for what can and can't ultimately be done by mind or machine? Is there a fundamental difference between these two? Or are many of the proponents of this just fooling themselves. There is much clarification on what Turing and Godel thought about these issues. They both thought that minds were more powerful problem solvers than machines (automata ). Turing emphasized the mind's essential creativity though was not unaware of machine creativity. He would presumably would have been astounded by modern AIs and machine learning systems. Godel emphasized the role of ever larger infinity axioms. Though why machines ( AIs, MLs) cant discover and deal with these just as effectively as we do was never made clear. The best essay by far is Scott Aaronson's on the relevance of computational complexity to many of these issues. Forget Quantum Computers, a CTC Computer (quantum or classical) will be able to 'efficiently' solve all problems in the PSpace complexity class!! Which is why he is convinced no such thing is possible. Pessimist!!
So overall its worth a browse but you need some reasonable background even for the simpler ones. And just skip over the hard ones.
Many of them are way too specialized and technical for anyone not already in the relevant niche - for that paper!! So a bit of a disappointment in that respect. I certainly couldn't follow them. They belong in (and are in) journals and it is either dishonest or inept to include them in a seemingly more general, more accessible book that interested readers are going to pay actual money for!!
However,
despite that hiccup the topic is of immense importance and many of the papers are well written, extremely interesting and historically illuminating. What is this general notion of 'computable' defined by Turing and others? What about non-computability, incompleteness (Godel) and undecidability (Church and Turing)? What are the implications for what can and can't ultimately be done by mind or machine? Is there a fundamental difference between these two? Or are many of the proponents of this just fooling themselves. There is much clarification on what Turing and Godel thought about these issues. They both thought that minds were more powerful problem solvers than machines (automata ). Turing emphasized the mind's essential creativity though was not unaware of machine creativity. He would presumably would have been astounded by modern AIs and machine learning systems. Godel emphasized the role of ever larger infinity axioms. Though why machines ( AIs, MLs) cant discover and deal with these just as effectively as we do was never made clear. The best essay by far is Scott Aaronson's on the relevance of computational complexity to many of these issues. Forget Quantum Computers, a CTC Computer (quantum or classical) will be able to 'efficiently' solve all problems in the PSpace complexity class!! Which is why he is convinced no such thing is possible. Pessimist!!
So overall its worth a browse but you need some reasonable background even for the simpler ones. And just skip over the hard ones.
October 31, 2018
A nice collection of articles on
July 5, 2023
Good compilation of work related with complexity.
Displaying 1 - 3 of 3 reviews