【可计算性理论】杨东屏科学.pdf

1783816 中国科学院科学出版基金资助出版可计算性理论杨东屏李昂生著斜学业版社

前言可计算性理论产生于对算法概念的数学研究,它是研究可计算对象的计算复杂性和不可计算对象的结构的学科,是数理逻辑的主要领域之一,也是计算机科学的理论基础.它的目的是研究在本世纪30年代产生了几种等价的刻划算法本质的精确定义,其中主要有入一可定义函数,递归函数,图灵可计算函数以及由波斯特产生式系统定义的算法可产生集.随着人们寻求谓词演算系统判定过程的失败,特别是著名的哥德尔不完全性定理的出现,人们转向了对不可计算对象的研究,找到了许多不可计算图灵归约及其它归约形式使人们可以对不可计算对象加以分类,以研究不可计算对象的数学结构,在这过程中也产生了研究算法和相对可计算性的工

目录可计算性理论基础知识关于可计算性的基本概念算法可计算函数的定义:无穷存储机器递扫函数的可计算性对程序配数,S定理,通用函数定理对角线方法遵归定理可计算枚举集可计算枚举集的基本性质不可解问题创造集,Post问题对局方法,极大集,e一状态方法用改选的Post思想对Post问题的解能行禁集和可构造禁集模引理和极限引理有穷和无穷延伸方法有穷延伸方法介绍力道法介绍 Kucer