数理逻辑和算法理论 课件 袁相碗 第5--7章 丘奇-图灵论题的创立和计算机的出现----人工智能与算法 .pptx

数理逻辑和算法理论

——计算机科学与人工智能的数学基础

第5章丘奇-图灵论题的创立和计算机的出现1可计算性理论的兴起2丘奇-图灵论题的创立3图灵理想计算机的意义4计算机的出现

可计算性理论的兴起5.1

5.1可计算性理论的兴起哥德尔首次精确地给出原始递归函数的描述性定义之后，激起了人们在原始递归函数基础上进一步寻找与研究更为一般的可计算函数的热情，开始提出并猜测:原始递归函数是否穷尽了一切可计算的函数？结果很快发现了其答案是否定的。因为，令0,…,如表示原始递归函数的有穷序列,如果定义函数g(n)=如3)+1,则这个函数g直观上是可计算的，但它不出现在这一有穷序列之中，而且不是原始递归的。据此,可计算的但非原始递归的函数必是存在的。

5.1可计算性理论的兴起5.1.1阿克曼函数希尔伯特在1925年《论无穷》的演讲中，提出了是否有些递归式可以定义非原始递归函数呢？他的学生阿克曼在1928年的《论实数的希尔伯特构造》中解决了这个问题。

5.1可计算性理论的兴起5.1.2三种可计算函数模型的提出阿克曼函数的发现，虽然表明了可计算但非原始递归函数是存在的，但是除原始递归函数之外,是否还有其他可计算函数,以及如何给出相应的数学定义这一根本问题并未解决。于是，在1930年代研究可计算函数的热潮中，最早提出一般递归函数精确定义的是法国学者艾尔伯朗(J.Herbrand)o他在1931年的一封致哥德尔的信中提出了一般递归函数的定义。然后，哥德尔在1934年的讲演《论形式数学系统屮的不可判定命题》中,根据艾尔伯朗的提议，给出了一般递归函数的如下定义：如果屮表示一个未知函数,饥,…，如是已知函数，并且如果?和少各以最一般的方式彼此代入，而所得表达式的某些对是相等的，那么若所得的函数等式集合对屮有一个且仅仅有一个解，则寸是_个递归函数。

丘奇一图灵论题的创立5.2

5.2丘奇一图灵论题的创立1930年代发现的艾尔伯朗一哥德尔一克林的一般递归函数、丘奇的X可定义性函数和图灵的理想计算机及其可计算函数（奇妙的是克林和图灵都是丘奇的学生，丘奇的X可定义性函数在历史上是最早发现的），它们的动机和方法是截然不同的，但却相互独立地刻画了本质上等同的可计算性函数。不久，丘奇和克林证明了定义性函数和一般递归函数是等价的。接着,图灵在《论可计算数》的附录中，又证明了他的可计算函数和X可定义性函数也是等价的。亦即三人证明了：“一切算法可计算函数=一般递归函数-X可定义性函数=图灵可计算函数”（其中“表示等同，互推或当且仅当）

5.2丘奇一图灵论题的创立5.2.1丘奇一图灵论题是可计算性的理论基础丘奇一图灵论题的主要目的是为了将计算性函数及其算法刻画为既直观又清晰、既简要又有一定理论依据的“断言”（相当于通用的可计算性函数或算法）o其思想方法是:数学的公理化思想和自然科学的假设演绎法相结合，其思维过程如图5-2所示。

5.2丘奇一图灵论题的创立由此可见:丘奇一图灵论题相当于自然科学方法论中的经“由果到因”的数学思维过程概括出来的“科学定律”（数学假设），是可计算性理论的基本原理。其主要内涵是：①丘奇一图灵论题是源于数学实践中发现的三种不同的可计算性数学模型，通过非逻辑的归纳思维方式将其概括出来的。它不是数学定理，也非严格意义上的命题，但它在数学的实践检验中是正确而可靠的，像数学中的猜想,至今尚未发现任一反例。它的数学真理性是“问题求解”的算法可计算性的正确性与有效性，而非数学的公理化严密性与抽逻辑性。②丘奇一图灵论题从直观的初始函数或原始递归函数出发，通过“代入”和“替换”等计算规则，将可计算性对象在有限步骤内计算出来的数学理论;本质上则是立足于可信性、能行性、可构造性，以自然数论和潜无穷论为基础的算法化的数学思想方法。丘奇一图灵论题的是判定可计算性对象和不可计算性对象的一个严格的准则。

5.2丘奇一图灵论题的创立5.2.2丘奇一图灵论题本质上是“判定性台可计算性”一阶谓词演算的判定性问题源于20世纪20年代希尔伯特提出的用计算代替推理的谓词运算的判定性问题，丘奇和图灵在分别而独立地提出相互等价的X演算和可机算性函数的同时，分别而独立地提出并证明了一阶谓词演算的不可判定性定理，其中应用了“判定性O可计算性”的原理。

5.2丘奇一图灵论题的创立5.2.3丘奇一图灵论题的算法概念计算和算法是密不可分的、既有联系又有区别的两个不同概念，总体而言,任何计算都是在一定的算法支持下进行的。丘奇一图灵论题则首次将算法概念从计算概念中独立出来，将其作为数学的直接研究对象，并在此基础上革新了算法的概念，提升了算法的地位。

图灵理想计算机的意义5.3