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.