Computability and Unsolvability (Mcgraw-Hill Series in Information Processing and Computers.) | 
 enlarge | Author: Martin Davis
Publisher: Dover Publications
Category: Book
List Price: $15.95
Buy New: $4.79
You Save: $11.16 (70%)
New (20) Used (18) from $4.08
Rating:  4 reviews
Sales Rank: 174699
Media: Paperback
Edition: New Ed
Pages: 248
Number Of Items: 1
Shipping Weight (lbs): 0.4
Dimensions (in): 8.5 x 5.5 x 0.7
ISBN: 0486614719
Dewey Decimal Number: 511.3
EAN: 9780486614717
Publication Date: December 1, 1985
Availability: Usually ships in 1-2 business days
Shipping: Expedited shipping available
Shipping: International shipping available
Condition: Brand New! Buy with confidence - your satisfaction is guaranteed at B-Logistics!
| |
| Similar Items:
|
| Editorial Reviews:
Product Description
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.
|
| Customer Reviews:
Another Dover classic reprint at a bargain price. July 3, 2001
anon2001 (Kinross, Western Australia AUSTRALIA)
12 out of 12 found this review helpful
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.
A great book on recusive function theory. June 27, 2005
Jason T (Canada)
14 out of 14 found this review helpful
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).
Mathematics and Computer Science May 25, 2008
Man Kam Tam (Calexico, CA USA)
1 out of 1 found this review helpful
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.), and mathematical logic (incompleteness and un-solvability theorems for logics). A glimpse of the "decisive limitation on the power of logics" (Godel's famous incompleteness theorem) is also presented. Chapter 9 to chapter 11 is about the further development of the general theory of computability. There are two appendixes related to mathematics. The first appendix is the fundamental facts of the elementary number theory. The second appendix is the author's paper "Hilbert's Tenth problem is unsolvable." The readers would need a clear concept on computable functions, effectively calculable functions, and algorithm to understand both the general theory of computability and the Hilbert's Tenth problem.
 Mapping the Outer Limits of Computation September 7, 2000
Dennis E. Hamilton (Seattle, WA United States)
59 out of 59 found this review helpful
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.
|
|
|
