机器上的带子

6.2　机器上的带子

即使不考虑其所有哲学上的保守立场，寻求一种希尔伯特式的有限直觉的数学模式是希尔伯特纲领面临着的最主要的问题。清楚的是，如果不存在严格的有限直觉的数学形式化公式，希尔伯特学派从一开始就不能处理任何东西，因为它一开始就得用真正的、有限的方法来研究形式定理。依赖于元数学层次上的非形式化的直觉概念，就像这些直觉被用到数学层次上一样，并不会给人们多少安慰：它不只过替代了原来的问题。

对这一问题的思考导致了在20世纪30年代几位数学家的工作，他们研究对于计算来说，那些构成人类能力的东西是什么，在更为广泛的有限符号序列的意义上来说，这些能力是如何被形式化的。英国数学家艾伦·图灵研究了人们操作计算的方式，从而在此基础上模拟出一种抽象的计算机器。当美国逻辑学家丘奇（Alonzo Church）与波斯特（Emile Post）各自提出他们的什么是有效的（真正的）可计算的观点时，哥德尔也考虑了他自己的模型。这些就是我们现在称之为计算机的几个理论原型。

图灵相当有说服力地表明，那些在原则上能够用人类计算器来计算的东西同样也能用人类的抽象机器来计算。这些抽象的机器非常类似我们今天的计算机，除了它们可能需要人们投入巨额的资金以及可能要花费任意长的计算时间以外。哥德尔虽然怀疑这些有效计算的模式，但他相信图灵的分析。在20世纪30年代，人们证明了各式各样的可计算性描述相互间是等价的。这给下列命题以经验的支持：

丘奇图灵命题：每一个有效的可计算概念（直觉意义上）都可以通过在通用图灵机上运行适当的程序来实现。

丘奇图灵命题并不是一个定理，它只是一个合理的假设。它不能够被证明。另一方面，对这一命题的反驳将包含发现某些我们可计算，但不能被图灵机所计算的东西。由于图灵的计算机器的概念是建立在对人类是如何进行计算行为的艰苦分析基础上，因此这样的反驳看来是不可能的。因此，几乎所有的人最终接受了这一命题。

上述命题对科学与盲目崇拜机器的文化的影响只是在后来才被人们理解。正是由于采用了人类心灵中某些过程的重要的计算，物理上实现了的模式，认知科学与人工智能研究领域大量采用图灵机与丘奇图灵命题，因此，我们可以相当肯定地说，在可计算的或有效计算意味着什么的问题上，我们已经达到了一致。大约说来，这意味着一种理想化计算机的程序，也就是说，对其计算能力来说，这是一个具有极大记忆力与没有生命极限的机器。

我们现在站在一种令人愉快的意识门槛上：那些最初作为人类计算能力的约定模式（被数学家认可，因为他们需要一种有限直觉计算的形式模式）将成为人类心灵的特殊地位的象征。这并不是计算机被模式化为心灵，而是沿另一条路径绕圈：心灵是计算机的一种模式。

人们可能会被引诱，视图灵机为一种崇拜的实体，在其想象中，我们人类为了自身的利益，被制造得非常强大⁽¹⁴⁾。人们可能会注意到有效的可计算性的观念不可能穷尽人类心灵的能力。一台图灵机能够做到的所有计算，我都能够做到，而且我们还能熟练地做多得多的计算。我还能够做它不能够做到的一些事情（当然不是计算）。

这看来是一个试图否认丘奇图灵命题的令人悲伤的尝试，还有些人确信我无法作任何此类尝试。我可能会质疑某些人趋向于理解和形式化这一命题，但不是这一命题自身本质的途径。其本质，从我理解来看，是那种在图灵机的概念中被捕捉到的直觉的（因此，也就是人类的）可计算性。情况也许是这样的，在直觉上可计算的东西都是在图灵机上可计算的。这意味着如果某些东西是图灵机不能计算的，那么我将肯定不能够计算它，这一点是很清楚的。我所埋怨的是相反的命题：如果某些事情能够被一图灵机所计算，它们也可能超越了我的计算能力。如在处理问题时，我只有有限的记忆力，有限的时间，我感到疲倦、我白日做梦等。

