图书介绍
可计算性理论PDF|Epub|txt|kindle电子书版本网盘下载
- 张鸣华著 著
- 出版社： 北京：清华大学出版社
- ISBN：15235·98
- 出版时间：1984
- 标注页数：352页
- 文件大小：8MB
- 文件页数：364页
- 主题词：
PDF下载
下载说明
可计算性理论PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
引论1
(一)计算及可计算性1
(二)可计算性理论的发展3
(三)G？del 编号5
(四)本书内容简介10
第一章 递归函数13
第一节 原始递归函数15
1.1 原始递归函数16
(一)原始递归函数的定义16
(二)原始递归函数的运算20
1.2 原始递归谓词23
(一)原始递归谓词的定义23
(二)原始递归谓词的运算27
1.3 原始递归函数的其它定义29
(一)递归与迭代29
(二)一元原始递归函数34
(一)多步递归37
1.4 关于递归运算37
(二)多变元递归39
(三)联立递归41
(四)嵌套递归42
第二节 递归函数42
1.5 μ递归函数及递归谓词43
(一)μ递归函数的定义43
(二)递归谓词46
(三)G？del β函数48
(四)利用μ运算消去递归运算50
1.6 Ackermann 函数52
1.7 一般递归函数61
1.8 μ递归函数与一般递归函数67
第三节 递归可枚举集及递归集79
1.9 递归可枚举集80
(一)递归可枚举集80
(二)递归可枚举集的运算81
(三)递归函数的图形定理83
(一)原始递归集及递归集89
1.10 递归集89
(二)原始递归集及递归集的运算92
(三)递归集与递归可枚举集的关系93
1.11 递归可枚举谓词98
第四节 通用函数、递归定理103
1.12 Kleene 法式定理、通用函数104
(一)Kleene 法式定理105
(二)原始递归函数的通用函数107
(三)递归函数的通用函数、枚举定理111
1.13 s-m-n 定理、递归定理113
(一)递归函数的G？del 编号113
(二)S-m-n 定理118
(三)递归定理120
1.14 关于集合及谓词的若干性质122
(一)递归可枚举集的编号122
(二)谓词的 Kleene-Mostowski 分层126
1.15 递归字函数的算术化定义133
(一)字的算术化133
第五节 字函数133
(二)递归的字集及字函数136
1.16 递归字函数的直接定义138
(一)直接定义139
(二)直接定义等价于算术化定义143
第二章 Turing 机149
2.1 Turing 机的概念151
(一)Turing 机及其计算151
第一节 Turing 机的基本概念151
(二)Turing 机计算及符号变换157
(三)Turing 机的四元组指令159
2.2 Turing 机的标准化及组合162
(一)Turing 机的标准化162
(二)Turing 机的组合167
第二节 Turing 可计算函数168
2.3 递归函数是 Turing 可计算函数168
2.4 Turing 可计算函数是递归函数180
2.5 通用 Turing 机186
(一)通用 Turing 机186
第三节 通用 Turing 机186
(二)Turing 机的枚举192
2.6 关于小的通用 Turing 机192
第四节 Turing 机的变形197
2.7 多头多带 Turing 机198
(一)半无限带的 Turing 机199
(二)多读写头的 Turing 机201
(三)多带 Turing 机204
(一)W 机205
2.8 W 机、URM 及算子算法205
(二)URM211
(三)算子算法216
2.9 Minsky 机218
(一)Minsky 机与算子算法218
(二)三带 Minsky 机220
(三)二带 Minsky 机223
第五节 递归函数的子类227
(一)Grzegorczyk 层次228
2.10 原始递归函数的层次228
(二)初等函数231
2.11 初等函数的层次233
(一)基本概念233
(二)函数类？237
(三)函数类？242
2.12 可计算函数的复杂性类243
(一)计算复杂性的尺度244
(二)复杂性类248
(三)分层问题250
第三章 Post 系统255
第一节 半 Thue 系统及 Thue 系统256
3.1 半 Thue 系统及 Thue 系统256
(一)半 Thue 系统256
(二)Thue 系统259
3.2 半 Thue 系统与可计算性260
(一)Turing 机可计算是半 Thue 系统可计算260
(二)半 Thue 系统的字集合与递归可枚举集262
第二节 Post 系统264
3.3 正规系统265
3.4 tag 系统268
3.5 标准系统276
(一)标准系统276
(二)标准系统与正规系统278
第三节 马尔科夫算法288
3.6 马尔科夫算法289
(一)马尔科夫算法的基本概念289
(二)马尔科夫算法的组合292
3.7 马尔科夫算法与递归函数299
第四章 判定问题305
第一节 基本概念306
4.1 判定问题的基本概念306
(一)历史背景306
(二)基本定义308
(三)基本方法310
4.2 非递归函数的例子310
4.3 Turing 机的停机问题314
(一)停机问题314
第二节 若干递归不可解的判定问题314
(二)Turing 机的完全性及等价性315
4.4 字问题及 Post 对应问题319
(一)半 Thue 系统及正规系统的字问题319
(二)Thue 系统的字问题321
(三)Post 对应问题322
第三节 不可解级326
4.5 相对递归及 Turing 级327
(一)相对递归327
(二)带有解算装置的 Turing 机329
(三)Turing 归约及 Turing 级330
4.6 (m，1)级及(1，1)级333
(一)(m，1)归约及(m，1)级333
(二)(1，1)归约及(1，1)级337
4.7 递归可枚举级338
(一)创造集及生产集338
(二)完全集342
(三)简单集及禁集344
参考文献348