资源描述：
《丘奇_图灵论点与认知递归计算假说》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、丘奇——图灵论点与认知递归计算假说郝宁湘提起哥德尔不完备性定理,从事数学哲学、乃至一般哲学研究的人几乎没有不知晓的。然而与其齐名、并同样具有重大数学意义和哲学意义的丘奇图灵论点,知道它的人就少得多了。对它的数学意义和哲学意义给出深刻研究的人就更少了。对于这样一个重大的数学论点,长期以来未能引起数学哲学界的足够重视,这不能不说是件十分反常的事。本文试图对这一论点的数学意义,尤其是它的哲学意义作一认真地阐述,并因此希望能够引起有关人士对这一论点的关注。了他早在1934年就孕育过的一个论点,即著名的丘奇论点:每个能行地可计算的
2、函数都是一般递归的。也就在1936年,数学家图灵定义了另一类可计算函数——图灵可计算函数,并且提出了图灵观点:能行可计算的函数都是用图灵机可计算的函数。一年后,图灵进一步证明了图灵可计算函数与Κ可定义函数是等价的。当然也就和一般递归函数是等价的。于是这三类可计算函数实际上就是一种。这样一来,丘奇论点和图灵论点也就是一回事了。现统称为丘奇——图灵论点。至此,人们便把直观的能行可计算函数归结为一般递归函数了。从而对可计算性的实质有了清楚的认识。由上可见,丘奇——图灵论点是递归论中最重要的基本理论。它的提出在数学和计算机科学上
3、具有重大的理论意义与现实意义。正如我国著名数理专家莫绍揆教授所言:有了这个论点以后,我们就可以断定某些问题是不能能行地解决的。因为在这之前,我们只能设法去寻找相应的解决办法,找不到,我们也不能断定该问题不能计算,因为“找不到”不等于“不存在”,故只有在接受丘奇——图灵论点的基础上,当我们证明了“没有相应的一般递归函数”时,我们才能作出否定的回答。另外,有了此论点,我们还可以讨论可计算的复杂性,即对一般递归函数再作分类:由最简单的到较复杂的,最后到最复杂的。这种分类研究,不仅使我们对数论函数本身有更深入的了解,而且对自动机
4、,计算机的研究也大有补益〔1〕。对于计算机科学,丘奇——图灵论点的意义是很直接的,它明确刻画了计算机的本质或计算机的计算能力,确定了计算机只能计算一般递归函数。对于一般递归函数以外的函数,计算机是无法计算的。可以说,递归性是使用计算机的前提。因此,丘奇1丘奇——图灵论点的提出及其数学意义丘奇——图灵论点是递归论中最重要的基本结论。递归论又称可计算性理论,它是研究计算的一般性质的数学理论。其中心问题是;计算的本质是什么?哪些问题是可计算的?哪些问题是不可计算的?不可解的程度如何?这些问题经过长期的探索,终于在本世纪30年代
5、由于递归论的建立而得到了确切地解决。递归论的建立首先得益于哥德尔等人关于原始递归函数的提出。所谓原始递归函数是指由初始函数出发,经过有限次的代入与原始递归式而作出的函数。1934年哥德尔在他人的启示下,又提出了一般递归函数的概念。一般递归函数就是由初始函数出发,经过有穷次使用代入、原始递归式和Λ算子而作成的处处有定义的函数。同时,数学家丘奇、克林也提出了一类可计算的叫做Κ可定义的函数。事隔不久,丘奇、克林就分别证明了Κ可定义函数正好就是一般递归函数,即这两类可计算函数是等价的、用计算机计算。当然,这是从理论意义上来讲的。
6、从现实意义上讲,计算机还有一个现实可计算性的问题。不过这是由另一门学科——计算复杂性理论来研究的,这里我们就不多言了。需要说明的是,丘奇——图灵论点并不象哥德尔不完备性定理那样能给出一个严格的数学证明,因为这一论点原本就不是一条定理,其中包含了一个数学上意义不明确的概念——能行可计算。即一面是直观的日常概念,另一面是明确的数学概念(一般递归函数),要证明二者是一致的,这是不可能的。后来人们实际上是把这一论点看作是对直观概念能行可计算的数学定义。既然是对一个不明确的概念给以明确的定义,这就无所谓正确与否,因此用不着证明也无
7、法证明。那一方法,再假定该方法可以通过语言由一个正常的计算员不走样地传达给另一个正常的计算员。那么,存在一个有终止的Floop程序,它给出的答案恰好和这另一个计算员的方法所得到的答案一样。——这样一来,对于反驳标准形式的人来说,无疑是一大挑战,因为假设任何人都有一种共同的潜意识能力,并可以做出答案一样的超越意识过程的事情,这是会受到普遍怀疑的。(3)哈代形式:从本质上讲,所有的数学家都同构。——这就是说,所有的数学家都在用同一性质的方法思维。这还没有把每个数学家的数学潜力都等同于一般递归函数的潜力。要想做到这一点,必须设
8、法说明某个数学家的心智能力与递归函数的能力是一样的。这样,如果你相信丘奇——图灵论点的哈代形式,那就可以知道全体数学家都是如此了。(4)同构形式:在标准形式的基础上,进一步认为,那个计算员的心智过程与Floop程序在下述意义上同构:在某个层次上,计算机和大脑各自执行的那些步骤之间存在一个对应。——这一形式就是在断言:
