《逻辑人生：哥德尔传》研究性摘要II

计算、AI和复杂性

文本出处： [美]约翰·L·卡斯蒂（John L. Casti），[奥]维尔纳·德波利（Werner DePauli）：《逻辑人生：哥德尔传》，刘晓力、叶闯译，上海科技教育出版社2008年

八、计算

1.程序、算法和图灵机

程序（program）或算法（algorithm）完全决定了一台图灵机，而图灵机是对程序或算法的表达。程序或算法的概念和图灵机的概念是等价的（它们都是形式数学概念）。

一方面，程序或算法是一种可计算策略，由有穷数目的指令组成，例如打印一个新符号或保留当前的符号，更改或保留当前的状态，向左或向右移，以及停止（停机）。

另一方面，图灵机是一种由一条无限长的纸带和一个读写头组成的理想机器（数学模型），可以运行某种程序或算法。图灵机对程序和数据不加区分，这意味着程序也可以当作是数据一样进行编码，从而我们可以设计一种被称为“通用图灵机”（Universal Turing Machine，简称UTM）的二阶图灵机，使得当我们把决定任意一个专用图灵机的程序编码并输入到UTM中时，UTM就可以模拟那个专用图灵机对数据进行处理/计算。

2.计算的本质：图灵-丘奇论题

“通过运行UTM上的恰当程序，每个能行过程（effective process）都是可实现的。”（pp.79）这相当于说，计算的本质就是图灵机可计算。

这一论题像是一个定义或断言，而不是一条真正的定理，因为在论题中的“能行过程”是我们关于计算的直观概念，并不能被形式化，因此整个论题不能被证明。

3.计算的极限

（1）可计算性

一个数是可计算的，如果有一台图灵机能够输出它并在有限步骤内停机。因此，一个整数n是可计算的，“如果有一台图灵机，从一个完全是0的带子开始，在有限步骤内停机，并且带子上有n个1连成一串，而其他地方全是0。”（pp.73）

然而，根据可计算的定义，我们很难说一个由无穷多位数组成的实数是可计算的。要么有一台图灵机“能够一个接一个地相继输出它的各位数字”（pp.73,引文略有改动），但这台图灵机却因此不能在有穷步骤内停机；要么有一台图灵机能在有穷步骤内停机，但却因此不能完整地输出这个实数的每一位数字。也就是说，对这样的实数而言，“输出”和“在有限步骤内停机”这两个可计算性的必要条件不能被同时满足，因此它不是可计算的。事实上，大多数实数都不是可计算的，我们对实数的计算一般只是近似计算，得到的是目标实数的近似值。

（2）不可计算数存在的证明

【证明一（间接证明）】考虑一台纸带上只包含两种可能符号的n态图灵机，它恰好可以写出(4n+4)2n种程序，程序的数量表明了这台图灵机至多能计算的数有多少。令n取值n=1,2,3,…，我们得出，图灵机至多能计算的数构成了一个可数集合（countable set），即一个与自然数的一个子集一样多的集合。但由于实数是不可数的，因此存在着不可计算的实数。

【证明二（直接证明）】康托尔对角线方法的实质不在于对集合或对象进行编码，而在于如何构造一个与已有集合或对象完全不同的新集合或新对象。要做到这一点，只需要使所构造的新集合或新对象与已有的每一个集合或对象都在某个部分不同即可。证明二利用了这种方法。

“假定我们列出所有的可计算数，并按照它们的十进位小数展开（尽管这样一张表可能有无穷长）。”（pp.74）现在我们来构造一个新数，它的第一位数是第一个可计算数的第一位数的前驱，第二位数是第二个可计算数的第二位数的前驱，……，第k位数是第k个可计算数的第k位数的前驱。由于这个新数与已有的每一个可计算数至少都有一位数字不同，因此，它与所有的可计算数都不同，从而它只能是一个不可计算数。

（3）不可计算数实例

“实际上，可计算数才是极个别的，而通常的数大多是不可计算的。”（pp.74）《哥德尔传》给出了两个不可计算的函数。

一个是忙海狸函数BB（n）。在所有的n态图灵机中，n态忙海狸（n -state Busy Beavers）是一个能在停机前输出最多的1的n态图灵机。忙海狸函数BB（n）则是一个表明n态忙海狸输出的1的数量如何取决于它本身的状态数n的函数。BB（n）的函数值增长速度极快，当n=12时，BB（12）就已经接近无穷大。这使得当n取值足够大时，BB（n）的函数值会超过任何可计算函数的相应函数值。因此，BB（n）是一个不可计算函数，并且，当n取值足够大时，BB（n）的函数值是一个不可计算数。

