Orcmid Writings

W000800: Précis of Computability and Unsolvability

Davis, Martin. Computability and Unsolvability. Dover (New York: 1958, 1973, 1982). ISBN 0-486-61471-9 pbk.

Last updated 2002-03-28-23:22 -0800 (pst)

An abbreviated version of this note appears as a review for the book on amazon.com.

The book is an introduction to the theory of computability and non-computability.  It uses the theory of recursive functions for entry to this topic and for exploring that theoretical territory on the borders 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 the establishment that there are absolutely unsolvable problems and undecidable questions, even ones that can be completely and precisely formulated using rigorous logic.  The result for computing is that there are some problems that are absolutely unsolvable by use of a computer program.  

This naturally leads one to wonder what problems are theoretically solvable by a computer program.  First, the idea of the Universal Turing Machine (UTM), recounted here, establishes the notion 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.  Basically, there is nothing that one UTM can compute that another can't.  

So, if we establish that the computer we have at hand is a universal computer, we at least 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.

The book also looks at the general limitation of universal computers.  There are functions that can't be computed (that is, for which there are no algorithms), and there are questions that can't be assured of an answer (as in proving a theorem in logic).  The formulation of this idea in the theory of computability employs the notion of recursively-enumerable sets that are not solvable -- there is no effective procedure determining whether a given object is a member of the set or not.  There is a large supply of such sets.  In practical terms, if a computational problem is equivalent to determining whether a particular item is a member of a recursively enumerable but not solvable set, you will be faced with the following situation.  The program may stop and confirm that the submitted item is a member of the set.  If the item is not a member of the set, the program will not stop.  Ever.  And if the program hasn't stopped yet, you don't know if that is because it will never stop or because you haven't ran it long enough.  And there is very little that can be done to improve this situation.

It would seem useful from this point to know when a problem of computation is one that is equivalent to the "easier case:" confirming that an  item is a member of a recursively enumerable set that is solvable.  There are abundant problem formulations that are guaranteed to be of this kind.  The task is then to find such a formulation for a practical problem in hand.  Then you'll have an assurance that there is an algorithm. Unfortunately, the algorithm may be too "hard" to compute, even though it is guaranteed to work.  You'll know that if you wait long enough you'll get the answer.  You simply might not be able to wait that long.  It may be that the universe won't even be around long enough to arrive at the answer.

 This book 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.

-- Dennis E. Hamilton
Renton, Washington
2000 August 9
revised: 2000 September 7

created 2000-09-07-09:56 -0700 (pdt) by orcmid
$$Author: Orcmid $
$$Date: 04-04-06 12:15 $
$$Revision: 14 $