因此，图灵机的可计算性是一种理想化，一种约定，或许是一种基础性的突破，但仍然是一种理想化的。它像一台超级计算机。它像是深刻思想（Deep Thought），道格拉斯·亚当斯（Douglas Adams）书《希彻西克银河系指南》Guide to Galaxy）中的那台超级计算机，它完成了其计算，指出进入未来的最终答案是42，然而在未来中，人们忘记了最初的问题是什么⁽¹⁵⁾。图灵机不仅是一种理想化，而且还是一种特殊的理想化。这种抽象的计算机被专门设计来捕捉我能够计算的所有对象，但不是我能够做的所有事情。图灵肯定没有把他的模式运用到对人类婚庆仪式的详细研究之中，也没有把他的模式引入到对俄罗斯符号主义诗人心中的神秘行为的详细研究之中。他的研究令人信服地论证到机器能够捕捉到人类的计算能力（这种研究肯定过高地估计了这种能力，把这种能力提高到数学抽象的技术约定层次上），没有比这更好的接受理由了。

因此，在我们断言心灵就是图灵机之前，看来还有某些更重要的事情有待说明。任何事物都能够被转变为数学，模式化为一个形式系统。甚至可能以提前几天来进行模拟和预言。但这并不意味着天气是上帝个人计算机中软件的一部分。

然而，后来人们发现丘奇图灵命题并不会把人们引向这一方面。数学家们最初一致认为这一命题是对“直觉计算”的含糊概念描述，现在却成为人类心灵自身的定义。那些曾经是一种约定的描述现在被认为是一种规则的规定。

让我们关注似乎毫无怀疑的几件事。形式的可计算性的概念产生于对希尔伯特的有限直觉进行模式化的尝试。借助丘奇图灵命题，用机器来完全替代直觉。最终，十分明确的是：人们可以声称这种抽象的工具只不过反映出心灵的普遍蓝图，亦即作为物质实体的我们的普遍精神。

在我们考虑某些后现代思想家努力反对导致人类精神在符号上的安乐死的工作前，让我们考虑有关对可计算性极限的另两个结果。这与后面的讨论有关，这是一个方便的切入点，从中，可能引入由美国数学家查尔汀（Gregory Chaitin）所解释的随机性的概念。

从一开始，作为每一个形式系统，某些语言的形式化语法，能够被图灵机编码。所有的“证明”，所有的语法结构都表现为符号系列的某种基本运算的结果。这种语法规则能够被我们的理想计算机编成一个程序。对于自然语言而言，这些规则都可根据乔姆斯基（Chomsky）⁽¹⁶⁾的“X‐bar理论”来很好地理解。对我们的目的来说，它采用何种精确的形式，这是无关要紧的，只要它是相关于形式化的程序（因而是相关于理想化的计算机器），这就足够了。

因此，看来可以自然地问道，对任何给定的符号串来说，是否存在着一个程序能够确定它的结构是否合乎文法。这看来并不难。例如，我能够写出一个程序，一个接一个句子地推导出所有的合乎文法的句子，并检查是否每一个给定的句子最终显示在这一清单上。如果这一句子是合乎语法的，它将最终显示在其中。但如果它不合乎语法，我将不得不永远地等待下去。

因此，我充其量只能在这种“蛮力”（brufe‐force）的方法中，列举出所有合乎语法的构造，在这一长串序列中尽力地发现我的句子。但这种思想只完成了一半的工作。如果某些事情是合乎语法的，“蛮力”将告诉我它是这样的。还有另一半的麻烦，如果它不是，又如何处理？

事实上，在我让“搜索完所有句子”程序工作前，我不得不处理程序计算的停止与不停止的问题。如果我知道了程序在某输入点处停机，那么我就知道它将在一系列合乎语法的句子中发现我的句子。如果我知道程序并不会在一给定的输入点处停机，那么我的句子将不会在这一清单中出现，从而，我的句子也就不合文法。然而，一般来说，我们知道还没有一个程序能够做出这样的决定（这依赖于语法有多复杂，有些可能，有些则不能。）

