Book:Martin Davis/Computability and Unsolvability/Second Edition
Jump to navigation
Jump to search
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 1. Computable Functions
- Chapter 2. Operations on Computable Functions
- 1. Preliminary Lemmas
- 2. Composition and Minimalization
- Chapter 2. Operations on Computable Functions
- 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 3. Recursive Functions
- Chapter 4. Turing Machines Self-applied
- 1. Arithmetization of the Theory of Turing Machines
- 2. Computability and Recursiveness
- 3. A Universal Turing Machine
- Chapter 4. Turing Machines Self-applied
- 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
- Chapter 5. Unsolvable Decision Problems
- 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 6: Combinatorial Problems
- Chapter 7: Diophantine Equations
- 1. Hilbert's Tenth Problem
- 2. Arithmetical and Diophantine Predicates
- 3. Arithmetical Representation of Semicomputable Predicates
- Chapter 7: Diophantine Equations
- Chapter 8: Mathematical Logic
- 1. Logics
- 2. Incompleteness and Unsolvability Theorems for Logics
- 3. Arithmetical Logics
- 4. First-order Logics
- 5. Partial Propositional Calculi
- Chapter 8: Mathematical Logic
- 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 9. The Kleene Hierarchy
- 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 10. Computable Functionals
- 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
- Chapter 11. The Classification of Unsolvable Decision Problems
- 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:
- 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