可计算性引论pdf电子书版本下载

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

可计算性引论PDF格式电子书版下载

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

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

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

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

第一章抽象算法族与算法族可计算性 2

§1.1函数与算法 2

1.1.1函数 2

目录 2

1.1.2算法及其分类 5

1.1.3抽象算法族 7

练习1.1 10

§1.2抽象算法族的基本性质 12

1.2.1基础函数性质（BFP） 12

1.2.2复合函数性质（CFP） 12

1.2.3通用函数性质（UFP） 14

1.2.4判定函数性质（DFP） 17

1.2.5标号函数性质（IFP） 20

练习1.2 23

1.3.1标准算法族 26

1.3.2标准算法族的固有局限性 26

§1.3标准算法族可计算性 26

1.3.3标准算法族的计算能力 30

练习1.3 36

第二章 程序算法族及其可计算性 39

§2.1程序语言？ 39

练习2.1 44

§2.2 ？语言程序算法族可计算性 45

2.2.1程序算法族可计算性的形式描述 45

2.2.2初等函数与初等谓词是？程序可计算的 48

2.2.3配对函数及程序编码 57

2.2.4通用程序与标号计算程序 63

练习2.2 71

第三章Turing机与Turing可计算性 73

§3.1什么是Turing机 73

3.1.1基本Turing机 73

3.1.2基本Turing机实例 80

3.1.3 Turing机的复合 87

练习3.1 89

§3.2其他种类的Turing机 91

3.2.1多道机以及其他的Turing机推广形式 92

3.2.2单边机以及其他的Turing机限制形式 95

练习3.2 99

§3.3通用Turing机 100

3.3.1机和带的描述 101

3.3.2通用机的构成 104

练习3.3 107

3.4.1 Turing机及其可计算性的形式描述 108

§3.4 Turing机族及其可计算性 108

3.4.2 Turing机标号 112

3.4.3 Turing机族 114

3.4.4计算通用函数的Turing机 116

3.4.5计算标号函数的Turing机 118

练习3.4 119

§3.5Turing机族的计算功能及局限性 120

3.5.1停机函数 120

3.5.2标号计算函数 122

3.5.3全性函数和等价性函数 123

3.5.4递归定理 125

练习3.5 126

第四章原始递归函数 129

§4.1初等函数集的不足 129

练习4.1 131

§4.2原始递归函数集 132

4.2.1原始递归式 132

4.2.2原始递归函数集 135

练习4.2 138

§4.3可以化为原始递归式的其他递归式 140

4.3.1联立递归式 140

4.3.2串值递归式 143

练习4.3 146

§4.4原始递归谓词 148

§4.5 Loop程序与原始递归函数 149

练习4.5 155

§5.1 Ackerman函数 156

5.1.1 Ackerman函数及基本性质 156

第五章递归函数 156

5.1.2 Ackerman函数的非原始递归性 159

练习5.1 163

§5.2μ-递归函数 164

5.2.1μ-递归函数及其可计算性 165

5.2.2 Ackerman函数的μ-递归性 167

5.2.3 Turing可计算函数的μ-递归性 173

练习5.2 177

5.3.1一般递归式及递归函数集 179

§5.3递归函数集 179

5.3.2递归函数的可计算性 181

5.3.3μ-递归函数的递归性 182

练习5.3 186

§5.4 Church-Turing论题 186

5.4.1 Church-Turing论题 186

5.4.2递归函数集是最小的标准算法族 188

可计算函数集 188

练习5.4 191

第六章字函数及其可计算性 193

§6.1∑*与∑*上的字函数 193

6.1.1∑*上的原始递归字函数 194

6.1.2∑*上的μ-递归字函数（递归字函数） 198

练习6.1 201

§6.2无零K进制与字的数表示 201

6.2.1无零k进制与K进制的换算是 203

原始递归可计算的 203

6.2.2几个重要字函数的数论函数表示形式 204

练习6.2 206

§6.3∑*上字函数的可计算性讨论 206

6.3.1程序语言？n 206

6.3.2∑*上递归字函数的可计算性 213

练习6.3 213

第七章形式语言与自动机 214

§7.1形式语言的生成与识别 214

7.1.1形式语言的生成 214

7.1.2形式语言的识别 217

练习7.1 219

§7.2正规语言和有穷自动机 219

7.2.1 正规文法与正规语言 219

7.2.2有穷自动机 224

7.2.3有穷自动机与正规语言 226

练习7.2 232

§7.3正规语言的性质及正规表达式 233

7.3.1正规语言的封闭特性 233

7.3.2正规表达式 238

7.3.3 Pumping引理及其应用 241

练习7.3 243

§7.4 上下文无关语言 244

7.4.1上下文无关文法及上下文无关语言 244

7.4.2文法树和导出树 246

7.4.3 Chomsky标准形、Pumping引理及 249

其他特性 249

练习7.4 254

§7.5下推自动机 255

练习7.5 259

§7.6形式语言的Chomsky分层 259

7.6.1上下文有关语言 259

7.6.2递归枚举语言 263

7.6.3 Chomsky分层 266

练习7.6 267

第八章递归集、递归枚举集和判定问题 268

§8.1递归集和递归枚举集 268

8.1.1递归集和递归枚举集 269

8.1.2递归关系和递归枚举关系 279

练习8.1 288

§8.2判定问题 289

8.2.1判定问题求解的常用定理及方法 292

8.2.2 Post对应问题 297

8.2.3形式语言中的判定问题 303

8.2.4其他判定问题简介 307

练习8.2 314

参考文献 316