Computability and Unsolvability (Mcgraw-Hill Series in Information Processing and Computers.)

Rating:
Summary: Another Dover classic reprint at a bargain price.
Review: 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.

Rating:
Summary: Another Dover classic reprint at a bargain price.
Review: 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.

Rating:
Summary: Mapping the Outer Limits of Computation
Review: 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.

Rating:
Summary: Mapping the Outer Limits of Computation
Review: 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.