一旦被应用于一种数学“语法”，上述说法就可以被解释如下：如果我用其可证明性来确认一个定理的真理性（证明的句子在语法上是“正确的”，能够借助于规则从公理句子中推出），那么我一般不能够确定一个陈述是否是真的。一般说来，存在着其真理是“无法确定的”句子。

这还不够，查尔汀已经证明情况可能更糟糕。不仅存在着其证明性是无法被有效确定的陈述，而且还存在着这样的陈述，其可证明性就像掷一枚硬币的结果：正面出现，可证明，反面出现不可证明那样不可预测。我们只能如此而已。后面我们还会给予讨论，因此我要阐述证明背后的基本思想。

为了形式化查尔汀的结果，注意我们并不需要考虑能够进行不同计算的许多不同的特殊图灵机。相反，我们能够考虑一个通用图灵机，它能够模拟任何其他的图灵机。那么任何图灵机能够被确定为通用图灵机的一个程序。人们采用什么样的程序语言是无关要紧的，因此，让我们假定，为简单性起见，我们正在处理的是“机器码”，也就是0与1的符号串。输入值能够被编成这一程序的一部分，输出值同样也是一串比特（0和1）。现在每一件事都用比特表示：输入、程序与输出。让我们不要忘记不可能判定程序是否停机的问题。

查尔汀询问如下问题：什么是一种“随意”选择程序将停机的概率？这种概率被称之为Ω（欧米伽），“停机概率”（halting probability），代表着一种由多次抛一枚硬币而记下的程序将是一个无规则程序概率。记住这一程序正是一个由0和1构成的序列。如果我选择0代表正面，1代表反面，那么通过掷一个硬币几次，就可得出一个“随机”程序。

因为一切已被表述为0／1的符号，关注同样表示的停机概率是方便的：所有Ω的十进位的数字也是0或者1，现在让我们看看为什么这个数字是不可能运算的，是因为没有程序可以生成它的数字的数列。

假设我们知道一个2位比特的程序的可能性将会停止。它的可能性有4种，这个数字可分出所有2位比特的程序：00，01，10，11。因此我们知道有多少2位比特的程序事实上停止了。例如，我们知道它们中的三个确切地停止了，我们可以运行所有2位比特的程序并等待。我们确切地知道它们中的三个会停止，所以我们极有耐心地等待它结束，到最后我们知道是哪三个停止了，没有停的一个就永远不会停止。

因此，我们可以决定哪一个2位比特的程序停止而哪个不会。这个论点也可以适用于更长的程序。如果我们知道n位程序的停止概率，对所有的n，我们能求解停机问题。它需要一些工作，但是，这个思想的更复杂的版本能够表明，如果数Ω的位是可计算的，那么，我们能够解决停机问题。然而，图灵证明这个问题是不可解的。所以，我们不能通过任何形式推理知道Ω，因为所有形式语言都能够编制为“语法”，这些语法规则在通用图灵机上是可编程的。

Ω的停机的概率封装了在任何形式理论中能被封装的所有信息。我们现在有一个单独的数字（用一明显的合理的方式来定义），它是如此的不可计算，以至于它超越了任何过去、现在和未来的形式理论的推理能力。

这并不像其听起来那样神秘。查尔汀（他在20世纪60年代所作的论证）引用了波莱尔（Borel）1927年所作嘲讽：

“人们能够根据对某一问题的答案是肯定或否定，每个后继的数字（二进制）等于0或1，来定义一个数。更进一步说，它将可能排列所有问题，这些问题能够通过像查法语词典一样查到它们。只有那些能够得到肯定或否定答案的问题才能得到保留。这样定义的数因此给出了科学、历史与好奇心的所有过去、未来与将来之谜的答案。”

