Computability and Unsolvability
Use the Amazon App to scan ISBNs and compare prices.
Order within 12 hrs and 22 mins Details
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
Frequently bought together
About the Author
Martin Davis: Computer Science Pioneer
Dover's publishing relationship with Martin Davis, now retired from NYU and living in Berkeley, goes back to 1985 when we reprinted his classic 1958 book Computability and Unsolvability, widely regarded as a classic of theoretical computer science. A graduate of New York's City College, Davis received his PhD from Princeton in the late 1940s and became one of the first computer programmers in the early 1950s, working on the ORDVAC computer at The University of Illinois. He later settled at NYU where he helped found the Computer Science Department.
Not many books from the infancy of computer science are still alive after several decades, but Computability and Unsolvability is the exception. And The Undecidable is an anthology of fundamental papers on undecidability and unsolvability by major figures in the field including Godel, Church, Turing, Kleene, and Post.
Critical Acclaim for Computability and Unsolvability:
"This book gives an expository account of the theory of recursive functions and some of its applications to logic and mathematics. It is well written and can be recommended to anyone interested in this field. No specific knowledge of other parts of mathematics is presupposed. Though there are no exercises, the book is suitable for use as a textbook." — J. C. E. Dekker, Bulletin of the American Mathematical Society, 1959
Critical Acclaim for The Undecidable:
"A valuable collection both for original source material as well as historical formulations of current problems." — The Review of Metaphysics
"Much more than a mere collection of papers . . . a valuable addition to the literature." — Mathematics of Computation
- Publisher : Dover Publications (December 1, 1985)
- Language : English
- Paperback : 248 pages
- ISBN-10 : 0486614719
- ISBN-13 : 978-0486614717
- Item Weight : 10.6 ounces
- Dimensions : 5.44 x 0.57 x 8.46 inches
- Best Sellers Rank: #205,678 in Books (See Top 100 in Books)
- Customer Reviews:
Top reviews from the United States
There was a problem filtering reviews right now. Please try again later.
The result for philosophy is establishment of absolutely unsolvable problems and undecidable questions, even ones that can be completely and precisely formulated using rigorous logic. The result for computing is problems that are absolutely unsolvable by use of a computer program.
So what problems are theoretically solvable by a computer program? First, the Universal Turing Machine (UTM) is presented along with the famous demonstration that all universal computers are equivalent in the sense that any one of them can be made to simulate any of the others, using a suitable representation.
So, if we establish that the computer we have at hand is a universal computer, we can be confident that, in principle, anything that any computer can compute, this one can also.
The book goes on to address what even universal computers can't do. The most well-known result in computer-science circles is the unsolvability of the halting problem. That is, if the computer is powerful enough to be universal, one of its limitations is the impossibility of an algorithm that will determine whether any program for that machine will always terminate for all inputs. It is as if the price of universality is the inevitability of programs that won't finish, along with having no absolute way of telling whether arbitrary given programs will finish or not.
Davis maps the boundary between the impossible (the unsolvable) and the merely inhumanly difficult (the computable). With that foundation, one can move on to other work that introduces what has been learned about computational complexity and how to apply the analysis of algorithms to finding computational methods that are practical and no more complex than absolutely necessary.
The book is an essential part of my library because of its availability and its standing as a fundamental reference in the theory of computation. Church's Thesis and the development of effective computability via the lambda-calculus and combinatory logic is neglected more than suits me. Available supplementary references are needed for access to those alternative formulations that promise to bear directly on having operational, practical computer systems that function at the limits of computability.
However, I think that what it lacks are less formal comments to accompany the heavy formalised theorems. I often found myself asking 'But what does this mean?' after reading the proof of a theorem. While it does give some plain English explanations, I would have liked it to have more. I cannot take away any stars because of this, due to the fact that it is 'advertised' as a technical book, not a philosophical one.