另一个函数是所谓“图灵机游戏”的必胜函数。假定有两个玩家A和B，A先任选一个正整数n，然后B根据n再任选一个正整数m，最后再由A根据m任选一个正整数k。在这场游戏中，“如果存在某个n态图灵机，从全是0的带子开始，恰好在m+k步停机，则玩家A胜。否则，玩家B胜。”（pp.77）然而，这场游戏没有哪个玩家有必胜策略，因为每一个必胜策略都需要计算一个函数值增长速度超过BB（n）的函数。由于BB（n）是一个不可计算函数，因此，为了得到必胜策略所需的必胜函数必定也是不可计算的。[补充：“根据博弈论（game theory），在玩家有必胜策略的意义上，任何固定的游戏，在有穷步内均能决出胜负。”（pp.77）]

4.希尔伯特判定问题和停机问题（Halting Problem）

（1）希尔伯特判定问题：“对任何形式系统F，能够找到一个有穷可描述的形式系统，判定F中的任何符号串是语法正确的吗？一个近似的表述是，是否存在一种系统的判定程序（decision procedure）能够告诉我们，任何给定的形式系统F的合式符号串是否为系统的定理。”（pp.68）

[疑问：判定问题的第一个表述令人不解，“语法正确”仅仅是“合式”的意思吗？]

（2）停机问题：是否存在一个能在任何情况下执行的单一（single）图灵机程序，能够预先判定一个给定的图灵机程序P在处理一个输入数据集I时是否会（在有穷步内）停机，或其停机条件被满足？

（3）图灵机的停机条件：一般是像“如果满足这个或那个条件的如此这般的量出现，则停机；否则继续计算”（pp.78）之类的隐式规则，以至于很难从图灵机程序本身直接得到。

（4）停机问题不可解（图灵停机定理）：“给定一个程序P和一个输入数据集I，一般来讲很难判定P是否会完成具有输入I的程序。”（pp.78）

（5）形式逻辑系统等价于图灵机：一台图灵机的初始内部状态和纸带上的初始符号对应于一个等价形式系统的公理，包含在图灵机程序中的所有操作指令对应于等价形式系统的推理规则，而图灵机的所有可能输出则与等价形式系统的所有可能的定理相一致。根据这种等价关系，我们会发现希尔伯特判定问题与停机问题是等价的，因此停机问题的否定解（停机定理）同样构成了对判定问题的否定解，而停机定理与哥德尔不完全性定理又是等价的。

[说明：从停机定理与哥德尔定理的等价性中，我们可以看到，实际上哥德尔定理早已表明了判定问题的不可解。因此，（受哥德尔影响的）美国逻辑学派的代表人物丘奇用-可定义性和一般递归的概念对判定问题不可解的证明与图灵之证明的等价性也就部分地可以理解了。]

九、思维机器和人工智能（AI）

1.认知科学（Cognitive Science）简介

根据心理学家加德纳（Howard Gardner）的观点，“认知科学是哲学、心理学、语言学、人工智能、人类学和神经科学六大传统学科的交叉学科。”（pp.84）与六大源学科相区分，认知科学具有其特有的五个核心特征：

（1）心理表征（mental representation）的概念对于人类认知行为的讨论是必要的，并且对该概念的分析必须区别于生物学层次和社会文化层次。

（2）必须把数字计算机作为人类心智的模型，借助计算机处理信息的方式来研究信息是如何被心智处理的。

（3）忽略情感、情境、文化和历史的因素对认知活动的影响（De-emphasis of Affect, Context, Culture and History）。

（4）交叉学科性（Interdisciplinary）：认知科学从六大源学科吸取方法，并力图削弱甚至完全消除六大源学科之间的壁垒。

（5）传统哲学问题（Classical Philosophical Problems）：认知科学家同样关注心灵哲学和认识论的相关问题。

2.人工智能：认知科学的一个子领域

2.1.强AI

用机器模拟人类认知，即设计“思维机器”，在原则上是可能的。基于模拟方式的根本差异，强AI可以分为以下两大基本立场。

（1）自顶向下（Top Down）/Gofai

人类智能和认知能力与人脑的特殊物理构成方式无关，而是集中体现在人脑的“思维规则”对知识（或信息）的符号表征的运用。因此，要建造一台思维机器，关键在于抽象并编码大脑的高阶表征模式和思维规则让计算机执行，又或者说是“以心智（mind）的一种形式理论镜像地反映世界”（pp.90）。在这种意义上，Top Down的世界观是理论负载的（theory-laden）。

正如形式系统以少量的公理和推理规则得到尽可能多的定理，持Top Down立场的研究者致力于让计算机以尽量少的知识和规则解决尽可能多的问题。在1955年-1965年，他们主要是让计算机利用“手段-目的分析”（means-end analysis）的通用启发搜索方法来解决问题，利用各种有效运算来减少系统当前状态与期望目标的描述之间的差距。司马贺（Herbert Simon）、纽厄尔（Alan Newell）和肖（Cliff Shaw）于20世纪50年代发明的通用问题求解程序（General Problem Solver）利用了这样的启发方法，是最早的Top Down程序。

