vi Contents
§3.6. The Church-Turing Thesis 65
§3.7. Other Definitions of Computability 66
Chapter 4. Working with Computable Functions 77
§4.1. The Halting Problem 77
§4.2. The “Three Contradictions” 78
§4.3. Parametrization 79
§4.4. The Recursion Theorem 81
§4.5. Unsolvability 85
Chapter 5. Computing and Enumerating Sets 95
§5.1. Dovetailing 95
§5.2. Computing and Enumerating 96
§5.3. Aside: Enumeration and Incompleteness 102
§5.4. Enumerating Noncomputable Sets 105
Chapter 6. Turing Reduction and Post’s Problem 109
§6.1. Reducibility of Sets 109
§6.2. Finite Injury Priority Arguments 115
§6.3. Notes on Approximation 124
Chapter 7. Two Hierarchies of Sets 127
§7.1. Turing Degrees and Relativization 127
§7.2. The Arithmetical Hierarchy 131
§7.3. Index Sets and Arithmetical Completeness 135
Chapter 8. Further Tools and Results 139
§8.1. The Limit Lemma 139
§8.2. The Arslanov Completeness Criterion 142
§8.3. E Modulo Finite Difference 145
Chapter 9. Areas of Research 149
§9.1. Computably Enumerable Sets and Degrees 149
§9.2. Randomness 155
§9.3. Some Model Theory 169
Previous Page Next Page