# Book:Martin Davis/Computability and Unsolvability/Second Edition

Jump to navigation
Jump to search
## Martin Davis:

## Contents

## Martin Davis: *Computability and Unsolvability (2nd Edition)*

Published $\text {1982}$, **Dover Publications**

- ISBN 0-486-61471-9.

### Subject Matter

### Contents

**Preface to the Dover Edition**(1982)

**Preface to the First Edition**

**Glossary of Special Symbols**

**Introduction**

- 1. Heuristic Remarks on Decision Processes
- 2. Suggestions to the Reader
- 3. Notational Conventions

- PART 1: 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 Semicomputable Predicates
- 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 Iteration 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_2}^A$
- 7. Post's Representation Theorem

**Chapter 10. Computable Functionals**- 1. Functionals
- 2. Completely 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**

## Further Editions

## Source work progress

- 1982: Martin Davis:
*Computability and Unsolvability*(2nd ed.): Still to be started.

- Starting on Appendix $1$ with
*Next*:

- Starting on Appendix $1$ with

- 1982: Martin Davis:
*Computability and Unsolvability*(2nd ed.) ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Lemma $1$

- Check it, make sure nothing has been missed