查尔汀使用的是程序语言而不是法语，但思想是类似的。数字Ω，超越了形式方法。通过这种与波莱尔的思想联系，查尔汀的结论，更像图灵的最初方法，看来与连续统问题联系在一起。哥德尔定理同样产生于他试图证明古典的连续统理论。对连续统理论的不同模拟已经走得很远。所有的理论都有自己的优点与缺点。不知何故，人们总是在抑制其缺点，但当它们用到别的地方时，引起了不完备性、不确定性甚至随机性。

但所做的这些与随机性有何关系？它导致了查尔汀数Ω，停机概率，在某种意义上说是随机的。对术语“随机”有几种不同的描述。几乎所有这些描述都得以这种方式或那种方式来处理复杂性问题，查尔汀的描述也必须为我们的抽象机处理程序的复杂性问题。

我们将看一看这是如何工作的。随机性与混沌看来是几乎所有时髦的后现代主义所钟爱的东西，我将在本书的最后考虑这些后现代主义。事实上在下一章的开始，我们将有机会观察到随机性是如何进入后现代图景。让我们首先考虑几种考虑随机性概念的数学途径。

首先，让我们再观察一次0和1组成的比特串（string）。查尔汀是用最短完成程序的长度来定义一个串的复杂性并以此作为它的输出量。以此为例，一个包含100万个0的串被更简明地定义为一个含有可以打印出100万个0的程序，而不是实际上写出100万个0，所以它的复杂性是比100万少得多的。包含在串内的信息可以被压缩，它的信息内容可以被比这个串本身短得多的一个串所描述（captured）。所以我们不能说它是完全随机的。

根据这个观点，一个串被认为是随机的，如果它的描述无法被压缩成这一种方式：我们无法用一个长度比N小得多的程序来定义一个随机的长度为N的串（否则它将具有一定的结构，所以它将不是随机的）。在某种意义上说，这些是最复杂的串。它们是“随机的”，因为它们拒绝化归为更简单的东西。它们是形式上不可化归（irreducible）的。这样，一个随机串可以说是模拟一个事件，该事件的“原因”（产生它的程序）不能被简化为更简单的“原因”（产生它的一个更简单的原因）。随机事件“就要发生”。

简单的计算表明，随机串是普遍存在的，如给定长度的16串中只有1能够压缩为4比特，给定长度500串只有1能够压缩9比特。串的压缩性越好，结构性越强。带有结构的串是不常见的。不带结构的串倒是常见的。因此随机性实际上并不是非常有兴趣的现象，数学家真正感兴趣是可以给予描述的，能模型化的，因此是能够给予研究的东西。

查尔汀定理指出Ω经历了一切事物都可能经历的随机过程。在没有程序能产生其数值的意义上来说，它是无法被压缩的。无论选择哪种程序，我都无法从程序的结果当中得到Ω的一个确切数值。我只能说是0或者1，如果我认为是0，我有1半对1半的机会是正确的。这是我所能做到的最好的估计。

现在让我们把真理视为与可论证性相等，看看发生了什么。可论证性总是依据于某种形式化，某种“语法”。对通用图灵机而言，这种语法的规则可以用一种程序P编码。如果我们的语法足够广泛以至可以表达一些基本的数学概念，我们可以用合乎语法的句子来定义数字Ω。我们乐意得到封装在我们的形式系统中的真理，那就是合乎语法的句子。我们可以让程序P列举出所有合乎语法的句子，我们可以那么做。因为Ω用我们的形式语法定义，我们可以问关于它的数位的问题。Ω的第164位数字是0还是1？

但P只是一个程序，我们知道没有程序可以运算出Ω的所有的数位。所以，不论我的形式语法怎样，如果有一个语句像“Ω的第N个数字是0”，这将是不确定的，正如投掷硬币你无法决定将会是人头的哪一面一样的道理，它是随机的。并且，似乎所有足够强的形式推理系统都有一些随机性。

