Theory of Recursive Functions and Effective Computability

Front Matter......Page _005.djvu
Preface......Page _010.djvu
Contents......Page _014.djvu
Introduction: Prerequisites and Notation ......Page _018.djvu
1.1 The informal notion of algorithm ......Page 001.djvu
1.2 An example: the primitive recursive functions ......Page 005.djvu
1.3 Extensionality ......Page 009.djvu
1.4 Diagonalization ......Page 010.djvu
1.5 Formal characterization ......Page 011.djvu
1.6 The Basic Result ......Page 018.djvu
1.7 Church's Thesis ......Page 020.djvu
1.8 Godel numbers, universality, s-m-n theorem ......Page 021.djvu
1.9 The halting problem ......Page 024.djvu
1.10 Recursiveness ......Page 026.djvu
2.1 Further examples of recursive unsolvability ......Page 032.djvu
2.2 Unsolvable problems in other areas of mathematics......Page 035.djvu
2.3 Existence of certain partial recursive functions ......Page 036.djvu
2.4 Historical remarks ......Page 038.djvu
2.5 Discussion ......Page 039.djvu
2.6 Exercises ......Page 040.djvu
3.1 Goals of theory ......Page 046.djvu
3.3 Summary ......Page 048.djvu
4.1 lnvariance under a group ......Page 050.djvu
4.2 Recursive permutations ......Page 051.djvu
4.3 Recursive invariance......Page 052.djvu
4.5 Universal partial functions ......Page 053.djvu
4.6 Exercises......Page 055.djvu
5.1 Definitions......Page 057.djvu
5.2 Basic theorem......Page 060.djvu
5.3 Recursive and recursively enumerable relations; coding of k-tuples......Page 063.djvu
5.4 Projection theorems ......Page 066.djvu
5.5 Uniformity......Page 068.djvu
5.6 Finite sets......Page 069.djvu
5.7 Single-valuedness theorem......Page 071.djvu
5.8 Exercises......Page 073.djvu
6.1 General introduction ......Page 077.djvu
6.2 Exercises ......Page 079.djvu
7.1 One-one reducibility and many-one reducibility ......Page 080.djvu
7.2 Complete sets ......Page 082.djvu
7.3 Creative sets ......Page 084.djvu
7.4 One-one equivalence and recursive isomorphism ......Page 085.djvu
7.5 One-one completeness and many-one completeness ......Page 087.djvu
7.6 Cylinders ......Page 089.djvu
7.7 Productiveness ......Page 090.djvu
7.8 Logic ......Page 094.djvu
7.9 Exercises ......Page 099.djvu
8.1 Simple sets ......Page 105.djvu
8.2 Immune sets ......Page 107.djvu
8.3 Truth-table reducibility ......Page 109.djvu
8.4 Truth-table reducibility and many-one reducibility ......Page 112.djvu
8.5 Bounded truth-table reducibility ......Page 114.djvu
8.6 Structure of degrees ......Page 118.djvu
8. 7 Other recursively enumerable sets ......Page 120.djvu
8.8 Exercises ......Page 121.djvu
9.1 An example......Page 127.djvu
9.2 Relative recursiveness......Page 128.djvu
9.3 Relativized theory......Page 134.djvu
9.4 Turing reducibility......Page 137.djvu
9.5 Hypersimple sets; Dekker's theorem......Page 138.djvu
9.6 Turing reducibility and truth-table reducibility; Post's problem......Page 141.djvu
9.7 Enumeration reducibility......Page 145.djvu
9.8 Recursive operators......Page 148.djvu
9.9 Exercises......Page 154.djvu
10.1 Constructive approaches ......Page 161.djvu
10.2 Friedberg's solution ......Page 163.djvu
10.3 Further results and problems ......Page 167.djvu
10.4 Inseparable sets of any recursively enumerable degree ......Page 170.djvu
10.5 Theories of any recursively enumerable degree ......Page 171.djvu
10.6 Exercises ......Page 174.djvu
11.1 Introduction......Page 179.djvu
11.2 The recursion theorem......Page 180.djvu
11.3 Completeness of creative sets; completely productive sets......Page 183.djvu
11.4 Other applications and constructions......Page 185.djvu
11.5 Other forms of the recursion theorem......Page 192.djvu
11.6 Discussion......Page 199.djvu
11.7 Ordinal notations......Page 205.djvu
11.8 Constructive ordinals......Page 211.djvu
11.9 Exercises......Page 213.djvu
12.1 Lattices of sets ......Page 223.djvu
12.2 Decomposition ......Page 230.djvu
12.3 Cohesive sets ......Page 231.djvu
12.4 Maximal sets......Page 234.djvu
12.5 Subsets of maximal sets ......Page 237.djvu
12.6 Almost-finiteness properties ......Page 240.djvu
12.7 Exercises ......Page 246.djvu
13.1 The jump operation......Page 254.djvu
13.2 Special sets and degrees ......Page 262.djvu
13.3 Complete degrees; category and measure ......Page 265.djvu
13.4 Ordering of degrees ......Page 273.djvu
13.5 Minimal degrees ......Page 276.djvu
13.6 Partial degrees ......Page 279.djvu
13.7 The Medvedev lattice ......Page 282.djvu
13.8 Further results ......Page 289.djvu
13.9 Exercises ......Page 295.djvu
14.1 The hierarchy of sets ......Page 301.djvu
14.2 Normal forms ......Page 305.djvu
14.3 The Tarski-Kuratowski algorithm ......Page 307.djvu
14.4 Arithmetical representation ......Page 312.djvu
14.5 The strong hierarchy theorem ......Page 314.djvu
14.6 Degrees......Page 316.djvu
14.7 Applications to logic ......Page 318.djvu
14.8 Computing degrees of unsolvability ......Page 323.djvu
14.9 Exercises ......Page 331.djvu
15.1 The hierarchy of sets of sets ......Page 335.djvu
15.2 The hierarchy of sets of functions ......Page 346.djvu
15.3 Functionals ......Page 358.djvu
15.4 Exercises ......Page 367.djvu
16.1 The analytical hierarchy ......Page 373.djvu
16.2 Analytical representation; applications to logic ......Page 384.djvu
16.3 Finite-path trees ......Page 392.djvu
16.4 pi_1^1-sets and delta_1^1-sets ......Page 397.djvu
16.5 Generalized computability ......Page 402.djvu
16.6 Hyperdegrees and the hyperjump; sigma_2^1-sets and delta_2^1-sets ......Page 409.djvu
16.7 Basis results and implicit definability ......Page 418.djvu
16.8 The hyperarithmetical hierarchy ......Page 434.djvu
16.9 Exercises ......Page 445.djvu
Bibliography ......Page 459.djvu
Index of Notations ......Page 469.djvu
Subject Index ......Page 473.djvu