1.北京大学物理学院量子材料科学中心; 2.上海交通大学维尔切克量子中心 【摘要】 数学是抽象的,它使用的符号和概念，以及研究的对象可以完全和实际的物体无关。但是数学家和计算机都是物理的实体，受物理规律的约束。这个无法逃避的基本事实会影响数学的发展。通过仔细分析图灵机，本文指出图灵和他同时代科学家忽略了一个基本的物理可能，信息的载体可以是量子系统。这个疏忽使得他们提出的计算机模型只能处理经典信息，能力受到极大限制。哥德尔不完全定理则反映了这样一个事实：数学家和计算机是由有限多的原子和分子构成，他们只能从有限的假设或公理出发，利用有限的符号和字母，完成有限步的推导。因此即使加上未来所有的数学家和计算机，他们能证明的数学定理一定是可数无穷多的。但是世界上有不可数多的数学命题，这样总是存在很多数学命题你既无法证明也无法证伪。朗道尔(Landauer)曾经说，信息是物理的;在同样的意义上,数学是物理的。
关键词： 图灵机，量子计算机，对角论证法，动力学系统，哥德尔不完全定理，停机问题
数学虽然源自实际生活，但是人类很早就开始讨论纯粹的数字，没有大小的点，没有宽度的线和完美的圆，这些在现实世界中并不存在的对象。这种抽 象是非常有效的，它让数学摆脱了不重要细节的纠缠，变得更加深刻和锐利。现代科学和技术所依赖的数学知识和体系在19世纪末就已经基本完全建立.在这些成功的激励下，二十世纪初，以希尔伯特 (David Hilbert) 、怀特海德 (Alfred Whitehead) 和罗素 (Bertrand Russell) 为代表的数学家有了更大胆的想法，他们试图建立公理化的纯粹数学：所用的符号都只是符号，不代表任何实际的物体，甚至都不代表没有大小的点和没有宽度的线；所有的数学定理都可以从有限的公理出发，利用有限的逻辑规则，经过有限步推导出来。怀特海德和罗素合著的《数学原理》(Principia Mathematica)代表了这种努力和尝试。 哥德尔(Kurt Gödel)在1931年证明的不完全定理宣告这种努力是徒劳的 [1, 2] ，数学不可能被归纳成这样的一个公理体系， 总是存在不可能被证明的数学定理。哥德尔不完全定理是非常深刻的，激发了很多数学和哲学的讨论。在我看来，哥德尔定理反映了这样一个基本事实：任何数学定理的证明都是数学家或机器或数学家和机器完成的。数学家和机器都是有限的物理实体，他们只能从有限的假设或公理出发，利用有限的符号和逻辑规则，进行有限步的推导。因此所有的数学证明都可以用一个由有限多的字母和符号构成的有限长的字符串表达出来。这意味着，如果我们用Σ 代表一个集合，它包括过去和将来所有数学家和机器能完成的数学证明。那么集合Σ 有可数无穷多个元素。但是所有数学命题的集合 Ω 有不可数无穷多个元素，这样，我们无法在两个集合Σ 和Ω 之间建立一一对应关系，因此总是存在不可能被证明的数学命题。 1991年朗道尔(Rolf Landauer)在一篇题为《信息是物理的》文中提出了一个很基本的问题[3] ，“计算不可避免地是由真实的物理自由度完成的，它们遵守物理定律，利用我们现实物理宇宙中的可用的部件。这个事实对计算施加了怎样的限制呢？”哥德尔定理是对这个问题的一个回答，展示了物理是如何限制数学和计算的。这个定理表明，即使我们将来发展出来远远超越人类大脑的具有超级推理能力的计算机，我们也不能从有限的公理出发证明或证伪所有的数学命题。 上面的讨论表明物理会限制数学的发展，但是 物理也可以促进数学的发展。量子计算机[4,5] 就是这样一个例子。在量子力学出现以前，数学家就已经透彻地研究了希尔伯特空间及其相关的线性代数，但是他们并没有意识到希尔伯特空间中的向量可以描述一种新的信息，量子信息。它和经典信息有一个本质的不同，它无法通过一次性测量获得，是不可克隆的。这种认识无法来自纯粹的数学研究，只能来自物理。可以非常有信心地断言：如果没有量子力学，数学家永远也不可能发现量子信息。针对量子计算机，肖(Peter Shor)设计了一个独特的整数因子分解的算法[6] ，和最快的经典计算机上的算法相比，这个量子算法有指数的加快。这个例子告诉我们，这种由物理带来的新的认识可以极大扩展数学的范围和能力。 因此 ，数学虽然是抽象的，似乎完全可以脱离物理而发展，但是它后面其实蕴藏着一些非常基本的物理，并受到这些物理的影响。这种影响至少体现在两个方面。首先，数学和计算都是由有限物理实体(人或机器)完成，它们只能利用有限的物理资源。哥德尔定理反映了这种有限性带来的限制。其次，当数学对象,比如向量和矩阵，由物理实体实现时，它会获得超越纯数学的性质。量子信息及其相关的量子计算就是很好的例子：当希尔伯特空间中的向量通过具体的量子体系实现成为量子信息后，它便获得的不可克隆的性质。这个性质超越了纯数学。数学和物理的这样联系是本质的，忽略这个基本的联系既会让数学家进行一些徒劳的尝试也会让数学家失去扩展数学的机会。而承认这个联系则会进一步促进数学和物理的发展。呼应朗道尔的观点———信息是物理的[3] ，我们可以说数学是物理的。
下面我们通过分析图灵机和哥德尔定理来详细 阐述数学是物理的这个观点。但是由于篇幅的限制，本文将不会详细描述哥德尔定理的证明。由于这个证明最实质部分是康拓(Georg Cantor)的对角论证法，我们将通过分析康拓关于无理数的对角论证以及停机问题(halting problem)来解读哥德尔定理的证明和它的本质。本文是对作者以前观 点 [7] 的 补充和扩展。
图1 图灵机的示意图
1926年薛定谔 (Ewin Schrödinger) 发表了现在以他名字命名的 方程 [8] ，这标志着量子力学的完全建立。十一年以后，1937年，图灵 (A. M. Turing) 发 表了一篇论文[9] ，他 在文中描述了一个抽象的计算机,现在被称为图灵机。如图1所示,图灵机由一个读写头和一个半无限长的纸带(tape)构成：读写头所有可能的状态是一个有限的集合Q； 纸带被分成大小相等的小方块，每一个方块上的字符标记这个方块的状态，所有可能的字符被称为字母表S ，它也是一个有限的集合。空白是一个特殊的字符，表示方块上没有任何记录，是唯一一个可以在纸带上出现无穷多次的字符。当读写头停留在一个方块上时，它会读取方块上记录的数据，然后根据读取的数据并结合自己的状态决定是否改写该方块的数据、是否改变自己的状态、最后如何移动(左移一格,右移一格，或不移动)。一个图灵机就是一个程序P，它规定了读写头的初始位置和状态，以及一个由有限条规则构成的转换表。
图2展示了一个图灵机的例子。它读写头的初始位置在最左边的空格，状态是 q 0 。 它的转换表有三条规则，见表1。这个表中，“停”是指图灵机停止工作。
图2 一个图灵机的例子
初始时刻，图灵机的纸带上除了第1、2、4方格 是1，其他方格都是空白.按照表1中的规则，图灵机将从图2(a)的初始状态，逐步演化到图2(g)中的末态。整个过程可以解释为图灵机完成了2+1=3的运算(1代表1、11代表2、111代表3)，也可以解释为将两个字符串，“11”和“1”，合并为一个字符串“111”。 上面的介绍表明，图灵机是一个用于计算的理想化机械装置。虽然是一个机械装置，并且当时量子力学已经完全建立，但是当时没有人认为或意识到图灵机是一种局限于经典物理的计算机。相反，图灵和他同时代的科学家很快达成共识：图灵机是普 适的，也就是说任何其他计算机可以完成的计算图 灵机也可以完成。这就是著名的邱奇-图灵猜想 (Church-Turing thesis)。 后来大家甚至广泛接受了一个更强的邱奇-图灵猜想：任何其他计算机可以完成的计算图灵机也可以有效完成。“有效”的具体含义是：对于一个给定的计算任务，如果一个计算机,比如最快的现代计算机，需要n 步来完成,图灵机需要的步数正比于 n α (α ≥1)。现在已经众所周知，图灵机是一种局限于经典 物理的计算机，即经典计算机。下面我将分析一下为 什么图灵机是一个经典计算机。我们将看到这和用什么物理系统实现图灵机没有关系。假设有一个世界，它的力学不是牛顿力学而是亚里士多德力学， 即 力正比于速度 ,这个世界里构造的图灵机依然是经典计算机。 为了进一步阐述这个论点，我们需要先回顾一下什么是动力学系统，以及经典动力学系统和量子动力学系统的本质区别。
一个动力学系统由两部分构成：状态空间和演 化规则.给定初始条件后，这个系统会按照演化规则在状态空间运动，形成一条轨迹。对于一个经典粒子，它的状态空间是6维相空间，这个空间中的每一个点或向量 代表粒子的一个状态；粒子状态的演化规则是牛顿运动方程，
这里m 是粒子的质量， 是势能。对于一个量子粒子，它的状态空间是希尔伯特空间，其中的每一个向量|ψ >代表一个量子粒子的状态(简称量子态)。量子态的演化规则是薛定谔方程，
其中哈密顿算符 .注意，虽然 量子态|ψ >是一个在实空间弥散开的函数，即波函 数，但是在希尔伯特空间中|ψ >是一个点，它的变化在希尔伯特空间中形成一条轨迹。图灵机也是一个动力学系统。图灵机的状态空间是纸带所有可能的状态T ：每一个状态中除了空格，字母表中的任何一个字符只能出现有限多次。图2中7个纸带的情况对应图灵机状态空间中的7个点。图灵机的演化规则是转换表。下面的分析将告诉我们，由于图灵机的状态和经典粒子的状态都是可克隆的，而量子态一般是不可克隆的，所以图灵机是经典计算机。 从公式(1)和(2)可以看出，经典动力学和量子 动力学的数学形式非常不一样。这很容易造成一个错误的印象：经典力学和量子力学的本质区别来自于它们动力学方程数学形式上的差异。但深入分析以后，人们发现经典动力学和量子动力学在数学上其实是严格等价的，牛顿运动方程(1)和薛定谔方程(2)数学形式上的差别是表面的，不是实质。 人们发现薛定谔方程在数学上可以表达成一个 经典哈密顿系统[10] 。为了简单，我们考虑最简单的量子系统，单个自旋1/2。它的薛定谔方程是
这个系统的能量期待值是
我们把它看作两对共轭变量 的经典哈密顿量,并引入如下泊松括号
直接计算表明这两个运动方程和公式(3)完全相同。通过选取一套完备的正交归一基，我们总是可以把薛定谔方程(2)写成矩阵形式。因此对于任何量子体系，它的能量期待值总是可以表达成和公式(4)中 类似的形式。这样通过进一步引入共轭变量和泊松括号，我们最后总是可以将薛定谔方程写成经典哈密顿运动方程。与此形成对照和互补的是，库普曼 (Bernard Koopman) 在1931年和冯诺依曼 John von Neumann) 在1932年分别独立发现,经典动力学在数学上也可以用希尔伯特空间和算符描述。有兴趣的读者可以参见他们的论 文 [11,12] ,这 里不再介绍。 综上所述，从纯数学的角度看，经典动力学和量子动力学没有本质的区别。但是众所周知它们在物理上却有巨大的差别。那么这个差别来自于什么地方呢？在下一节我们将仔细分析对比两个系统：一维经典粒子和自旋1/2。分析表明，经典动力学系统的状态是经典信息，是可以克隆的；量子动力学系统的状态是量子信息，是不可以克隆的。这是经典系统和量子系统的本质区别，这种区别无法通过纯粹的数学研究发现。
对于一维经典粒子，它的状态空间是二维相空间，粒子的某个状态是这个空间中的一个点或向量X ，这个向量的两个分量分别是位置x 和动量p ，即X =(x,p )。自旋1/2的状态空间是二维希尔伯特空间，自旋的状态是这个空间中的一个点或向量。
我们设定|↑>代表自旋沿z 轴向上，|↓>代表自旋 沿z 轴向下。以这两个状态作为基，希尔伯特空间的一个向量或自旋1/2的状态可以写成
其中ϕ 1 ,ϕ 2 为向量的两个分量。虽然都是某个线性 空间中向量的分量，但是x,p 和ϕ 1 ,ϕ 2 x 和动量p 都是可以直接观测的。在理想情况下(即仪器无限精确，对被测物体的扰动无限小，没有任何噪声等等)，我们可以通过一次性测量，准确得到这个粒子的位置x 和动量p 。与此形成鲜明对照的是ϕ 1 ,ϕ 2 ϕ 1 | 2 的概率自旋向上，自旋态变为|↑>； |ϕ 2 | 2 的概率自旋向下，自旋态变为|↓>。这说明量子测量和经典测量有两个本质差别：(1)测量结果不确定；(2)测量结果不是希尔伯特空间中向量的分量ϕ 1 ,ϕ 2 ，而是基矢|↑>或|↓>。这就造成了一个有趣的局面，一方面ϕ 1 ,ϕ 2 完全确定了自旋的状态，另一方面我们却无法通过一次性测量得到它们的数值。为了得到ϕ 1 ,ϕ 2 的数值，我们必须进行多次测量，测量次数越多，精度越准。即使这样我们也只能得到|ϕ 1 | 2 , |ϕ 2 | 2 的数值。为了得到复数ϕ 1 ,ϕ 2 的相位，我们必须改成沿x 轴或y 轴进行多次测量。这和经典力学形成强烈对比：在经典力学中，x,p 完全确定粒子的状态，同时我们可以通过一次性测量准确地得到它们的数值。 上面描述的和测量相关的区别是纯物理的，是 不可能从数学得到的。可能有人会反对，认为 ϕ 1 ,ϕ 2 不能被直接测量是因为它们是复数。这是错误的。 对于一维经典粒子，我们也可以引入如下复数变量
它们显然满足泊松括号{a,a* }=i ，是一对共轭变 量。虽然a 是复数，由于其实部和虚部都可以直接测量，所以a 也是可以直接测量的。对于自旋，我们显式地写出ϕ 1 ,ϕ 2 的实部和虚部，即
将它们代入公式(3)就能得到一组只有实数的方程。 遗憾的是，实数变量ϕ 1r ,ϕ 1i ,ϕ 2r ,ϕ 2i 依然是不能直接测量的。总之，一个量是不是可以直接测量的是完全由物理决定的，和它的数学形式没有关系。
经典动力学变量x,p 是可以直接测量的，而量 子动力学变量ϕ 1 ,ϕ 2 是不可测量的。这种物理上的区别是非常深刻的。如果我们用D0 表示测量仪器测量前的状态，那么经典测量对应如下过程，
其中DX 表示测量后仪器的状态：粒子的状态X 被 精确地记录在仪器中。这实质上是一个复制或克隆过程：测量前，只有粒子具有X 描述的信息；测量后，仪器中也具有了X 的完整信息，世界上于是有了两份X 的信息。在量子测量中，我们没有办法一次性地得到ϕ 1， ϕ 2 ，也就是量子态|ψ >的信息,，这可以表示成
这表明量子测量不是一个克隆过程。我们现在知道在量子力学的框架内，克隆是不可能,，这就是不可克隆定理 [13,14] 。这些分析表明，经典粒子的状态是可克隆的，而以自旋态为代表的量子状态是不可克隆的。
图灵机的演化规则非常丰富，不同的图灵机具 有不同的演化规则。按照邱奇-图灵猜想，它可以完成任何计算任务。也就是说，我们可以设计两台图灵机：一台计算牛顿方程(1)，另外一台计算薛定谔方程(2)。所以从演化规则看，我们无法判断图灵机是经典动力学还是量子动力学。这和我们前面的分析一致：动力学方程的数学形式不是经典系统和量子系统的本质区别。 让我们转而考虑图灵机的状态空间，它由纸带上所有可能的记录T 组成，例如图2中展示的纸带情况对应这个空间的七个点。显然，通过一次性观测我们就能准确了解纸带的情况。这和读写头能一次性读取纸带方格上的字符是一致的。只需要将X 换成某个纸带记录tp ，公式(10)就能描述我们对纸带的观测。因此，纸带的记录tp 是可以克隆的，和经典力学中的状态 X =(x,p )一样。正是由于这个原因，图灵机是经典计算机，不是量子计算机。注意，计算薛定谔方程(2)的图灵机也是经典计算机，这和求解薛定谔方程的笔记本电脑依然是经典计算机一样。 上面的讨论表明信息分为两类：经典信息和量 子信息。经典信息是可以克隆的信息；量子信息是不可以克隆的信息。这和著名的不可克隆定理是一致的。任何直接处理经典信息的计算机是经典计算机；任何直接处理量子信息的计算机是量子计算机。图灵机直接处理的是经典信息，所以图灵机是经典计算机。这里“直接”二字很关键。前面已经提到，图灵机和通常的笔记本电脑都可以用来计算薛定谔方程，比如方程(3)。这时候，虽然图灵机和笔记本电脑处理的是由ϕ 1 ，ϕ 2 代表的量子信息，但是它们将ϕ 1 ，ϕ 2 代表的量子信息转化成了经典信息——四个实数——记录在图灵机的纸带或笔记本的内存中，可以被一次性读取(或测量)。因此图灵机或我们的笔记本电脑并没有“直接”处理由ϕ 1 ，ϕ 2 代表的量子信息。这和量子计算机形成鲜明的对照.在量子计算机中，ϕ 1 ，ϕ 2 被直接处理成一个量子比特的状态，而不是四个可以一次性读取的实数。后面我们会进一步讨论这个微妙而又深刻的区别。 图灵机是1937年提出的，那时候量子力学已经 完全建立十一年了。但是图灵和他同时代的科学家，以及后来的很多科学家显然没有意识到，图灵机以及其他类似的计算机模型后面隐藏着一个的假设：这些计算机或计算机模型直接处理的信息都是记录在可以直接观测的媒体上的，可以被一次性准确读取和复制。在日常生活中，信息都是记录在这样的媒体上，比如纸、胶片、声波、电磁波等。这种经验也正好和经典物理完全吻合：经典物理中粒子的状态和各类波的状态原则上都是可以通过一次准确观测而获得。由于我们对信息的这个性质太熟悉，以至于大家都没有意识到这个性质是和经典物理紧密相连。直到1980年和198年，前苏联数学家曼 宁(Yuri Manin) [15] 和美国物理学家费曼(Richard Feynman)[16] 才 分别意识到以图灵机为代表的计算机由于只能处理经典信息，它们在处理量子系统时会遇到原则性的困难。
我们用图灵机来演示这种原则性的困难。上面 提到，图灵机可以计算描述一个粒子运动的牛顿方程(1)。为了简单，我们假设粒子在一维空间运动。如果只有一个粒子，它的状态由两个变 量(x1 ，p1 )描述；如果有两个粒子，这时系统的状态由四个变量(x1， p1； x2 ，p2 )描述,即两个粒子的位置和动量。这时候，图灵机纸带上记录运动状态的数据长度比模拟一个粒子时增长了一倍。如果有三个粒子，系统的状态由6个变量(x1 ，p1 ；x2 ，p2 ；x3 ，p3 )描述 ，即三个粒子的位置和动量。这时候，图灵机纸带上记录运动状态的数据长度比模拟一个粒子时增长了两倍。 以此类推，如果有n 个粒子，系统的状态 是(x1 ，p1 ；x2 ，p2 ；…；xn ，pn )，这 时记录运动状态的数据长度是一个粒子时的n 倍。因此图灵机纸带上的数据长度和系统中的粒子数n 成正比。 当用图灵机计算描述一个自旋的薛定谔方程 (3)时，它的纸带需要记录ϕ 1 ，ϕ 2 ，等价于记录四个实数。如果有两个自旋，这时希尔伯特空间的维数是四，它的向量有四个分量，这时记录这个系统的状态需要八个实数。如果有三个自旋，希尔伯特空间的维数是八，这时记录这个系统的状态需要16个实数。以此类推，当系统有n 个自旋时，希尔伯特空间的 维数是 2 n ，这时记录这个系统的状态需要 2 n+1 个 实数。这说明图灵机纸带上数据的长度会随着自旋个数指数增长，即正比于 2 n 。虽然图灵机的纸带是半无限的，可以容下这么多数据，但是它的计算速度将指数减慢.。这有两方面的原因：(1)读写头每移动一步的时间是有限的；(2)读写头为了读取系统的状态需要在纸带上移动的距离会随n 指数增长，这样不算其他操作，仅仅读取数据的时间就会随n 指数增长。因此图灵机不能有效模拟多体量子系统。这就是曼宁和费曼意识到的原则性困难：在模拟多粒子量子体系时，经典计算机需要的存储空间会随粒子个数指数发散。显然，指数发散的根源是n 个自旋系统的量子态被处理成了经典信息，而不是直接处理成量子信息。如果将量子态处理成量子信息，直接用量子比特来表示这个多自旋系统的量子态，我们只需要n 个量子比特来“记录”n 个自旋系统的量子态，指数发散问题不再存在。这就是量子计算机的最大用处,有效模拟多体量子系统。 从上面的讨论可以总结出两个非常重要的结 论。首先,量子信息可以被处理成经典信息，但是付出的代价是昂贵的：像图灵机这样的经典计算机需要的存储空间会随系统的大小指数增长。其次，物理可以扩展数学的能力：基于量子力学构建的量子计算机能有效模拟量子多体系统。不但如此，进一步的研究表明，量子计算机还可以更快地解决一些我们熟悉的计算问题，比如整数因子分 解[6] 和随机搜索[17] 。这 里要强调量子计算机这类计算机模型的提出和数学是完全没有关系的。量子计算机依赖的数学，幺正矩阵和希尔伯特空间以及相关的数学，并不是新的数学。这些数学在量子力学建立以前就已经存在，并得到了深入的研究；但是没有人意识到可以 基于这些数学建立一类更强大的计算机模型，量子计算机。只有通过物理人们才发现了另外一类信息，量子信息。它不能通过一次性测量读取，不能克隆。无论怎样从数学角度研究希尔伯特空间，人们也不可能发现量子信息。数学上还有很多其他的线性空间，其中某一个线性空间非常可能在将来被用来描述另外一种新的信息。但是如果不结合新的物理，我们是无法知道这种信息具有什么新的特征，什么样的物理系统可以被用来直接存储这种新的信息。所以从这种意义上讲，数学是物理的。数学的发展不可能完全脱离现实，最终被归为一堆抽象符号之间的逻辑关系。量子计算机的出现表明，物理可以给数学赋予更丰富的内容，让它更加强大。 上面的讨论还给我们一个启示，如果能发现一 种新的信息，那么就可以构建一个直接处理这种信息的计算机模型。这种新的计算机模型很可能比量子计算机还强大。在文献 [18] 中，我和合作者就提出了这样一种新的信息，它不但不可以被克隆而且其 中有一部分信息是永远无法观测的，基于这种新的 信息，我们构建了一种新的计算机模型，洛伦兹量子计算机，其中的某些逻辑门是复数域上的洛伦兹变换。我们发现，这种计算机模型确实比量子计算机更强大。
前面关于计算机的讨论让我们看到，物理可以 扩展数学的范围和能力。而1931年提出的哥德尔不完全定理(简称哥德尔定理)则表明物理也可以限制数学的能力。哥德尔定理比较严格的数学表述是：任何基于有限个公理的形式理论无法证明所有关于自然数的真命题，也无法展示这个理论体系是自洽的。虽然哥德尔定理的严格表述只涉及关于自然数的命题，但是现在人们已经普遍接受了一个更普适的表述：在任何一个有限公理体系里存在不可证明或证伪的数学命题。哥德尔定理经常给人神秘的感觉，但是它实质上反映了这样一个基本事实：数学命题虽然可以超越物理，和物理没有任何关系，但是它们的证明是通过人或机器完成的。一方面，任何人或机器只能使用有限多的字符，掌握有限多的方法，进行有限步的推导，所以所有人和机器能证明或证伪的数学命题的数量一定是可数的。即使宇宙永远存在， 人类能一直生存下去，这样人类自己或借助机器能证明或证伪的数学命题是无穷多的，但一定是可数无穷多，即等价于整数的个数。另外一方面，数学命题的个数是不可数无穷多，即等价于实数的个数。因此我们无法在两个集合，所有人类可以证明的数学命题Σ 和所有的数学命题Ω ，之间建立一一对应关系，这样总是有数学命题不可证明或证伪。由于篇幅的限制，我们这里无法详细讨论哥德尔定理的证明，有兴趣的读者可以哥德尔的原始论文 [1] 或者文献 [2] 。我们将介绍康拓(Cantor)关于无理数的对角论证法，然后基于这个方法并结合停机问题 (halting problem)来阐释哥德尔定理的实质。
1891年德国数学家康拓证明了实数的个数要多于整数的个数,是不可数的。不但 这 个结论非常重要，而且康拓采用的对角论证法也影响深刻，哥德尔正是使用了这个方法来证明他的定理。下面介绍对角论证法。首先，我们可以只考虑开区间(0，1)上所有的实数。如果这个区间上的实数比整数多，那么所有的实数就比整数多。康拓采用了证法，他先假设(0，1)上所有实数的个数和整数一样多，那么所有这些实数就可以标记为r1 ，r2， r3， …，rn ,…. 如果将这些实数用二进制表示，忽略小数点和它前面的零,只保留小数点后面的数字,那么我们会得到下面这个矩阵
现在将上面矩阵中对角元进行0和1之间的转换得到一个新的实数
这个实数显然和上面矩阵中列出的所有实数都不一 样，因为它小数点后第n 位数字和rn 的第n 位数字 正好相反。但是根据假设，上面的矩阵已经列出了所有的实数。矛盾。因此假设是错误的，开区间(0，1)上实数的个数比所有的整数多，不能被整数标记从而列在上面的矩阵中。这就证明了实数是不可数的。由于有理数是可数的，这同时也证明了无理数是不可数的。 利用上面的证明我们立刻可以得到一个推论： 不可能建立一个只有有限个字符的字母表，用这个字母表中所有的字符将每一个实数表达成一个有限长的字符串。在二进制下，任何一个整数都可以用‘0，1，一’这三个字符表达出来,并且字符串的长度是有限的，比如11和-1011。同样在二进制下，任何一个有理数都可以用‘0，1，一，/’这四个字符表达出来，并且字符串的长度是有限的，比如-11/10和101/11。但是对于实数，这是无法做到的。对于某些实数，尽管在十进制下它们需要用一个无穷长的字符串表达，但是我们可以通过引入新的字符，把它们表达成有限长的字符串。比如通过在字母表中引入三个新的字符‘(,)，∧ ’, 即左右圆括号和上尖号，我们可以把无理数 表达成 3∧ (1/2)， 这个字符串的长度是7。还有很多无理数，比如 5 1/3 也 可以用这些字符表达成有限长的字符串。但是利用这个扩大的字母表还是不能将任意一个无理数表达成一个有限长的字符串，比如π 就不行。我们当然可以进一步扩大字母表，比如直接加入π，把更多的无理数用有限长字符串表达出来，比如 表达成π∧ (1/2)。但是依然有很多无理数无法用有限长的字符串表达，比如lnπ .事实上，利用一个有限大的字母表，我们永远也无法把任意一个无理数表达成有限长的字符串。我们用反证法，假设可以用一个有限大的字母表，把任意一个无理数表达成有限长的字符串。那么我们将字母表中所有的字符表达成一个二进制整数，就像在计算机里一样。这样每一个无理数就表达成了一个有限大的整数，这时按照大小排列起来就可以和自然数形成一一对应。由于无理数是不可数的，这是不可能的，因此假设错误。我们不可能用一个有限大的字母表，把任意一个无理数表达成有限长的字符串。这个结论看上去似乎很明显，但是非常深刻。事实上，对于任何一个具有不可数无穷多元素的集合，我们有类似的结论：不可能建立一个有限大的字母表，将这个集合中任意一个元素表达为有限长的字符串.在下面的讨论中我们将用到这个结论。 现在我们考虑集合Σ ，所有的数学证明。这个 集合Σ 既包括已经存在的所有数学证明，也包括在无穷长的未来会发现和完成的更多的数学证明。我们以上面康拓的论证为例来看一下数学证明的特点。康拓先假设实数是可数的，那么根据已有的数学知识，可数的集合总是可以用自然数来标记。这意味着可以把所有的实数记为一个无穷数 列r1， r2， r3 …，rn ,…. 康 拓对这个数列进行了一个创新的操作，利用它们构建了公式(12)中的矩阵，最后借助这个矩阵的对角元构建出一个新的实数 ，和最初的假设矛盾。于是证明了实数是不可数的。这个证明有一个非常有趣的特征：虽然证明过程中涉及了一个无穷维的矩阵(12)，但是证明的总长度依然是有限的。这是因为康拓在证明中并不需要知道每一个实数的细节，比如第二个实数r2 第一百万位是0还是1。这些细节和证明无关。康拓只在意实数的一个基本特征：每一个实数都可以表达成这样一个由0和1构成的有限长或无限长的字符串。这个特征可以保证构建出来的新数 实 数。换句话说，康拓关心的实数的特征只需要有限长的字符就能表达。类似的情况出现在很多数学证明中：虽然考察的对象是一个不可数集合，但是证明并不关心集合中 每一个元素的细节，而只关心这个集合一些普遍的 特征，这些特征只需要用有限长的字符来描述。 基于上面的讨论，我们有这样的结论：每一个数 学证明的长度都是有限，即一个有限长的字符串。数学证明中用的字母表包含所用语言中所有的文字(如果是英文，那就是26个英文字母以及其标点符号)和数学中所有的符号，这个字母表的长度显然也是有限的。根据我们上面的结论，包含所有的数学证明的集合Σ 是一个可数无穷集合。这个结论实质上反映了这样一个基本的物理事实。任何一个数学证明都是数学家，或者计算机，或者数学家和计算机完成；而每一个数学家或机器都是一个有限物理实体，他们只能使用有限的字母和符号,掌握或具备有限的变换方式和操作，进行有限步的推导。 我们考虑另外一个集合Ω ，所有的数学命题。这 个集合显然有无穷多个元素，但是是不可数的。这个结论不是很明显因为每一个数学命题似乎也是一个有限长的字符串，而且使用的字母表也是有限大的。 事实不是这样。比如，我们可以针对每一个实数设 置一个数学命题，而且该数学命题和每一个实数的细节相关，这就会给我们不可数无穷多个数学 命题。下面是一个具体的例子。如果一个数x 的所有数字可以按次序在π 中找到，那么我们说这个数x可以嵌入π。比如x=1.234567可以嵌入π，
R (n) (x) 被定义为一个操作，它将x 的每一个数字重复n 次。比如， R (1) (23456)=23456， R (3) (1.36)=111.333666。对于每一个实数x 和每一个自然数n， 我们可以设立一个数学命题 E (n) (x)：R (n) (x) 可以嵌入π⁽⁷⁾ 。这样我们就有了不可数无穷多个数学命题。 由于所有数学命题的集合Ω 具有不可数无穷 多个元素，而所有数学证明的集 合Σ 是可数无穷多，因此我们不可能建立这两个集合之间的一一对应，Ω 中总是有命题无法被证明或证伪，而且这样的命题有无穷多个。注意，对于任何一个错的命题，它的否命题是对的，因此证明和证伪是等价的。 前面关于π 的嵌入命题E(n) (x) 中应该有很多 这样的无法证明同时也无法证伪的命题。比如命题E(1) ( )非常可能是真的，但是要证明它似乎是不可能的，因为我们需要对比两个无穷长且没有规律的数字序列，而人类的大脑和任何计算机只能记录 下有限长的数字序列。另外一方面，我们也不能完全 排除证伪这个命题的可能性。如果通过某种方法我们发现π 的小数点第2200 位以后就不再出现数字9，而 的小数点后第2200 位或更高位会出现9，那么命题E(1) ( )就是错的。 总结一下。上面的讨论清晰地表明：由于数学家 或计算机都是有限的物理实体，只能使用有限的字母或符号，掌握或具备有限的变换方式和操作，进行有限步的推导，因而总是存在很多数学命题数学家既无法证明也无法证伪。因此，数学是物理的，它不 可能超越研究数学的人是一个有限的物理实体这样 一个基本事实。只是这一次,，物理在某种意义上限制 了数学，而量子计算机则是扩展和加强了数学。这个结论也有积极的一面：数学家永远不会失业。 上面的讨论不是特别严谨，但反映了哥德尔定 理的实质。为了让上面的讨论严格，哥德尔非常有创意地将所有数学表述编码在自然数中，这些数学表述既包括1=1这样的数学公式也包括“x是一个实数”这样的元数学(meta-mathematical)表述。最后哥德尔利用康拓的对角论证法证明了现在以他名 字命名的定理，哥德尔不完全定理。由于篇幅的限制，我们这里就不详细介绍哥德尔定理的证明。有兴趣的读者当然可以去阅读哥德尔的原始论 文 [1] 或者后来的解读[2] 。 非常 有趣的是，图灵从计算机的角度研究了这个问题，提出了一个与之等价的停机问题(halting problem)[5,9] 。对于一个特定的输入，某个程序 可能在完成计算后停机也可能陷入死循环。停机问题是这样表述的：是否存在一个程序 ,它能够在有限 时间内判断任意程序 循环。
我们考虑一类特殊的程序，它们的输入是正整 数。这类程序构成一个集合 中的任意程序m 最后会停机还是陷入死循环。集合m 是否会停机还是陷入死循环实质上是一个数学命题。如果集合 我们进一步设定,如果 对于整数输入m 会停机，那么程序 如果 对于整数输入m 会死循环，那么程序 这些输出 个矩阵，利用对角证法，我们构建一个程序 ,它对 于输入n 停机如果 ;它对于输入n 陷入死循环如果 这个程序 这和前面的假设，序列 已经包含了集合 这个证法和通常见到的证法[5] 有些不同，但本 质是一样的。通过本文的证法，更容易透过那层神秘的面纱，看清停机问题的本质：无法判断任意程序是否停机的根本原因是程序的个数是不可数无穷多。这和我们无法证明或证伪所有的数学命题是等价的。由于原则上每一个程序都可以用一台图灵机完成，停机问题也可以表述成这样：不存在一个图灵机，它能判断其它图灵机是否会停机。
伽利略在他的著作《试金者》中写道[19] ，“宇宙 是一本敞开的任人翻阅的大书。去理解其中的哲学，你必须先学会它的语言。这本书的语言是数学，它所用的字符是三角形、圆和其他几何图形。不懂这些，你不能理解书中任何一个字，只能在黑暗的迷宫中徘徊。”伽利略说的“哲学”指的是现在的科学或者，更具体一些，物理。伽利略的这段话是非常大胆和有远见的，因为那时还只有很少的物理现象，比如自由落体和单摆，可以用数学精确描述.后来物理的发展印证了伽利略的远见，数学成为物理不可缺少的一部分。数学不但是物理学家描述宇宙的语言,在很多方面也深刻影响了物理学家思考问题的方式。理论物理学家会毫不犹豫地讨论很多理想化的情况，比如没有大小的质点,没有噪声的思想实验。
反过来，物理也影响了数学，为数学提供了思考 的素材和启迪，比如流体力学方程和统计力学模型。哥德尔定理和量子计算机体现的物理对数学的影响则更加基本，是原则性的。它们反映的是这样一个基本事实：数学是人脑或机器等有限物理实体的产物。哥德尔定理表明这些物理载体会对数学产生某种限制；量子计算机则表明，物理载体会给数学对象赋予额外的性质,从而扩展数学的范围和能力。 可以相当有信心地预言，这种原则性的影响在 将来依然会出现，而且会以更多样的形式出现。一方面，在未来，人类可能会设计出一种新型的计算机，它会模拟大脑在自然界的进化，不断优化自己，最后经过上百年甚至上千年的演化获得比人类大脑更发达的智能。这个新的计算机能证明很多人类无法证明的数学命题，发现很多崭新的数学关系。人的大脑甚至不能理解这些新的数学，正如现在绝大多数的人无法理解顶尖数学家发现的新数学。 在另外一方面，物理学家在未来的研究中，比如 在统一引力和量子力学的努力中，得到一个全新的动力学系统。可以预见，类似于量子动力学赋予了希尔伯特空间新的内涵一样，这个动力学系统即使用的是成熟的数学，它也会给这些成熟的数学赋予新的内涵，给我们带来一类新的信息。而基于这种新信息的计算机将更加强大，能解决以前解决不了的疑难问题。在文 献 [18] ，我 们就指出了一种可能的新的信息，构建了一种 新 的计算机模型,它确实比量子计算机还要强大。 一 只翱翔的雄鹰，很多时候它似乎完全克服了那无形的引力，在无拘无束地飞行；但事实是，它永远也无法彻底摆脱引力的影响。数学就是一只雄鹰，很多情况下可以脱离物理发展，但是它无法完全和彻底地超越物理而独立前进。朗道尔曾经说，信息是 物理的;我们对此的呼应是,数学是物理的。 [1] K.Gödel,Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I, Monatsheftefür Mathematik und Physik,38,pp.173-198(1931). [2] E. Nagel and J. R.Newman,Gödel’s Proof,revised ed. (New York University Press,New York),2001. [3] R. Landauer, Information Is Physical, Physics Today 44(5), 23(1991). [4] 吴飙,《简明量子力学》(第九章)(北京大学出版社,2020). [5] M.A.Nielsen and I. L.Chuang, Quantum Computation and Quantum Information (Cambridge University Press,Cam bridge,UK,2000). [6] P.W.Shor,Algorithms for quantum computation:discrete logarithms and f actoring,Proceedings of the 35th AnnualSym posium on Foundations of Computer Science, 124-134 (1994). [7] Biao Wu,Classical Computer, Quantum Computer,and the Gödel’s Theorem, arXiv: 2106.05189 (2021); 收入在 Frank Wilczek,50 years of theoretical physics (World Scientific, 2022),pp.281-290,edited by A.Niemi,K.K.Phua,and A.Shapere. [8] E. Schrödinger,Quantisierung als Eigenwertproblem (Erste Mitteilung) [English translation: Quantisation as an Eigenvalue Problem (First Communication)],Annalen der Physik,79361-376(1926). [9]A.M.Turing,On Computable Numbers,with an Applicati on to the Entscheidungsproblem,Proceedings of the London Mathematical Society,s2-42,230(1937). [10] A.Heslot,Physical Review D31,1341(1985). [11] B.O.Koopman, Proc. Natl. Acad. Sci.U.S.A.17,315 (1931). [12] J.von Neumann, Ann. Math.33,587(1932);ibid.33,789 (1932). [13] J.L.Park,Foundations of Physics 1,23(1970). [14] W.K.Wootters and W.H.Zurek,Nature 299,802(1982). [15] Y.I.Manin,Computable and Noncomputable,(Sov.Radio., 1980)in Russian. [16] R.P.Feynman,International Journal of Theoretical Physics, 21,467(1982). [17] L.K.Grover , Phys. Rev.Lett.79,325(1997). [18] W.He,Z.Wang, and B.Wu,Chinese Physics B 32,040304 (2023); arXiv: 2103. 10315 (2021). [19] G.Galilei , The Assayer (University of Pennsylvania Press, USA,1960). 蔻享学术 平台 介 绍
蔻享学术平台，国内领先的一站式科学资源共享平台，依托国内外一流科研院所、高等院校和企业的科研力量，聚焦前沿科学，以优化科研创新环境、传播和服务科学、促进学科交叉融合为宗旨，打造优质学术资源的共享数据平台。
识别二维码，
下载 蔻享APP 查看 最新资源数据。