然而，所有这一切并不意味着真理是随意的以及每一件事都是任意的。我只是相当随便地说：“让我们把真理与可论证性等同起来，看一看发生了什么。”其结果是，在其中存在如此之多的困难，以致它们是如此之不可靠。如果我们不走向极端，看一看事情会走向多远。

【注释】

(1)引自Mancosu．From Brouwer to Hilbert（New York：Oxford university Press，1998）p．170．希尔伯特在其1922—1923年的演讲中论述了Kant立场的相关性，但他的演讲笔记在随后相当长的一段时间内都未发表。

(2)引自Mancosu（1998）p．198．

(3)引自Berlin（1999），p．89．

(4)Kant，Critique of Pure Reason，引自Detlefsen（1996），p．79．同样可参见pp．76—81，这一段对希尔伯特与康德比较进行了详细讨论。

(5)Herman Weyl．“The Current Epistemological Situation in Mathematics．”In Mancosu（1998），p．140．

(6)Edmund Husserl，The Crisis of European Sciences and Transcendental Phenomenology（Evanston，Northwestern University Press，1970）．第2、9段，其标题是“通过技术化抽空了数学自然科学的意义”。在同一段中，Husserl还论述到数学纲领的“直觉主义深化”，谨慎地哀悼了“实证科学”的偏见。这种偏见阻止了直觉主义寻求一种广泛的接受。

(7)这样一种把语言游戏引入不可通约的地域性的做法应该是后现代思想的主导观点，虽然这种观点，被典型地引入社会研究的领域。如：“社会主体自身看来就消解在语言游戏的这种传播之中。”（Jean‐Francois Lyolard．The Postmodern Condition：A Report on Knowledge［Mineapolis．University of Minnesota Press，1984］p．66）

(8)Hilbert学派与Nelson新康德主义学派的联系，见Mancosu（1998），173－175．

(9)J．Van Heijenoort，From Frege to Gödel（Cambridge Mass．，Harvard University Press．1967）．p．484．还请参见Mancosu（1998），p．81．

(10)引自Solomon Feferman，In the Light of Logic，（New York，Oxford University Press，1998），p．159．

(11)Louis Couturat，Opuscules et f ragments inédits de Leibniz，（Paris，Alcan，1903），p．28．引自Eco（1995），p．277．

(12)引自Feferman，S．In the Light of logic（New York；Oxford University Press，1998），p．158．

(13)同上书，第6—8章。

(14)作者在上一段谈到，图灵机最初是作为人类计算能力的形式模式而出现。然而，几年后，奇怪的事情发生了：人开始反过来论证人类心灵是图灵机的一种特殊产物。这意味着图灵机变成了上帝，这类似于基督教教条：“人是在上帝的想象中被创造的”。因此，作者的这句话意味着科学家过于匆忙地得出图灵机代表着一种智力模式，在其想象中，人的心灵不过是其特例的结论。这样做，科学家开始成为神学家而不是科学家。他们是在寻求一种实体，在其想象中，人类被创造出来。图灵机因此变成上帝的代名词。——译者按

(15)在这本名叫《希彻西克银河系指南》一书中，亚当斯发明了一台名为深刻思想（Deep Thought）计算速度相当惊人的超级计算机，它将解决终极问题（Ultimate Question），它回答了所有的哲学问题、解决了世界上所有的问题。经过数代人的操作，计算机最终给出了其答案：42。但其计算过程是如此之长，以致人们经历了相当长的时间后，忘记了终极问题是什么。因此，人们不得不重新制造另一台更高级的超级计算机（supercomputer），以重新发现终极问题是什么。作者在这里讲述这一故事，其目的是表明我们计算的理论模式，最初是作为人类计算能力的一种模拟，是一种理想化，并不能看作是人类计算能力的真实模式。在理论上，一台图灵机可以进行100万年的计算以寻求其解答，但它肯定不能够完全代替人脑。从这个意义上来说，计算机相当于Deep Thought，而人脑相当于那一台更高级的Supercomputer。——译者按

(16)Chomsky，1928— ，美国语言学家，转换生成语法的创始人。——译者按