[可计算性理论]·杨东屏·科学社版

【可计算性理论】杨东屏科学.pdf1783816 中国科学院科学出版基金资助出版 可计算性理论 杨东屏李昂生著 斜学业版社前言 可计算性理论产生于对算法概念的数学研究,它是研究可计 算对象的计算复杂性和不可计算对象的结构的学科,是数理逻辑 的主要领域之一,也是计算机科学的理论基础.它的目的是研究 在本世纪30年代产生了几种等价的刻划算法本质的精确定 义,其中主要有入一可定义函数,递归函数,图灵可计算函数以 及由波斯特产生式系统定义的算法可产生集.随着人们寻求谓词 演算系统判定过程的失败,特别是著名的哥德尔不完全性定理的 出现,人们转向了对不可计算对象的研究,找到了许多不可计算 图灵归约及其它归约形式使人们可以对不可计算对象加以分 类,以研究不可计算对象的数学结构,在这过程中也产生了研究 算法和相对可计算性的工目录 可计算性理论基础知识 关于可计算性的基本概念 算法可计算函数的定义:无穷存储机器 递扫函数的可计算性 对程序配数,S定理,通用函数定理 对角线方法 遵归定理 可计算枚举集 可计算枚举集的基本性质 不可解问题 创造集,Post问题 对局方法,极大集,e一状态方法 用改选的Post思想对Post问题的解 能行禁集和可构造禁集 模引理和极限引理 有穷和无穷延伸方法 有穷延伸方法介绍 力道法介绍 Kucer
———— 文字由OCR识别(未校验)，可能存在错字；请以原始完整版为准。