COMPUTABILITY AN INTRODUCTION TO RECURSIVE FUNCTION THEORYPDF电子书下载

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