COMPUTABILITY AN INTRODUCTION TO RECURSIVE FUNCTION THEORYpdf电子书版本下载

点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用
种子下载[BT下载速度快] 温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页 直链下载[便捷但速度慢]   [在线试读本书]   [在线获取解压码]

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

下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。

建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！

（文件页数 要大于 标注页数，上中下等多册电子书除外）

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

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