丘奇_图灵论点与认知递归计算假说.doc

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