递归论:算法与随机性基础/逻辑与形而上学教科书系列

引言 **章 可计算性的基本知识 1.1 算法与可判定问题的例子 1.2 可计算性的**定义之图灵机版本 1.2.1 图灵机的描述 1.2.2 图灵可计算性 1.2.3 用有向转移图来表示图灵机 1.3 可计算性的**定义之递归函数版本 1.3.1 原始递归函数 1.3.2 原始递归函数的性质和编码 1.3.3 非原始递归函数 1.3.4 递归函数 1.3.5 部分递归函数 1.4 图灵可计算性与一般递归的等价性 1.4.1 从部分递归函数到图灵可计算函数 1.4.2 从图灵可计算函数到部分递归函数 1.4.3 丘奇论题 1.4.4 克林尼正规型定理 1.5 递归定理 1.5.1 s-m-n定理 1.5.2 递归定理 1.6 递归可枚举集 1.6.1 基本概念 1.6.2 ∑1-集 1.7 习题. 第二章 不可判定问题 2.1 不可判定问题 2.1.1 停机问题 2.1.2 指标集与莱斯定理 2.2 希尔伯特第十问题 2.3 马季亚谢维奇定理的证明 2.3.1 佩尔方程及其基本性质 2.3.2 指数函数是丢番图的 2.3.3 引理2.2.10的证明 2.3.4 引理2.2.9的证明 2.4 习题. 第三章 归约和度 3.1 多一归约和多一**集 3.1.1 多一归约的基本性质 3.1.2 一一等价与递归同构 3.1.3 创造集、产生集和1-** 3.1.4 单集 3.2 图灵归约和图灵度 3.2.1 相对可计算性 3.2.2 图灵归约和图灵度 3.2.3 图灵度上的算子 3.3 算术分层 3.3.1 算术分层的基本性质 3.3.2 分层定理 3.3.3 极限引理 3.3.4 ∑n-**集的例子(n=2，3) 3.4 习题 第四章 典型构造 4.1 尾节扩张与克林尼-波斯特定理 4.2 弗里德伯格-穆奇尼克定理 4.3 萨克斯分裂定理 4.4 习题 第五章 算法随机性的基本知识 5.1 0-1字符串与康托尔空间 5.1.1 随机性 5.1.2 0-1字符串与康托尔空间 5.2 基于不可压缩性的刻画 5.2.1 柯尔莫哥洛夫复杂度 5.2.2 无前束程序 5.2.3 1-随机与柴廷数 5.3 基于测试的刻画 5.3.1 马丁-洛夫随机性 5.3.2 与1-随机的等价性证明 5.3.3 通用马丁-洛夫测试 5.4 基于不可预测的刻画 5.5 习题 参考文献 索引 符号索引 术语索引 人名索引