图书介绍
可计算性引论PDF|Epub|txt|kindle电子书版本网盘下载
- 王元元著 著
- 出版社： 南京：东南大学出版社
- ISBN：7810231030
- 出版时间：1990
- 标注页数：316页
- 文件大小：8MB
- 文件页数：329页
- 主题词：
PDF下载
下载说明
可计算性引论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.110
§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.223
1.3.1标准算法族26
1.3.2标准算法族的固有局限性26
§1.3标准算法族可计算性26
1.3.3标准算法族的计算能力30
练习1.336
第二章 程序算法族及其可计算性39
§2.1程序语言？39
练习2.144
§2.2 ？语言程序算法族可计算性45
2.2.1程序算法族可计算性的形式描述45
2.2.2初等函数与初等谓词是？程序可计算的48
2.2.3配对函数及程序编码57
2.2.4通用程序与标号计算程序63
练习2.271
第三章Turing机与Turing可计算性73
§3.1什么是Turing机73
3.1.1基本Turing机73
3.1.2基本Turing机实例80
3.1.3 Turing机的复合87
练习3.189
§3.2其他种类的Turing机91
3.2.1多道机以及其他的Turing机推广形式92
3.2.2单边机以及其他的Turing机限制形式95
练习3.299
§3.3通用Turing机100
3.3.1机和带的描述101
3.3.2通用机的构成104
练习3.3107
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.4119
§3.5Turing机族的计算功能及局限性120
3.5.1停机函数120
3.5.2标号计算函数122
3.5.3全性函数和等价性函数123
3.5.4递归定理125
练习3.5126
第四章原始递归函数129
§4.1初等函数集的不足129
练习4.1131
§4.2原始递归函数集132
4.2.1原始递归式132
4.2.2原始递归函数集135
练习4.2138
§4.3可以化为原始递归式的其他递归式140
4.3.1联立递归式140
4.3.2串值递归式143
练习4.3146
§4.4原始递归谓词148
§4.5 Loop程序与原始递归函数149
练习4.5155
§5.1 Ackerman函数156
5.1.1 Ackerman函数及基本性质156
第五章递归函数156
5.1.2 Ackerman函数的非原始递归性159
练习5.1163
§5.2μ-递归函数164
5.2.1μ-递归函数及其可计算性165
5.2.2 Ackerman函数的μ-递归性167
5.2.3 Turing可计算函数的μ-递归性173
练习5.2177
5.3.1一般递归式及递归函数集179
§5.3递归函数集179
5.3.2递归函数的可计算性181
5.3.3μ-递归函数的递归性182
练习5.3186
§5.4 Church-Turing论题186
5.4.1 Church-Turing论题186
5.4.2递归函数集是最小的标准算法族188
可计算函数集188
练习5.4191
第六章字函数及其可计算性193
§6.1∑*与∑*上的字函数193
6.1.1∑*上的原始递归字函数194
6.1.2∑*上的μ-递归字函数（递归字函数）198
练习6.1201
§6.2无零K进制与字的数表示201
6.2.1无零k进制与K进制的换算是203
原始递归可计算的203
6.2.2几个重要字函数的数论函数表示形式204
练习6.2206
§6.3∑*上字函数的可计算性讨论206
6.3.1程序语言？n206
6.3.2∑*上递归字函数的可计算性213
练习6.3213
第七章形式语言与自动机214
§7.1形式语言的生成与识别214
7.1.1形式语言的生成214
7.1.2形式语言的识别217
练习7.1219
§7.2正规语言和有穷自动机219
7.2.1 正规文法与正规语言219
7.2.2有穷自动机224
7.2.3有穷自动机与正规语言226
练习7.2232
§7.3正规语言的性质及正规表达式233
7.3.1正规语言的封闭特性233
7.3.2正规表达式238
7.3.3 Pumping引理及其应用241
练习7.3243
§7.4 上下文无关语言244
7.4.1上下文无关文法及上下文无关语言244
7.4.2文法树和导出树246
7.4.3 Chomsky标准形、Pumping引理及249
其他特性249
练习7.4254
§7.5下推自动机255
练习7.5259
§7.6形式语言的Chomsky分层259
7.6.1上下文有关语言259
7.6.2递归枚举语言263
7.6.3 Chomsky分层266
练习7.6267
第八章递归集、递归枚举集和判定问题268
§8.1递归集和递归枚举集268
8.1.1递归集和递归枚举集269
8.1.2递归关系和递归枚举关系279
练习8.1288
§8.2判定问题289
8.2.1判定问题求解的常用定理及方法292
8.2.2 Post对应问题297
8.2.3形式语言中的判定问题303
8.2.4其他判定问题简介307
练习8.2314
参考文献316