丘奇－图灵论点与人类认知能力和极限
郝宁湘
（山西大学科哲中心，湛江师范学院政法系）
The Church-Turing Thesis and Human Cognitive Ability and Limit
Hao Ningxiang
Center for Philosophy of Science and Technology, Shanxi University
Department of Politics and Law, Zhanjiang Normal College
摘要：本文以丘奇—图灵论点为背景，论述了人类认知能力及其极限，提出了人类认知的可数无限性，和人的认知能力是受递归规律限制的观点。最后，为计算主义认知观提供了一定的计算神经科学的证据。
关键词：丘奇—图灵论点 人类认知能力及其极限 可数无限性 递归规则
Abstract：Based on the background of Church-Turing thesis, this paper discusses mankind's cognitive ability and limit, points out that mankind's cognition has countable infiniteness property and it’s ability is restricted by recursive rule. At last, the author proposes certain proof of computational neuroscience for algorithmist cognition theory.
Key words: Church-Turing thesis, mankind's cognitive ability and limit, countable infiniteness, recursive rule
一、引言
正如美国科学家马尔所言：“计算”的概念对于认知科学的基本重要性，就像“能量”和“质量”的概念对于物理学的基本重要性一样，就像“蛋白质”和“基因”的概念对于生物学的基本重要性一样。没有计算的概念就没有把智力的研究建立在现代科学基础之上的认知科学。马尔曾举例说明，要理解人类的知觉如果仅仅研究人类的神经细胞，就像要理解鸟的飞翔只研究鸟的羽毛一样，是不够的。要理解鸟的飞翔我们必须理解空气动力学；只有理解了空气动力学才能真正理解羽毛的结构和翅膀的形状。计算理论的分析对理解认知和智力过程的重要性，就像空气动力学对理解飞行的重要性一样。无论人脑和计算机在硬件层次乃至在软件层次可能是如何的不同，但是在计算理论的层次，它们都具有产生、操作和处理抽象符号的能力；作为信息处理的系统，无论是人脑还是计算机都是操作处理符号的形式系统。这种符号的操作过程就是图灵机意义下的“计算”。
87
⑴
丘奇－图灵论点是可计算性理论中最重要的基本结论。它的确立，回答了计算的本质是什么、哪些问题是可计算的、哪些问题是不可计算的等这些人类曾长期探索过的具有重大哲学意义的问题。其意义不仅体现在数学、逻辑学、计算机科学等方面，而且也体现在大脑与认知的哲学方面。如美国学者霍夫斯塔特就曾指出：“丘奇－图灵论点确实是数学、大脑及思维的哲学中最重要的概念之一”。为此，霍夫斯塔特（中文名：侯世达）在其著名巨作《哥德尔、艾舍尔、巴赫》的第17章中，对丘奇－图灵论点专门作了颇有深度的哲学研究，给出了丘奇－图灵论点十种不同的表述形式，它们都是很有意味和深度的。如丘奇－图灵论点的“人工智能形式”：人的任何心智过程都可以用一个计算机程序来模拟，而该程序的基础语言与FlooP（可理解为“一种能且仅能计算一般递归函数的程序”）一样强。这实际上是把丘奇－图灵论点改换成了人工智能论点：随着智能机的发展，它的基础机制会逐渐收敛于人类智能的基础机制。换句话说，一切智能都只是同一主题——计算的各种变奏。⑵
丘奇－图灵论点的人工智能形式是霍夫斯塔特所做的最后一个哲学拓展，也是其之所以给出这一系列哲学拓展的最终目的。我们认为，其拓展在一定意义上是可以接受的，它们为人们理解人类认知之本质提供了有意义的哲学观念。西方认知科学领域中占中心地位的计算主义学派，最集中地体现了这种哲学思想。我们相信，计算主义这条路是颇有前途的。这里我们并不是说计算主义是唯一可行的途径。我们相信并认为，在探索人类认知、意识和大脑之谜的过程中，各种不同的观点和理论会有着相互补充、相互促进的积极作用。霍夫斯塔特是一位对人工智能持乐观、积极态度的学者。相信丘奇－图灵论点为人工智能的最终实现奠定了牢固的基础。不过我们与霍夫斯塔特有所不同：他所关注的问题是，能不能制造一台像人一样思维或认知的计算机。对此，他的答案是肯定的。而我们的兴趣或所关注的问题是，一种怎样的理论才能有效地解释人的认知。我们认为，丘奇－图灵论点对于人们创建一种有效的认知理论是极富启示性的，尤其对考察人类的认知能力和极限更有着最直接的指导意义。
二、不可解性与人类认知的可数无限性
我们认为，丘奇－图灵论点以及可计算性理论乃至整个数理逻辑科学，在哲学上，尤其在认知哲学上均有着极其重大的意义。可以说，它们在最抽象的意义上有效地解释了人类认知的诸多现象和特征。特别是对人的认知能力和极限的认识有非常重要的启示。
现实中，许多人似乎从来就没有经过认真地思考便不由自主地接受了人的认知能力是无限的、没有根本性限制的观点。我们认为,对于任何一个受了人的认知能力是无限的这种思想影响的人,当他面对20世纪许多最深刻和最令人难忘的“限制性或否定性”科学结论时,他都不可避免地要陷入一种尴尬的境地。通常人们最熟悉的这种限制性成果大概要数哥德尔不完备性定理和海森柏测不准原理。不过我们这里要提到的是可计算性理论中的丘奇－图灵论点。从表面上看，丘奇－图灵论点是一个肯定性命题,但也正是基于这个论点,人们才有了对什么是不可计算性的明确认识，并在此基础上相继发现了一大批不可计算或不可判定的问题或命题,丢番都方程有无整数解问题、半群（群）的字问题、四维流形的同胚问题等等就是其中的典型代表。等等这些事实的确定，逐渐让人们体会到,在数学和逻辑领域中,人的认知能力是有限度的。
首先，有了可计算性的精确定义，也就等于有了不可解性的精确定义,即对于一个问题，
88
如果我们证明了其“没有相应的一般递归函数”或“没有相应的一般递归谓词”，那么就可以确切地说该问题是不可解的。这是在数学史上人类第一次认识到，从逻辑意义上讲数学中存在着不可解的问题。以往人们总是以为，任何一个精确表述的数学问题，总是可以判定它是对还是错，是有解还是无解。暂时没有解决，以后也一定会解决。现在看来，有一些问题是根本就不存在算法的，这无疑是对人类智力的一次最深刻、最严峻的挑战。在我们看来，不可计算或不可判定问题的存在（以及哥德尔不完备性定理），不仅是对计算机的限制，而且是对我们人类自己的限制——对人类认知的限制。
其次，根据计算复杂性理论与丘奇－图灵论点，数学家把各种数学问题从其复杂性、难解性的角度作了如下一个分类：一是现实可解问题，即具有多项式复杂性算法的可以有效地解决的P类问题；二是理论上可解但现实不可解问题，包括仅有指数复杂性算法的较难的NP类问题、特殊的最难解的NPC类问题及“NP难的”问题和完全无法有效地解决的超NP类问题；三是理论上不存在任何算法的被证明为不可解的问题。这一结论无疑使任何数学问题都是可解的、甚至都是具有有效算法的幻想彻底破灭了。而这意味着：当我们费尽心思去求解一个数学问题时，我们可能是在求解一个不可解的问题；当我们绞尽脑汁去判定一个数学命题时，我们可能是在判定一个不可判定的命题。我们想要解决的问题可能已经包含了某些超越我们的智力所能把握的困难。而且由于数学家们还认识到，可计算函数共有可数无穷多个，而全体函数的个数却是不可数无穷的，因此不可计算的函数要比可计算的函数多得多（多无穷多个）。也就是说，在理论上，可以求解的问题尽管是无穷的，但不可求解的问题更是无穷的，而且是更高层次的无穷。这便是可计算性理论等数学理论告诉我们的一个铁的事实。
最后，数学和科学是不完备的。基于哥德尔不完备性定理——没有一个演绎推理系统能够回答所有的利用该系统的语言所描述的问题。每一个足够有力量的、一致性的逻辑系统都是不完备的——人们已经认识到数学是不完备的。同样，自然科学也是不完备的——自然科学的不完备性主要表现在存在着许多不可解的科学问题和一些否定性的科学结论。在一篇文章中，我们一方面根据人的认知的不完备性说明数学、科学的不完备性,另一方面又根据数学、科学的不完备性说明人的认知的不完备性。这似乎陷入了一个矛盾的循环论证之中，但我们认为,与其把这视为一个矛盾的循环论证,毋宁把它看作一个真实的现状。不完备的人创造了不完备的数学和科学,这不显得更真实、更符合逻辑吗?人类认知的不完备性正好通过自己的不完备的创造物得以显现,自己的创造物正是反观自己的最好镜面。
由此我们得到启示：1.并不是每一个问题都是可求解的，一个问题没能求解，并不总是因为人们没有找到求解它的方法。我们相信，有些问题无法求解、是由该问题的本性所至，即使将来人类的思维更加发达，技术更加先进，这些问题也依然是不可解的，或依然是没有求解它的方法的。2.理论上可解决的问题并不一定可现实地解决，因为任何问题都有它的时间复杂性和空间复杂性，时间和空间的极限就是求解问题的极限。在我们看来，理论上可解但现实上不可解问题的存在，更主要是对人类计算技术的挑战。无疑，计算不论是现代计算机的计算，还是中国古老的算盘计算，或是人脑的计算，它们在本质上都有一个物理的操作运行过程。这一过程的完成需要最起码的运行时间和计算装置（空间），即计算存在一个基本物理极限。计算的时间复杂性和空间复杂性的存在正是从时间和空间两个方面对计算技术的深刻挑战。3. 人类认识（认识主体）的无限性是可数的、不完备的，而有待人类去认识的对象（认识客体）的无限性是不可数的、完备的。也就是说，尽管人类的认识是无限的，但人类认识（认识主体）的无限性远远小于有待人类去认识的对象（认识客体）的无限性。因而人类总
89
有着永远也无法穷尽的世界奥秘，世界上存在不可知的部分或客体。换句话说，也就是人类不可能成为万能、全知的上帝。注意，我们这里并没有否认人类认识的无限性，人类的认识确实处于无限的发展过程之中。但是，如今从丘奇－图灵论点对人类认知能力的限制，我们进一步看到，人类认识的无限性是一种递归无限性，有待人类去认识的对象的无限性是一种非递归的无限性（现代数学早已揭示，所有递归集构成的集合是可数无限的，所有非递归集构成的集合是不可数无限的）。下面的论述可视为对这一观点的进一步论证。
三、丘奇－图灵论点对人类认知能力的限制
我们认为，丘奇－图灵论点最根本的哲学意义，就在于它表明了人类认知的一种计算主义特征，预示了人类的认知能力和极限，即它不仅是对机器认知的限制，而且是对人脑认知的限制。
在具体论述前，我们首先明确一个前提，大家知道，认知科学的一个被广泛接受的方法论原则是，对认知和智力的理解应从三个不同的层次来分析研究〔马尔〕：第一个层次是最抽象的“计算理论”层次，它关注的主要问题是：计算的本质是什么？或认知的本质是什么？；第二个层次是“表征和算法”的层次，它关注的主要问题则是：计算或认知的具体方法是什么？是如何操作的？完成计算任务的效率如何？第三个层次是“计算的物理实现”层次，它关注的主要问题又是：实现计算的物质载体是什么？它是如何运转的？我们的论点主要是在最抽象的第一个层次即计算的层次上言说的。当然，也不排除其他两个层次。
确切地说，丘奇－图灵论点具体地表明了：①人的认知结构是一种递归结构；②人的认知过程是一种递归计算过程；③人的认知能力是受递归规律限制的，即人只能在递归的意义上认知事物。我们不妨把它称为“递归认知假说”。
基于篇幅所限，这里我们仅就“递归认知假说”的第三部分做一论述。我们说人的认知能力是受递归规律限制的，人只能在递归的意义上认知事物，这包含两个含义：一是指人只能认知（计算）具有递归结构或递归性质的事物；二是指对于非递归结构或非递归性质的事物，人只能做递归性的认知。何以这样说呢？其实只要接受了认知计算主义纲领，上述观点便就是很自然的推论。因为认知计算主义纲领中所说的“计算”就是“递归计算”或“图灵计算”。西方认知计算主义学派的基本口号是“认知就是计算”，说的更具体些更确切些，实际上就是“认知就是递归计算”。既然认知就是递归计算，那么说人的认知结构是一种递归结构，人的认知过程是一种递归计算过程，以及人的认知能力是受递归规律限制的，即人只能在递归的意义上认知事物，便也就是很自然的了。不过下面我们还是给出我们何以提出这一更加具体明确的看法的几点理由：
1.可计算理论或递归论是研究计算的最一般性质的理论，即并不是专门研究现实中具体的计算机的计算能力的，因而它的结论具有很强的普适性、抽象性。由丘奇－图灵论点所揭示的计算本质，它不仅包括数值计算、定理推导等不同形式的计算，而且包括人脑、电子计算机等不同“计算器”的计算，尤其在理论上还包括了DNA计算机、量子计算机等新型计算机的计算。大家不要忘了，以丘奇－图灵论点为基石的可计算性理论是在电子计算机诞生之前的30年代提出的，即它不是在对电子计算机进行总结与抽象的基础上提出的，但它又深刻地刻画了电子计算机的计算本质。如今最先进的电子计算机在本质上就是一台图灵机。现在人
90
⑶
们又进一步认识到，目前尚在实验室阶段的DNA计算机、量子计算机，在本质上也是一种图灵计算。这说明不同形式的计算、不同“计算器”的计算，在计算本质上是一致的，这就是递归计算或图灵计算。因此，我们有理由相信，丘奇－图灵论点是对一切“计算器”的计算能力的限制，进而也就是对人类认知能力的限制。我们想，这或许正是由威格纳所说的“数学那不可思议的有效性”决定的。数学是研究模式的科学。这个模式既可以是一种现实世界的模式，也可以是一种逻辑可能世界的模式。而数理逻辑研究的模式是一种思维的模式、认知的模式和推理的模式。基于数学那不可思议的有效性，数理逻辑研究的这种思维的模式、认知的模式和推理的模式不仅是指人脑的思维、认知和推理模式，还包括一切非人脑——动物、机器等的思维、认知和推理模式。即具有高度的普适性、抽象性和有效性。另外，数理逻辑是人类大脑的产物，我们猜测，这种人类大脑的产物正好是反观大脑自身的最好镜面。我们相信，数理逻辑中许多具体的理论、定理，尤其是递归论、模型论中的理论、定理，均有着丰富而深刻的认识论意义和认知哲学的内涵。而且，我们认为，数学中人们只能解决具有递归性的问题，而对非递归性问题不可解的这一事实，是对我们上述观点的有力支持，亦可看作是一个例证。
2.尽管理论上和现实中存在大量不可解的问题，但对这些问题人们也不是无所作为的，人们依然可以从计算的角度将问题按其计算的难易程度和复杂性进行分类、分层，从而进一步了解有关问题的特征或解的性质。另外，无论是理论意义还是现实意义上的不可解，指的无非是无法得到精确解、解析解，这并不意味着不能得到近似解、概率解和局部解或弱解。对于一个不可解的问题，人们通常可以采取这么几个研究途径：1.不去解决一个过于一般的问题，亦即不妄图去解决一大类问题，而是通过弱化有关条件把问题限制得特殊一些，来解决这个一般问题的特例或更窄的小类问题。2.寻求问题的近似算法、概率算法。这是目前十分流行的研究方法。这就是说，对于不可计算或不可判定的问题，人们并不是袖手无策，而是依然可以从计算的角度，把不可解的问题——或为非递归问题、或为高指数复杂性问题——转化为递归问题或非指数复杂性问题，从而给予解决。这也就是我们所说的，对于非递归结构或非递归性质的事物，人只能做递归性的认知。
3.质疑和反对认知计算主义的人们的一个错误在于把某些问题计算机不能解决而人能解决这一暂时的事实绝对化。如他们认为，尽管今天的计算机可以做人不能做的许多复杂工作,但在模式识别、感知和在复杂境域中决策的能力远不及人。确实，今天的计算机在模式识别、感知和在复杂境域中决策的能力远不及人，但这并不从逻辑上或从根本上构成对计算主义纲领的否定。因为今天的计算机在模式识别、感知和在复杂境域中决策的能力正在不断提高，至多只是提高的速度还不能让大多数人满意。这里我们也想提醒质疑者们注意这样一个事实：计算机在模式识别等方面的发展还不足五十年，而人的大脑却已进化了数百万年。要想在如此短的时间里让计算机全面地达到人脑的水平，是不是太苛刻了些？在我们看来，从这个角度质疑认知计算主义纲领的朋友们实际上是对计算机提出了一个不现实的极其苛刻的要求（尽管其人可能并没有意识到这一点）。谁能料想得到百年后、千年后计算机的模式识别能力将会是什么样的？无疑，计算机不是万能的，计算机不能做的事有很多。但是，我们对这些计算机所不能做的事要有一个清醒的认识，比如，非递归函数它是不能计算的，具有高指数复杂性的问题它也是很难解决的，不过这些也是人脑所无法解决的。这正如有人说，计算机连同人的局限性也一起“复制”了。但更多的情况是，一些问题一时无法由计算机解决，那是基于计算机技术的相对滞后。只要不是出于计算机之本质的原因，那么今天不能做到的事，
91