内容介绍
用户评论
全部咨询
内容简介
本书包括数理逻辑的递归论和形式语言论两部分内容.一至八章为递归论部分,详尽地研究了初等函数、原始递归函数、递归函数及各类算子,充分地讨论了Turing机与Turing可计算性概念.九、十两章为形式语言论部分,系统地介绍了各种形式语言及相应的语言识别器——各类自动机.作为递归论内容的深入,本书还概要地介绍了递归集、递归枚举集及递归度的概念;作为上述两部分内容的应用,第十一章还讨论了判定问题.
本书可作为高等院校计算机专业及有关专业的教材,也可供计算机科学和数学工作者阅读、参考.
目录
- 第一章 引论
1.1 集合
1.2 函数
1.3 谓词及其特征函数
1.4 能行可计算性
第二章 迭置及算子
2.1 本原函数
2.2 迭置
2.3 算子
第三章 初等函数集
3.1 三级初等函数集(EFS3)
3.2 Kalmar初等函数集(KEFS)
3.3 初等函数集(EFS)的性质
第四章 原始递归函数集
4.1 原始递归函数集(PRFS)及其与初等函数集的关系
4.2 可以化为原始递归函数的递归定义的函数
4.3 Ackermann函数与原始递归函数集的不足
第五章 递归函数集
5.1 一般递归函数集(GRFS)
5.2 部分函数与算子概念的推广
5.3 递归函数集(RFS)
5.4 可在有穷步骤内计算的函数集(FCFS),Church论题
5.5 递归定理
第六章 递归字函数集
6.1 ∑*上的原始递归函数集
6.2 ∑*上的递归函数集
6.3 字函数与数论函数
第七章 Turing机
7.1 基本Turing机及其形式定义
7.2 基本Turing机的加强与减弱
7.3 其他形式计算模型简介
第八章 Turing可计算函数集
8.1 Turing可计算函数集(TFS)
8.2 Turing可计算函数是可摹状函数,Turing论题
8.3 通用Turing机
8.4 递归字函数与Turing可计算函数
第九章 形式语言和自动机
9.1 文法、语言及语言的生成和识别
9.2 正规语言和有穷自动机
9.3 正规集合与正规表达式
9.4 上下文无关语言和下推自动机
9.5 上下文有关语言、递归语言、递归枚举语言
第十章 递归集、递归枚举集
10.1 递归集与递归枚举集
10.2 非递归集和非递归枚举集
10.3 创造集和单纯集
第十一章 判定问题
11.1 判定问题
11.2 关于Turing机的判定问题
11.3 Post问题和关于形式语言的判定问题
11.4 关于一阶谓词演算的判定问题
11.5 数学中的几个判定问题
参考文献