《可计算性理论》求取 ⇩

目录1

前言1

第一章 可计算性理论基础知识1

§1 关于可计算性的基本概念1

§2 算法可计算函数的定义：无穷存储机器11

§3 递归函数的可计算性16

§4 对程序配数，S？定理，通用函数定理23

§5 对角线方法32

§6 递归定理34

第二章 可计算枚举集37

§1 可计算枚举集的基本性质37

§2 不可解问题43

§3 创造集，Post问题46

§4 单纯集56

§5 超单纯集59

§6 对局方法，极大集，e-状态方法62

§7 用改进的Post思想对Post问题的解69

§8 能行禁集和可构造禁集80

§9 模引理和极限引理83

第三章 有穷和无穷延伸方法87

§1 有穷延伸方法介绍87

§2 力迫法介绍89

§3 Ku？era解决Post问题的方法98

§4 余无穷的无穷延伸方法………………………………103 §5 极小度108

第四章 有穷损害优先方法115

§1 引言115

§2 有穷损害优先方法介绍118

第五章 无穷损害优先方法143

§1 真步方法144

§2 树构造方法156

§3 弹球机方法172

第六章 有穷损害优先方法补充176

§1 非钻石格的嵌入与分杈度176

§2 同时区间允许184

第七章 计算复杂性理论195

§1 抽象计算复杂性195

§2 多项式计算复杂性205

第八章 及时单纯集和间段、余间段方法219

第九章 n-可计算枚举集和可计算逼近函数的图灵度237

§1 可计算枚举差集（d.c.e.）237

§2 n-可计算枚举集的定义和基本性质241

§3 n-可计算枚举度（n≥1）的结构研究259

§4 Dn（n≥1）中的可杯性定理267

第十章 树构造和O？-方法279

§1 树构造的基本思路283

§2 定理和需求：Lachlan非囿界定理288

§3 基本模块292

§4 构造299

§5 验证305

§6 相关结果和问题314

第十一章 囿界极小度定理318

§1 介绍318

§2 需求和基本模块322

§3 多个需求相结合时的基本模块330

§4 策略和优先树335

§5 构造339

§6 验证345

参考文献356