由于日常生活中的大多数实际问题都涉及到大量的关于真实世界的背景知识或“默会知识”（tacit knowledge），为了让计算机能解决这类问题，在1965-1975年，持Top Down立场的研究者试图创造一个真实世界的模型，即所谓“微型世界”，在这个模型中包含了各种简化的关于真实事物的信息。计算机通过完全理解这个微型世界和掌握其中的背景信息，就能借助对微型世界的思考解决真实世界中相应的实际问题。

由于常识知识（common knowledge）不能解决所有深层次问题，因此持Top Down立场的研究者从1975年开始试图将数据结构引入计算机程序，使计算机有能力解决这类问题。

然而，由于常识知识和数据结构的引入迄今均未成功，这使得基于Top Down立场设计的计算机并不能解决人类心智所能解决的大量问题，因此，这一立场的吸引力下降，逐渐成为了拉卡托斯（Imre Lakatos）所说的一个“退化的研究纲领”。（pp.90）

[说明：Top Down设计心智的形式理论的想法与早期维特的语言图像论近似，哥德尔定理对后者的驳斥间接地说明了前者没有吸引力。]

（2）自底向上（Bottom Up）/新联结主义（New Connectivism）

Bottom Up立场采取一种关于人类智能的“内在者”的第一人称观点，认为人脑的功能结构对于人类智能和认知能力起了关键作用。因此，设计一台思维机器的核心在于构造一种计算机程序以模拟人脑的功能结构。对Bottom Up立场的支持者来说，构造一种包含思维规则的、关于心智的形式理论是不必要的，因为只要机器具有了人脑的功能结构，思维规则就能从功能结构的模型中突现（emerge）出来。在这个意义上，与Top Down相对，Bottom Up的世界观是不需要理论的（theory-free），即认为“在没有世界理论的世界中智能地行为是可能的。”（pp.93）

（a）人脑的功能结构

人脑包含了上千亿神经元，这些神经元通过突触连接成一个协同作用的网络模式[整体并行论（massive parallelism）]。在其中，每一个神经元都可以看作是一个简单处理器（simple processor），即一台极其简单的计算机；而连接神经元、决定神经元发放模式的突触，其连接强度由大脑中的各种学习过程而非直接给定的思维指令控制，这使得大脑是非程序化的（unprogrammed），具有很强的适应性（adaptable），从而在本质上可以允许重新改写自己的程序，重新组织神经元的连接——这正是记忆、学习和创造性思维的必要条件。[说明：记忆和适应性学习涉及大脑以某种半持久方式改变其状态，而创造性思维在大脑中会生成和储存一些新东西，这也涉及到大脑神经元的重新组织。见pp.92。]

（b）模拟大脑硬件的程序——神经网络

每个处理元素都对应于大脑中的一个物理神经元；每一种连接都有一个可正可负的数值权重，以表示一个神经元对另一神经元的刺激/抑制的影响。在神经网络中，每一个神经元的行为取决于它从邻近神经元接收到的刺激和抑制之影响的总和。神经网络具有极强的适应性，可以接受训练，通过核正权重来回应一套目标模式，在此基础上还能对类似于目标模式的其他模式给出回应。随着时间的推移以及与环境之间的相互作用，神经网络还可以用更有效的思维模式取代过去的模式。

受过训练的神经网络还具有其他一些与人脑相关的特征。例如，它可以把一个给定的模式识别为目标模式（训练模式）的一部分，也可以区分不属于目标模式的新模式（识别新颖性）；它可以呈现出整个网络的协同作用，也可以只表现单个神经元的行为，甚至表现出完全脱离网络的行为。

（c）神经网络的局限

神经网络如果要具有人类的智能，就必须拥有与人相同的概括能力。这就要求神经网络能够鉴别出与特定输出相关的输入的类型（type），并对属于同一类型的输入作出相同的回应。然而，要让神经网络具有这样的概括能力存在着两个困难。

第一个困难是，为了让神经网络能够鉴别出不同的模式类型，类型之间必须存在严格的界限，这就相当于限制了智能行为产生的可能性。

第二个困难是，当一个神经网络对一个特定类型的输入作出了出乎意料的反应时，网络设计者很难辨别这究竟是神经网络的一次概括失败，还是神经网络具有了一种关于“类型”的不同概念，以至于把给定输入识别为属于另一种类型。

考虑到以上两个困难，要使神经网络具有与人相同的概括能力，神经网络似乎得全方位地“拟人化”，即不仅要具有人脑的功能结构，还要拥有与人一样的需要、欲望和情感，乃至一个适当的躯体。这是很难做到的。（常识知识的难题）

2.2.弱AI

思维机器是不可能被设计出来的。支持这一立场的主要有如下三类哲学论证（均基于对“智能”这一概念的精细思考）。

（1）现象学（Phenomenology）论证：休伯特·德赖弗斯（Hubert Dreyfus）&斯图尔特·德赖弗斯（Stuart Dreyfus）

德赖弗斯兄弟的现象学论证发端于海德格尔（Heidegger）、胡塞尔（Husserl）和梅洛-庞蒂（Merlau-Ponty）等现象学家的思想——“（人类的）认知行为不能归于遵循一套规则”（pp.97）。人类的智能不仅仅体现在对规则的遵守，更体现在超越规则的行事经验和“本能”，而后者是不能被总是遵循规则行事的计算机捕获的。因此，我们不可能真正设计出一台思维机器。

德赖弗斯兄弟以开车为例说明其论点。要学会开车，需要经历五个阶段：

在初学者（Novice）的阶段，司机只是学习一系列刻板的开车规则，不必考虑对路况和天气的感觉。

在高一级初学者（Advanced beginner）的阶段，司机开始根据对路况和天气的感觉来运用开车规则。

在胜任者（Competence）的阶段，司机掌握了全面的驾车技巧，甚至为了达到开车的特定目标而违反一些刻板的规则。

到了熟练者（Proficiency）的阶段，基于对过去经验的提升，司机开始拥有一种“自然而然的领悟和‘洞察’一项计划或策略的‘本能’”（pp.96），以至于他在开车中的所有判断虽然都是出于对景况的“感觉”，但却都是慎重的、有意识的选择。

最后是专家（Expert）的阶段。司机不再把开车当作是要解决的问题，也不再为开车做出任何决断。他仅仅是在根据直觉开车，开车只是司机的一项正常工作。

从开车的例子中，我们可以看到，人类的智能不仅仅是遵守规则，还可以破坏规则；除了对规则的考虑以外，还体现在基于大量经验而获得的、超越规则的行事“本能”。因此，规则并不能完全支配人类的认知或智能行为。

由于经验往往与默会知识相联系，因此，作为一个第三人称论证，现象学论证实质上揭示了强AI立场所面临的常识知识的困境。

（2）反行为主义（Anti-behaviorism）论证

（a）图灵测试：

一项由图灵提出的著名的智能标准。图灵建议通过模仿游戏（Imitation Game）观察人的行为，从中提取判定人的智能/思维的标准。假定我们已有了关于人的智能/思维的标准，我们就可通过图灵测试来判定一台机器是否有人的智能/思维。给定一台测试机器和若干测试者，如果那台机器能表现出与有智能的人难以分辨的行为（例如对话、下棋等等），以至于成功地欺骗了测试者，使他们认为那些行为是由有智能的人做出的，那么我们就可以说，那台机器是有（与人类相同的）智能的。

图灵测试本质上是一项行为主义的标准，体现了关于人类智能的第三方观点。它对智能的鉴别完全不考虑机器的内部构成，而是“单纯依靠观察机器的输出行为”（pp.88）。

（b）布洛克（Ned Block）和塞尔（John Searle）的质疑：

布洛克和塞尔均认为图灵测试并不是一项判定智能的恰当标准。

（i）布洛克认为，机器是否有智能，不仅仅与其是否有能力做出与有智能的人难以分辨的行为有关，还与其产生行为的方式有关。例如，假定我们把一个能恰当安排不足5小时的所有可能对话的树结构输入一台计算机，然后让这台计算机与询问者对话。即使这台计算机能通过图灵测试，但我们也并不认为以树结构生成对话的它真正具有智能。

（ii）塞尔同意布洛克的观点，并通过限定行为产生的方式给出了一项判定智能的新标准。在他看来，机器具有智能的必要条件是具有意义和语义理解能力。（关于智能/思维的第一人称观点）只有当机器是通过对意义的理解，而不是仅仅凭借一系列语法操作产生那些与有智能的人难以分辨的行为时，我们才愿意承认它们真正具有智能。然而，根据这项新标准，机器是不可能拥有智能的。因为计算机的“内部行为是纯粹句法的”，而“单纯的句法（即符号变换）的总和决不会产生语义”，因此，“计算机不可能理解支配它的符号的意义（meaning）”。（pp.97）

塞尔以中文屋（Chinese Room）论证说明了他的上述观点。计算机的所作所为可以类比为一个在一个封闭屋子内的人，仅凭借查阅中文字典与屋外懂中文的人所进行的完美交流。我们一般认为这个人不懂中文，因为他并不真正理解中文的意义，他为交流所做的一切完全是句法层次的。就像我们认为中文屋内的人不懂中文一样，类似地，我们也会认为完全句法的计算机不具有智能。（类比推理）

