可计算性理论PDF电子书下载

目录 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