引论 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
(二)URM 211
(三)算子算法 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
- 《可计算性理论》杨东屏,李昂生著 1999
- 《可计算性理论》 2222
- 《可计算性理论》张鸣华著 1984
- 《可计算性理论导引》李祥编著 1986
- 《可计算性理论》张宏裕编著 1989
- 《可计算性复杂性语言 理论计算机科学基础》(美)戴维斯(Davis,M.D.),(美)威尤克(Weyuker,E.J.)著;张立昂等译 1989
- 《弯斜桥计算理论与实用计算》邢志成著 1994
- 《船舶适航性的理论计算程序 第1部分 理论计算方法》交通部上海船舶运输科学研究所译 1973
- 《可计算性理论》莫绍揆,王元元著 1987
- 《计算理论基础 可计算性、复杂性和语言 英文版 第2版》(美)戴维斯(Davis,M.D.),(美)西加尔(Sigal,R.),(美)韦约克(Weyuker,E.J.)著 2009
- 《可计算性理论》张鸣华著 1984
- 《厄洛斯的“乱箭”》陈鸣华著 1991
- 《C程序设计实践教程》张鸣华主编;寿宇文,曾台盛副主编;孔令德主审 2014
- 《清代永嘉之学:纪念张振夔先生诞辰210周年》张鸣华编著 2008
- 《计算机文化基础》张冬梅,朱鸣华主编;贾长隆,张晓景,尹明,朱鸣华等编 1998
- 《大学计算机基础 第2版》朱鸣华著 2012
- 《Visual Basic程序设计项目教程》郭晓平,朱鸣华著 2014
- 《初中生阅读讲堂》孔有君丛书主编;陶益普主编;张鸣,王海洋副主编;韩世坤,张绍敏,杨春芳,谭吉勇,皮坤龙,申华强,牟南,张鸣,冉静,刘净编写 2006
- 《农药立体化学》王鸣华,宋宝安等编著 2016
- 《气藏工程》王鸣华主编 1997
- 《THE GOVERNMENT/PRESS CONNECTION PRESS OFFICERS AND THEIR OFFICES》STEPHEN HESS 1984
- 《PRESS》POLITICS & PUBLIC OPINION IN BIHAR 1912-1947 2010
- 《Press law》Robin Callender Smith. 1978
- 《SUING THE PRESS》RODNEY A.SMOLLA 1986
- 《THE PRESS AND AMERICA》 2222
- 《FREEDOM OF THE PRESS》ERIC BARENDT 2009
- 《FREEDOM OF THE PRESS》ROB EDELMAN 2006
- 《FREEDOM OF THE PRESS》DAVID L.GEBERT 2005
- 《Racism and the press》Teun A.van Dijk 2016
- 《Im spiegel per presse 1》Albert Schmitz 1983