（3）诉诸哥德尔定理（Godel’s Theorem）：卢卡斯（John Lucas，1961）、彭罗斯（Roger Penrose,1989，《皇帝新脑》）

卢卡斯指出，任何机器（形式系统）都存在不可证的算术真理，而那些真理却可在机器（系统）之外为人类心智所知（彭罗斯：“洞察”），因此“人类心智的能力必定超越任何机器的能力”。（pp.98）由于机器的能力实际上也就是逻辑理性或计算理性的能力，卢卡斯的论证相当于说，人类心智的能力有超出逻辑和计算的部分，因此不能被归结为后者。

[补充：对应地，强AI的观点实际上是说，“所有人类认知行为都是可计算的（行为）。”（pp.101）]

彭罗斯接续了这个思路，他认为“至少人类思维的某些部分与不可计算量有关”。之所以如此，是因为“存在神秘的量子事件影响着大脑的神经元发放模式”（这只是一个宽泛的、带有思辨色彩的断言，pp.82,98）。

然而，这种诉诸哥德尔定理的论证路线是值得商榷的。马丁·戴维斯认为，哥德尔定理只适用于具有可靠性的机器（系统），但人类心智完全可以是一个不可靠的机器（系统）。（见《引擎》摘要）本书的两位作者则提示了另一种可能。他们指出，哥德尔定理的前提是机器（系统）具有一致性，但人类心智完全可能是一个不一致的机器（系统）。总之，以上两种可能性均试图表明，哥德尔定理在AI的领域并不适用，设计一台思维机器始终是可能的。

3.从人工智能（AI）到人工生命（AL）

哥德尔认为，可能存在（甚至在经验上可发现）一台思维机器，但这台思维机器可能是不可靠的（马丁·戴维斯），并且是人类不能理解的。1990年，雷（Tom Ray）用Tierra模拟器和电子有机体成功地模拟了达尔文进化过程，从而第一次明确地表明，“进化过程是独立于特殊的物质基质的。”（pp.100）

由于进化可以为最基本的结构带来惊人的复杂性，并且也可能在机器群体中发生，这就提示了一种设计思维机器的可能性，即思维机器有可能通过进化过程从最基本的机器程序中生长出来。这相当于说，AI首先得是AL。“如果你能够在一台计算机上创造生命，那么智能将自然产生。”（pp.103）

为此，我们将注意力转向AL领域是值得的。拉斯马森（Steen Rasmussen）在严格的实验基础上提出了AL的假设集（pp.101-3）：

假设（1）：一台图灵机可以模拟任何物理过程（包括其中的信息传递规律）。

[说明：这相当于说，图灵-丘奇论题不仅对所有能行计算过程成立，还对所有的物理过程成立。]

假设（2）：生命是一个物理过程。

[说明：生命是系统内的物理组分的功能的组织。对于功能主义者和联结主义者而言，认知也是如此。“人类思维就是大脑的物理组成部分被组织的产物。”（pp.101）假设（1）和（2）合起来表明了人工生命是可能的。]

假设（3）：存在可区分生命系统和非生命系统的标准。

[说明：我们有极强的直觉可以帮助我们直接判断某物是否是生命，而且我们目前对于生命至少有一个共识——“所有的生命系统都应包括新陈代谢功能、自我修复和复制功能。”（pp.102）这个假设则进一步断言，判定生命的无例外的严格标准是存在的，尽管当前我们对这样的标准究竟是什么仍有争议。]

假设（4）：一个人工有机体必定感知一种实在R*，对于它，这种实在就像“真实”实在R对于我们那样“实在”。

假设（5）：实在R*和实在R具有相同的本体论地位。

[说明：假设（5）是（4）的一个推论。如果思维机器和有智能的人具有相同的本体论地位，那么会涉及到一个从“是”到“应该”的问题，即思维机器是否应被赋予与人相同的公民权利。]

假设（6）：可以通过研究不同的实在R*的详情，学习我们实在R的基本性质。

[说明：“这个假设是全部认知科学事业的存在理由。”（pp.102）它断言机器世界和真实世界是“同构的”或“功能等价的”，这使得我们可以通过对机器和人工生命的研究来认识真实生命的形成。]

十、复杂性和随机性

1.奥卡姆剃刀（Ockham’s Razor）：“当犹豫不决时就采用最简单的说明事实的理论。”（pp.114）在哥白尼革命中，日心说相比于地心说（附加一系列辅助假说）的吸引力就在于，尽管前者没有后者预测得那么精确，但前者确保对观察证据给出了合理解释的前提下，做到了比后者更简单。

2.复杂性和随机性的概念

