Prologue.Prerequisites and notation 1
1 Sets 1
2 Functions 2
3 Relations and predicates 4
4 Logical notation 4
5 References 5
1 Computable functions 7
1 Algorithms，or effective procedures 7
2 The unlimited register machine 9
3 URM-computable functions 16
4 Decidable predicates and problems 22
5 Computability on other domains 23
2 Generating computable functions 25
1 The basic functions 25
2 Joining programs together 25
3 Substitution 29
4 Recursion 32
5 Minimalisation 42
3 Other approaches to computability：Church’s thesis 48
1 Other approaches to computability 48
2 Partial recursive functions（Godel-Kleene） 49
3 A digression：the primitive recursive functions 51
4 Turing-computability 52
5 Symbol manipulation systems of Post and Markov 57
6 Computability on domains other than N 65
7 Church’s thesis 67
4 Numbering computable functions 72
1 Numbering programs 72
2 Numbering computable functions 76
3 Discussion：the diagonal method 79
4 The s-m-n theorem 81
5 Universal programs 85
1 Universal functions and universal programs 85
2 Two applications of the universal program 90
3 Effective operations on computable functions 93
Appendix.Computability of the function σn 95
6 Decidability，undecidability and partial decidability 100
1 Undecidable problems in computability 101
2 The word problem for groups 106
3 Diophantine equations 107
4 Sturm’s algorithm 108
5 Mathematical logic 109
6 Partially decidable predicates 112
7 Recursive and recursively enumerable sets 121
1 Recursive sets 121
2 Recursively enumerable sets 123
3 Productive and creative sets 133
4 Simple sets 140
8 Arithmetic and Godel’s incompleteness theorem 143
1 Formal arithmetic 143
2 Incompleteness 146
3 Godel’s incompleteness theorem 149
4 Undecidability 155
9 Reducibility and degrees 157
1 Many-one reducibility 158
2 Degrees 161
3 m-complete r.e.sets 165
4 Relative computability 167
5 Turing reducibility and Turing degrees 174
10 Effective operations on partial functions 182
1 The second Recursion theorem 182
2 Effective operations on computable functions 189
3 The first Recursion theorem 192
4 An application to the semantics of programming languages 196
11 The second Recursion theorem 200
1 The second Recursion theorem 200
2 Discussion 207
3 Myhill’s theorem 210
12 Complexity of computation 212
1 Complexity and complexity measures 213
2 The Speed-up theorem 218
3 Complexity classes 223
4 The elementary functions 225
13 Further study 236
Bibliography 239
Index of notation 241
Subject Index 246