《COMPUTABILITY AN INTRODUCTION TO RECURSIVE FUNCTION THEORY》

Prologue.Prerequisites and notation1

1 Sets1

2 Functions2

3 Relations and predicates4

4 Logical notation4

5 References5

1Computable functions7

1 Algorithms，or effective procedures7

2 The unlimited register machine9

3 URM-computable functions16

4 Decidable predicates and problems22

5 Computability on other domains23

2Generating computable functions25

1 The basic functions25

2 Joining programs together25

3 Substitution29

4 Recursion32

5 Minimalisation42

3Other approaches to computability：Church’s thesis48

1 Other approaches to computability48

2 Partial recursive functions（Godel-Kleene）49

3 A digression：the primitive recursive functions51

4 Turing-computability52

5 Symbol manipulation systems of Post and Markov57

6 Computability on domains other than N65

7 Church’s thesis67

4Numbering computable functions72

1 Numbering programs72

2 Numbering computable functions76

3 Discussion：the diagonal method79

4 The s-m-n theorem81

5Universal programs85

1 Universal functions and universal programs85

2 Two applications of the universal program90

3 Effective operations on computable functions93

Appendix.Computability of the function σn95

6Decidability，undecidability and partial decidability100

1 Undecidable problems in computability101

2 The word problem for groups106

3 Diophantine equations107

4 Sturm’s algorithm108

5 Mathematical logic109

6 Partially decidable predicates112

7Recursive and recursively enumerable sets121

1 Recursive sets121

2 Recursively enumerable sets123

3 Productive and creative sets133

4 Simple sets140

8Arithmetic and Godel’s incompleteness theorem143

1 Formal arithmetic143

2 Incompleteness146

3 Godel’s incompleteness theorem149

4 Undecidability155

9Reducibility and degrees157

1 Many-one reducibility158

2 Degrees161

3 m-complete r.e.sets165

4 Relative computability167

5 Turing reducibility and Turing degrees174

10Effective operations on partial functions182

1 The second Recursion theorem182

2 Effective operations on computable functions189

3 The first Recursion theorem192

4 An application to the semantics of programming languages196

11The second Recursion theorem200

1 The second Recursion theorem200

2 Discussion207

3 Myhill’s theorem210

12Complexity of computation212

1 Complexity and complexity measures213

2 The Speed-up theorem218

3 Complexity classes223

4 The elementary functions225

13 Further study236

Bibliography239

Index of notation241

Subject Index246