“复杂性”和“简单性”是两个可被形式化的直观概念。“大致来讲，简单性=描述的经济性。”（pp.114）由于简单性和复杂性是相对的，为了方便起见，在这里我们可以只考察复杂性。

（1）一般而言，一个事物/理论/数的复杂性可被定义为对它的最短描述或生成它的最短程序的长度（size）。长度可以以多种方式衡量，例如敲键盘的次数或ASCII编码的字节数等等。在这里，“我们把一个数或程序的长度取作写下那个数或程序所需二进制位数。”（pp.119）

（2）对一个一个事物/理论/数而言，随机性是它所能达到的最大的复杂性。随机性与“（良）模式”的概念相对。

一个数是随机的（random），当且仅当它不具有良模式（well-patterned），即所有生成它的最短可能的（shortest possible）程序的长度都不比它本身短（亦即：对它本身的直接表达就是生成它的最短程序）。

一个数是非随机的（nonrandom），当且仅当它具有良模式，即它“能由一个长度明显短于它自身的计算机程序产生。”（pp.119）

（3）复杂性和随机性均与模式和结构有关。一个事物/理论/数越复杂，相对而言它就越没有模式，也越不可构造。如果它具有了所能具有的最大复杂性，即随机性，那么它就完全没有模式和结构了。

3.蔡廷定理和相关推论

3.1.贝里（G. G. Berry）悖论：

假定U是不能用词语表达的最小数。一方面，根据摹状词“不能用词语表达的最小数”的语义，U是不能用词语表达的；另一方面，U却已经由以上的摹状词表达出来了。这是一个矛盾。

格雷戈里·蔡廷（Gregory Chaitin）认为，这个悖论产生自“表达”这个不可形式化的概念。如果用“由复杂性为n的程序不可计算的最小数”这个可被形式化的短语替换以上的摹状词，悖论就会被消除。蔡廷正是在处理贝里悖论的过程中发现了蔡廷定理。

3.2.蔡廷定理：没有程序能计算比它自身更复杂的数。更具体地说，没有复杂性为n的程序能生成一个复杂性大于n的数。

3.3.蔡廷定理的推论：

（a）（考虑到程序与形式系统等价）最直接的推论是，“尽管存在具有所有复杂性层次的数，但证明这个事实是不可能的。”（pp.120）

（b）“对于充分大的数N，不能证明一个特殊的数串具有大于N的复杂性。”（pp.121）

（c）对于“一个层次N，没有一个二进制数串长度大于N的数能被证明是随机的”。（pp.121）

（d）对任意一个程序，“总存在能由这个程序生成的一个最复杂的有穷数t”（pp.122）,但比t更复杂的数也总是存在的。

3.4.重要结论：尽管几乎所有的数都是随机的，但我们不能证明任意一个给定的数是随机的。（pp.121）

（1）关于“几乎所有的数都是随机数”的证明：

所有长度（即对应的二进制位数）为n的实数一共有2n个，在其中所有的非随机数（即复杂性小于n）所占的比例很小，例如，其中复杂性不大于n-5的数最多有2n-4-1个，占总体的比例不到1/16。当n→∞时，易证非随机实数集仅仅是实数全集的一个无穷小子集，以此结论得证。

（2）关于“任意一个给定的数是随机数”之不可证：

给定任意一个具体的数n（n足够大），如果要证明n是随机数，必须存在一个程序P，“它核实n只能用比P长的程序生成”。（pp.121）[why?]

假定程序P存在。一方面，我们可以用P生成所有长度为1,2，…等等的程序，其中有一些程序实际上证明了P不能生成n。另一方面，当P存在时，我们又拥有能打印出n的程序，以至于P可以生成n。[why?] 这是一个矛盾。因此，程序P不可能存在，进而n是随机数不可证。

我们可以从两个角度进一步理解为什么“任意一个给定的数是随机数”是难以证明的：

（a）考虑随机数包含的信息量：几乎所有的实数都是无限不循环的、随机的数字序列，以至于序列中的每一位数均携带一个正信息，并且前一位数的信息不包含下一位数的信息。这使得一个随机实数包含的信息超过了所有有穷数逻辑系统的总和所包含的信息。由于我们不能凭空从少量的信息得到更多的信息，因此，一个给定的实数是随机数都是不可证的。（pp.121-2）

（b）考虑随机数的可能生成规则：任一随机数都是一个无模式的数字序列。根据形式系统和图灵机程序的等价性，一个数是随机数是可证的，当且仅当存在一种生成规则，可以生成无模式序列中的每一位数。但如果存在这样的生成规则，并且比“序列的任何一个固定的前段的长度更短”，那么序列就不再是无模式的，这构成一个矛盾。因此，一个任意的数是随机数不可证。

（3）随机数不可计算：总之，“任意一个给定的数是随机数”之不可证告诉我们，随机数（至少当足够大时）是绝对不可计算数，是任何计算机程序均不能生成的。

