Computability Theory

Table of contents

1. Front Cover
2. Computability Theory
3. Copyright
4. Dedication
5. Table of Contents
6. Foreword
7. Preface
8. Chapter 1. The Computability Concept
   1. 1.1 The Informal Concept
   2. Exercises
   3. 1.2 Formalizations – An Overview (1/3)
   4. 1.2 Formalizations – An Overview (2/3)
   5. 1.2 Formalizations – An Overview (3/3)
   6. Exercises
9. Chapter 2. General Recursive Functions
   1. 2.1 Primitive Recursive Functions
   2. 2.2 Search Operation
   3. Exercises
10. Chapter 3. Programs and Machines
    1. 3.1 Register Machines
    2. 3.2 A Universal Program (1/3)
    3. 3.2 A Universal Program (2/3)
    4. 3.2 A Universal Program (3/3)
    5. Exercises
    6. 3.3 Register Machines Over Words
    7. Exercises
    8. 3.4 Binary Arithmetic
11. Chapter 4. Recursive Enumerability
    1. 4.1 Recursively Enumerable Relations (1/3)
    2. 4.1 Recursively Enumerable Relations (2/3)
    3. 4.1 Recursively Enumerable Relations (3/3)
    4. Exercises
    5. 4.2 Parameters (1/2)
    6. 4.2 Parameters (2/2)
    7. Exercises
12. Chapter 5. Connections to Logic
    1. 5.1 Arithmetical Hierarchy
    2. Exercises
    3. 5.2 Definability in Arithmetic
    4. 5.3 The Complexity of Truth
    5. Exercises
13. Chapter 6. Degrees of Unsolvability
    1. 6.1 Relative Computability
    2. 6.2 Equivalence Relations
    3. 6.3 Preordering Relations
    4. 6.4 Ordering Degrees
    5. Exercises
    6. 6.5 Structure of the Degrees
    7. Exercises
14. Chapter 7. Polynomial-Time Computability
    1. 7.1 Feasible Computability
    2. 7.2 P versus NP
    3. 7.3 Some Other Complexity Classes
    4. Exercises
15. Appendix 1. Mathspeak
16. Appendix 2. Countability
17. Appendix 3. Decadic Notation
18. References
19. Index (1/4)
20. Index (2/4)
21. Index (3/4)
22. Index (4/4)