Industrial-Sized Deals TextBTS15 Shop Women's Handbags Learn more nav_sap_plcc_6M_fly_beacon Andra Day Fire TV Stick Off to College Essentials Find the Best Purina Pro Plan for Your Pet Shop Popular Services tmnt tmnt tmnt  Amazon Echo Starting at $99 Kindle Voyage Metal Gear Solid 5 Shop Back to School with Amazon Back to School with Amazon Outdoor Recreation Deal of the Day
Computability and Unsolvability and over one million other books are available for Amazon Kindle. Learn more

Computability and Unsolvability

7 customer reviews
ISBN-13: 978-0486614717
ISBN-10: 0486614719
Why is ISBN important?
This bar-code number lets you verify that you're getting exactly the right version or edition of a book. The 13-digit and 10-digit formats both work.
Scan an ISBN with your phone
Use the Amazon App to scan ISBNs and compare prices.
Have one to sell? Sell on Amazon
Buy used
Buy new
More Buying Choices
29 New from $8.00 40 Used from $1.93

InterDesign Brand Store Awareness Textbooks
$14.35 FREE Shipping on orders over $35. Only 19 left in stock (more on the way). Ships from and sold by Gift-wrap available.

Frequently Bought Together

Computability and Unsolvability + The Universal Computer: The Road from Leibniz to Turing + The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine
Price for all three: $59.11

Some of these items ship sooner than the others.

Buy the selected items together

Editorial Reviews

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


Best Books of the Month
Best Books of the Month
Want to know our Editors' picks for the best books of the month? Browse Best Books of the Month, featuring our favorite new books in more than a dozen categories.

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: 11.4 ounces (View shipping rates and policies)
  • Average Customer Review: 4.1 out of 5 stars  See all reviews (7 customer reviews)
  • Amazon Best Sellers Rank: #422,205 in Books (See Top 100 in Books)

Important Information

Example Ingredients

Example Directions

More About the Author

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

Customer Reviews

Most Helpful Customer Reviews

67 of 67 people found the following review helpful By Dennis E. Hamilton on September 7, 2000
Format: Paperback Verified Purchase
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.
Read more ›
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
24 of 24 people found the following review helpful By Jason T on June 27, 2005
Format: 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).
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
14 of 14 people found the following review helpful By anon2001 on July 3, 2001
Format: 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.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
4 of 4 people found the following review helpful By Man Kam Tam on May 24, 2008
Format: Paperback Verified Purchase
Martin Davis' "Computability and Un-solvability" has been used as the textbook of a graduate course offered by the author at the University of Illinois and a series of lectures at Bell Telephone Laboratories. The style of the book is mathematically formal. Its primary elements are definitions, lemmas, theorems, and proofs. For the readers, who are pursuing to understand more about the Hilbert's tenth problem, algorithm, and recursively enumerable sets, would find this book interesting. The first five chapters are about the general theory of computability, which is the concern of the existence of algorithm--purely mechanical procedures for solving various problems (no creative thought is needed while executing the procedure). First of all, the author introduces Turing machines (A Turing machine is a finite (nonempty) set of quadruples that contains no two quadruples whose first two symbols are the same). Then Davis introduces the definition of the computation of a Turing machine (a finite sequence of instantaneous description of a Turing machine), symbolic representation for numbers (5=SiSiSiSiSi), partially computable functions (the existence of a Turing machine whose resultant is equivalent to f(x1,x2,...,xn), computable functions (f(x1,x2,...,xn) is a total function), recursive functions (a function can be obtained by a finite number of applications of composition and minimalization of regular functions), and unsolvable decision problems (the non-existence of an algorithm for deciding the truth or falsity of whole class of statements). Chapter 6 to chapter 8 are about the applications of the general theory of computability, which includes the applications on combinatorial problems, Diophantine Equations (Hilbert's tenth problem is recursively unsolvable.Read more ›
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again

Set up an Amazon Giveaway

Amazon Giveaway allows you to run promotional giveaways in order to create buzz, reward your audience, and attract new followers and customers. Learn more
Computability and Unsolvability
This item: Computability and Unsolvability
Price: $14.35
Ships from and sold by