4.科学理论的复杂性[所罗门诺夫（Ray Solomonoff，1964）、格雷戈里·蔡廷（Gregory Chaitin）和托姆（Rene Thom）]：

（1）理论等价于图灵机（所罗门诺夫）：一个（科学）理论相当于是这样的一台机器，“给定一种对实验装置的描述作为输入，就会产生经验观察的数据作为输出。”（pp.116）

（2）科学理论作为“减少任意性工具”：

托姆把科学理论称为“减少任意性工具” （arbitrariness-reducing tools）。他和蔡廷（包括更早的所罗门诺夫）均认为，“一个科学理论的关键是尽量减少观察数据的任意性。”（pp.116）为此，科学理论不仅需要对观察数据作出预测和解释，还需要对观察数据进行提炼，即“比实际数据本身更短地再现观察数据”（pp.116）。在这种情况下，我们说观察数据具有良模式，而提炼它们的科学理论是非随机的。

更进一步来讲，只有非随机的科学理论才是有用的。如果一个科学理论是随机的，那么等价的所有最短可能的程序并不比观察数据本身的表达更短。在这种情况下，观察数据是没有良模式的，不存在简洁的规律（或规则）可以对它们作出预言或解释，以至于我们最好的呈现观察数据的方式就是直接表达它们，科学理论就完全无用了。

（3）蔡廷定理和理论解释的限度：

假定存在一台UTM（用M表示），“它的推理能力相当于最专业和最具智慧的人的能力”，并假定K表示数学和所有自然科学的最新知识。对M来说，它能计算的最复杂的数t=复杂性K+复杂性M+100,0000。

鲁迪·拉克（Rudy Rucker）对t值作了估算。假定K的知识容量是1000本书，每本书的平均容量（以ASCII码表示）是800,0000比特，即100,0000字节。因此，K的复杂性是80亿比特。同样地，M的复杂性也可用1000本平均容量为800,0000比特的书刻画，因此也是80亿比特。最后一项100,0000在计算M程序的资源占用（overhead）可以舍去。最终，t值不会大于160亿比特。

根据拉克的估算，人类推理能力的限度（M）是80亿比特，超过这个限度，“理性和系统化分析将让位于直觉、洞察、感觉、预感和意会。”（pp.123）而科学理论所能解释的观察数据（其复杂性？）则最多是160亿比特。对于观察数据（其复杂性？）大于160亿比特的现象，没有任何一个可能的科学理论能够加以解释，尽管依然可能存在一个“相对简单”的解释，但对人类来说是过于复杂、难以理解的。

5.丢番图方程、希尔伯特第十问题和算术的随机性

5.1.丢番图方程：一类有（正/负）整数解的多项式方程。如果把一个一般的多项式方程看作一个丢番图方程，那么前者的整数解的集合就构成了后者的全部解集。

5.2.费马猜想：当n是大于2的整数时，丢番图方程xn+yn=zn没有正整数解。1993年，此猜想由怀尔斯（Andrew Wiles）证明，成为费马定理。

5.3.希尔伯特第十问题（丢番图方程问题）：是否存在一种一般性算法，能判定任意的丢番图方程是否有解，或解集是否为空集？（pp.125）

5.4.希尔伯特第十问题不可解：

（1）要判定任意的丢番图方程是否有解，我们不能依靠蛮力搜索方程的第一个解的算法，因为第一个解可能不存在，也可能因数值过大而难以找到，而这两种情况是难以区分的。

（2）波斯特认为第十问题是不可解的。马丁·戴维斯、朱丽亚·鲁滨逊（Julia Robinson）和普特南（Hilary Putnam）证明了，“如果存在一个丢番图方程，它的解完全以一种特殊的爆炸性方式呈现，那么，希尔伯特第十问题在否定的意义上将得到解决。”（pp.126）

（3）1970年，马佳舍维奇（Yuri Matyasevich）利用斐波那契数列（1202年由比萨的莱奥纳尔多引入，被用于描述由野兔繁殖行为构成的爆炸性增长模型）找到了一例爆炸性地呈现解的丢番图方程，从而最终给出了第十问题的否定解。

马佳舍维奇证明的一个推论是，“存在一个多项式，如果其变量a, b, c等等取全部正整数为值，那么这个多项式本身的正数值恰好是素数集合。”（pp.127）这样的多项式已经被构造出来，它一共包含26个变量。

（4）图灵机等价于丢番图方程：马佳舍维奇的证明的一个要点是，“任何计算都可以编码为一个多项式。”（pp.127）由于每一个多项式方程都可以看作是一个丢番图方程，因此，马佳舍维奇的要点相当于说，“对每个图灵机，都存在一个与之等价的丢番图方程，这个方程的解的特性严格反映对应图灵机的计算能力。”（pp.127）

