- 作 者：
- 出 版 社：CAMBRIDGE UNIVERSITY PRESS
- 出版年份：1980
- ISBN：0521294657
- 标注页数：251 页
- PDF页数：262 页
请阅读订购服务说明与试读!
订购服务说明
1、本站所有的书默认都是PDF格式，该格式图书只能阅读和打印，不能再次编辑。
2、除分上下册或者多册的情况下，一般PDF页数一定要大于标注页数才建议下单购买。【本资源262 ≥251页】
图书下载及付费说明
1、所有的电子图书为PDF格式，支持电脑、手机、平板等各类电子设备阅读；可以任意拷贝文件到不同的阅读设备里进行阅读。
2、电子图书在提交订单后一般半小时内处理完成,最晚48小时内处理完成。(非工作日购买会延迟)
3、所有的电子图书都是原书直接扫描方式制作而成。
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