Computability and Unsolvability [Paperback]

Martin Davis (Author)

Book Description

ISBN-10: 0486614719 | ISBN-13: 978-0486614717 | Publication Date: December 1, 1985

Classic text considers general theory of computability, computable functions, operations on computable functions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.

Product Details

• Paperback: 248 pages
• Publisher: Dover Publications (December 1, 1985)
• Language: English
• ISBN-10: 0486614719
• ISBN-13: 978-0486614717
• Product Dimensions: 8.5 x 5.4 x 0.6 inches
• Shipping Weight: 6.4 ounces (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (6 customer reviews)
• Amazon Best Sellers Rank: #457,829 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

62 of 62 people found the following review helpful:

4.0 out of 5 stars Mapping the Outer Limits of Computation, September 7, 2000

By 

Dennis E. Hamilton "orcmid" (Seattle, WA United States) - See all my reviews
(REAL NAME)   

This review is from: Computability and Unsolvability (Paperback)

The book introduces the theory of computability and non-computability to the mathematically-comfortable. The theory of recursive functions provides entry to that theoretical territory at the limits of what is computable and what is solvable. The theory is relevant to important philosophical questions and also in the theory of computing and what is possible (and never possible) by use of computing machines.

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.

21 of 21 people found the following review helpful:

5.0 out of 5 stars A great book on recusive function theory., June 27, 2005

By 

Jason T (Canada) - See all my reviews

This review is from: Computability and Unsolvability (Paperback)

This is a reprint of Davis's 1958 book, and at the dover price, it's a great bargain. The book is for math students and introduces the basics of recursive function theory (the table of contents gives a good impression of what's included- here the 'iteration theorem' means the smn theorem). Note it doesn't cover a lot of the more computer-science oriented topics that are standard for undergraduate books titled 'computability theory', such as regular automata, grammars & parsing, complexity classes and NP-completeness (if you want this material I recommend Lewis & Papadimitriou). I found it very well-written and it gets a lot done in under 200 pages. The theorems fit together like precision-machined parts- Davis obviously put a lot of care into his choice of material and presentation, achieving a maximum of efficiency and cohesion. The style is rigorous throughout (for instance, I enjoyed his tight handling of Turing machines by using a series of well-chosen lemmas- its perhaps the first time I've really seen this done right). The last three chapters are noticeably steeper and not as well done- its too bad there was never a second edition. In the appendix is a complete proof of the unsolvability of Hilbert's 10th problem. There are no exercises.

This would be a good preparation for Hartley Rogers book- Davis provides a solid foundation of the material taken as the starting point in Rogers (and then some), and his rigorous style should give you the confidence and familiarity with working things out in full detail before you allow yourself the looser style of Rogers "by Church's Thesis" approach. Of course, I read Rogers first so maybe I'm wrong. I also prefer the way Davis handles relativized computation (he uses oracle machines and all theorems are relativized right from the beginning).

14 of 14 people found the following review helpful:

5.0 out of 5 stars Another Dover classic reprint at a bargain price., July 3, 2001

By 

anon2001 "anon2001" (Kinross, Western Australia AUSTRALIA) - See all my reviews

This review is from: Computability and Unsolvability (Paperback)

Another classic reprint rom Dover at a reasonable price. Martin Davis is a very well-known worker in the area of logical foundations of computing. This book covers much fascinating material and provides answers to some deep questions relating to the limits of computations. The material can be a little dry but worth the effort. The book is worth the price for the appendix which is a reprint of an article by Davis on the proof of the unsolvability of Hilbert's Tenth Problem.