5.5.指数丢番图方程（exponential Diophantine equation）、停机问题和算术随机性

（1）指数丢番图方程：丢番图方程的一个普遍类型。在这类丢番图方程中，变量可以以以其他变量为幂，例如，方程ab + 5c3 - d3e = 0即是如此。（pp.127-8）

（2）停机问题不可解的丢番图方程证明

基于琼斯（James Jones）和马佳舍维奇的结果，蔡廷找到了一个特殊的只带一个参量k的指数丢番图方程组，其中每个方程的区别只在于参量k的取值，而k可以取遍自然数。这个方程组中的方程“对k的一个给定值有解，当且仅当一台UTM的第k个计算机程序（即这个程序的哥德尔数是k）曾经停机”。（pp.128）

由于第十问题不可解，因此不存在一个一般性算法，以判定以上指数丢番图方程组中的每一个方程是否有解。再根据图灵机和丢番图方程的等价性，我们可以得出结论，不存在一个一般性算法，能够判定UTM上的计算机程序是否停机。这就是对停机问题的否定解。（第十问题与停机问题是等价的。）

（3）停机问题的拓展：随机程序的停机问题

给定一台UTM，对它能运行的所有程序进行编码，并按照编码大小排成一个序列。现在，从程序序列中随机选取一个程序令UTM运行，又或者令UTM运行一个给定的程序，但该程序的输入量是随机的，问：UTM是否会停机？

为了回答这个问题，蔡廷又构造了一个只带一个参量k（可取遍自然数）的新指数丢番图方程组，这个方程组有超过17000个附加变量，记为Χ (k, y1, y2, …, y17000+) = 0。[说明：Χ是希腊字母，读chi。]

从这个方程出发可以构造一个特殊的二进制数串，使得：数串的第n位是1，当且仅当Χ = 0对k=n有无穷多个解；数串的第n位是0，当且仅当Χ = 0对k=n有有穷多个解（包括无解）。假设数Ω表示由这个特殊二进制数串代表的实数，它具有如下特征：

（a）数Ω是一个不可计算数；

（b）由数Ω是一个不可计算数可以推知，数Ω是一个随机数；

（c）数Ω的二进制数串在统计上和逻辑上都是独立的。[说明：蔡廷把丢番图方程有无解的问题替换为其解集是有穷还是无穷的问题，就是为了确保对问题的回答能对每一个k的取值独立，从而确保了由问题生成的这个二进制数串的独立性。]

（d）通过在数Ω前加一个小数点，得到的新数（代表0和1之间的一个小数）可用于表示UTM在运行一个随机程序或一个固定程序在处理一个随机输入时，停机的可能性。[疑问：可能性具体是什么没说，而且数Ω似乎不是一个固定值？]例如，当新数为0时，随机程序必定不停机[原始程序STOP可处理这样的情形？]；而当新数为1时，随机程序必定停机。

（4）数Ω和算术的随机性（算法信息论）

取一个有穷的但“充分大”的整数，例如某个大于忙海狸函数值BB（12）的数，令k的取值大于这个数。数Ω的构造使得其对应的二进制数串的第k位及以后位的数字是0还是1都是（在逻辑和推理的范围内）不可判定的和不可计算的。这样的（绝对）不可判定数字有无穷多个，这也就表示对k的这些无穷多取值，方程Χ = 0的解集是有穷还是无穷的是（绝对）不可判定的，尽管答案必定是两种可能性之一。事实上，由于两种可能性（有穷或无穷）是完全的[疑惑：什么意义上的“完全”？]，因此可以在逻辑和推理之外，通过掷硬币的方式来合法地判定，从而对k的那些无穷多的每一个取值，方程Χ = 0的解集之有穷或无穷均是一个能行随机的（effectively random）算术事实。

这些无穷多的能行随机的算术事实的存在，表明了随机性即使在算术的领域内也相当基本，以至于我们甚至可以说“算术结构本身是随机的”。（pp.128）这进一步支持了“实验数学”和“拟经验数学”的观点——算术结构的随机性表明逻辑确定性在数学中是不能完全获得的，数学家并不总是能用逻辑手段解决问题。在必要的情况下，数学家应满足于像物理学家那样，通过做实验（包括使用计算机）来获得结果。这种关于数学实验的合法化观念为数学革命的到来提供了一个理论基础。

Further Reading

Hofstadter, D. Godel, Escher, Bach: An Eternal Golden Braid. New York: Basic Books, 1979.（第一本关于哥德尔定理的普及读物）

Rucker, R. Mind Tools. Boston: Houghton-Mifflin, 1987.（pp.136：“关于哥德尔工作的许多激动人心主题的讨论，……，外行人可读，极力推荐。”）