- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Dover Publications

Publication Date:

1982

Number of Pages:

288

Format:

Paperback

Price:

15.95

ISBN:

9780486614719

Category:

General

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

[Reviewed by , on ]

Art Gittleman

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

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

- Log in to post comments