You are here

Computability and Unsolvability

Martin D. Davis
Publisher: 
Dover Publications
Publication Date: 
1982
Number of Pages: 
288
Format: 
Paperback
Price: 
15.95
ISBN: 
9780486614719
Category: 
General
BLL Rating: 

The Basic Library List Committee strongly recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Art Gittleman
, on
01/25/2011
]

This edition of the classic Computability and Unsolvability is a reprint of the 1958 edition with an added appendix. Computabiity, the theory of recursive functions, is a branch of mathematics that focuses on the existence of effective computational procedures. The foundation of the field by Alan Turing, Alonzo Church, and Emil Post occurred before the advent of electronic digital computers. In fact the computer in those days was a human. Matin Davis, who has made fundamental contributions to the field, was influenced by Post as an undergraduate at City College of New York, and received his Ph.D. under Church at Princeton. Davis also was one of the first computer programmers and he states, [1], that it influenced his presentation in this text.

Part 1, The General Theory of Computability, comprises five chapters. Chapter 1 uses Turing machines to define computable functions. A Turing machine is a simple model of computation which uses a potentially unbounded one-dimensional tape to store and retrieve symbols. The next chapter develops operations on computable functions so that one does need to refer directly to the underlying Turing machine and Chapter 3 applies these results to recursive functions. Chapter 5, Unsolvable Decision Problems, turns from computability to uncomputability.

Davis presents the first seven chapters with more details given for less experienced readers. Chapter 6 applies the theory of computability to the systems of Thue and Post, while Chapter 7 applies the theory to Diophantine equations and Hilbert’s Tenth Problem, which asked if an arbitrary polynomial equation with integer coefficients has an integer solution. Davis himself contributed a major piece of the negative result that the problem is unsolvable. Matiyasevic completed the last piece of the proof after this book was first published in 1958, but the added appendix is a Monthly article by Davis giving the complete proof. The last chapter of the second part on applications treats mathematical logic. Part 3 contains three chapters on advanced topics.

Davis’ approach using recursive functions, although algorithmically motivated, is well-suited to a mathematical audience. This book is a classic that introduced many to theoretical computer science. For those with more of a programming background, Davis is the coauthor of a more recent text, [2], that bases computability on a very simple programming language.


References:

[1] Jackson, Allyn (September 2007), “Interview with Martin Davis,” Notices of the American Mathematical Society (Providence, RI: American Mathematical Society) 55 (5): 560–571, 2008.

[2] Davis, Martin D., Sigal, Ron, Weyuker, Elaine J., Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Second Edition, Academic Press,1994.


Art Gittleman (artg@csulb.edu) is Professor of Computer Science at California State University Long Beach.


Preface to the Dover Edition;
Preface to the First Edition;
Glossary of special symbols
Introduction
1. Heuristic Remarks on Decision Problems
2. Suggestions to the Reader
3. Notational Conventions
Part I. The general theory of computability
Chapter 1.Computable Functions
1. Turing Machines
2. Computable Functions and Partially Computable functions
3. Some Examples
4. Relatively Computable functions
Chapter 2. Operations on Computable Functions
1. Preliminary Lemmas
2. Composition and Minimalization
Chapter 3. Recursive functions
1. Some Classes of Functions
2. Finite Sequences of Natural Numbers
3. Primitive Recursion
4. Primitive Recursive functions
5. Recursive Sets and Predicates
Chapter 4. Turing Machines Self-applied
1. Arithmetization of the Theory of Turing Machines
2. Computability and Recursiveness
3. A Universal Turing Machine
Chapter 5. Unsolvable Decision Problems
1. Semicomputable Predicates
2.Decision Problems
3.Properties of Semicomputable Predicates
4.Recursively enumerable Sets
5.Two Recursively enumerable Sets
6.A Set Which Is Not Recursively Enumerable
Part 2. Applications of the General Theory
Chapter 6. Combinatorial Problems
1. Combinatorial systems
2. Turing machines and Semi-Thue Systems
3. Thue Systems
4. The Word Problem for Semigroups
5. Normal Systems and Post Systems
Chapter 7. Diophantine Equations
1. Hilbert's Tenth Problem
2. Arithmetical and Diophantine Predicates
3. Arithmetical Representation of Semicomputable Predicates
Chapter 8. Mathematical Logic
1. Logics
2. Incompleteness and Unsolvability Theorems for Logics
3. Arithmetical Logics
4. First-order Logics
5. Partial Propositional Calculi
Part 3. Further Development of the General Theory
Chapter 9. The Kleene Hierarchy
1. The Interation Theorem
2. Some First Applications of the Iteration Theorem
3. Predicates, Sets, and Functions
4. Strong Reducibility
5. Some Classes of Predicates
6. A Representation Theorem for P subscript 2 superscript A
7. Post's Representation Theorem
Chapter 10. Computable Functionals
1. Functionals
2. Complete Computable functionals
3. Normal Form Theorems
4. Partially Computable and Computable Functionals
5. Functionals and Relative Recursiveness
6. Decision Problems
7. The Recursion Theorems
Chapter 11. The Classification of Unsolvable Decision Problems
1. Reducibility and the Kleene Hierarchy
2. Incomparability
3. Creative Sets and Simple Sets
4. Constructive Ordinals
5. Extensions of the Kleene Hierarchy
Appendix 1. Some Results from the Elementary Theory of Numbers
Appendix 2. Hilbert's Tenth Problem is Unsolvable
References; Index