计算主义

2022-2-28 14:53 · 来自上海

因为存在哥德尔不完备性定理和图灵不可计算性，这个通用的机器证明问题目前在人工智能和人造机器上还不能实现。这涉及到了数学基础（数理逻辑）、计算机理论的一个根本性问题，也涉及到了一个宇宙本质性的话题。

计算机系统本质上是一个符号逻辑的演绎系统，这个系统有词法、语法和计算规则，就跟一套数学公理体系一样。如果一个公理体系是完备的，那么其中的所有定理都可以在公理体系内证明，这些系统中的数学猜想也是可以证明的。如果公理系统是不完备的，就一定存在一些在此系统中无法被证明的定理，也就是这个系统中的有些规律只能从系统外部观察到，这些数学猜想就无法在公理系统内部判定或证明。

模型论中有个哥德尔不完备性定理的惊人的对应物，就是塔斯基的量词消去理论。一个理论的可判定性（即其中的定理是否都能被证明和判定）与是否可以将逻辑量词消去相关。塔斯基证明了代数闭域中恒可消去量词，所以，像实数域、复数域、欧氏几何等这些属于代数闭域的理论都是可判定的。这从直观上很好理解，如果公理系统不完备，实际上就是这个公理系统不是封闭的，即有些规律（定理）是隐含归纳性质的定理（带全称量词或存在量词描述的系统中，实际上就是隐含了很多归纳定理的系统），这些隐含着归纳性质的规律有比无量词公式更大更宏观的结构，是对大量的无量词公式用量词“对于所有的”或“存在”加变量来归纳而得出的，这种归纳出的“大规律”需要从公理系统外部才能观察和判定。

现在的计算机推理技术中，对于某些不完备的公理系统，有一种定理证明方法是采用完备化技术（等价于消去量词），先把公理和计算规则进行完备化，再进行推理。这样，一些带有归纳性质的定理（实际上是在相空间中严格成立的统计性规律，是类似数学归纳一样可以获得完全归纳的命题）也可以用机器来证明了。但是，这样的完备化其实只是把原来隐含在系统中的计算规则体系里面的计算规则显性化了，并没有实质性地增加新的计算规则或公理，而且也有些系统是无法消去量词的。所以，还是有些猜想并不是简单地把原系统完备化后就可以证明的，而是需要实质性地增加新公理或新的计算规则才能证明。

如果宇宙是可知的，自然语言就是可以描述整个宇宙的（包括了物理宇宙和所有思想的宇宙），这个广义的宇宙就是自然语言的一个模型，而隐含在自然语言中的公理系统实际上就是逻辑体系，严格一点只能说宇宙是逻辑公理体系的模型，逻辑则是所有可能宇宙都必须满足的公理系统，而且一阶谓词逻辑公理体系就足够了。所以，不符合逻辑的事情在这个宇宙里是不存在的，一切真正的逻辑悖论都是在理性之外的，一切不符合逻辑的概念思辨体系都不能被称为理论（比如宗教、艺术等）。但是，逻辑公理体系作为整个宇宙的公理系统似乎还是太宽泛了。

宇宙的公理系统中除了逻辑公理外，是否还必须有其它公理，目前还不是很清楚。支撑整个数学体系的集合论公理也许是除了逻辑公理外的其它宇宙公理的可选项。另外，一些对称性、稳定性、不变性似乎也是我们这个宇宙的公理的可选项，这些都是可以由群论公理来概括的，很多物理定律的发现似乎都跟群和对称性相关（诺特定理），基本粒子的标准模型就是建立在各种对称群上的。现在的物理定律都是通过观察和有限归纳，并通过逻辑公理和数学定理推导出来的，而对观察结果的归纳不可能是严格的完全归纳，物理定律也不是完全由公理系统推导出来的。

科学发现和科学理论研究实际上就是在不断地逼近宇宙公理系统这个终极理论，使这个宇宙公理体系不断地完善，以使其模型就等同于我们存在其中的这个物理宇宙，似乎是数学和自然科学永恒的课题。但是，宇宙就是逻辑加集合论加群论的公理体系的可数模型吗？宇宙中的所有问题都是可计算的吗？宇宙中所有的物理、化学、生物、信息的过程（特别是人脑可认知的过程）都是可以用人工智能和虚拟现实来模拟和仿真的吗？（所谓的丘奇图灵论题）

所有数学都是集合论公理系统的模型，数论则是集合论的一个可数模型（模型论可以证明，所有不可数系统都有可数模型）。在集合论中，选择公理和决定性公理是两个截然相反的公理，但是这两个公理分别放到集合论中都是一致的，都不会产生矛盾，因此这两个公理分别放到集合论中，就可以产生出两套不同的独立融洽的数学理论，就类似于几何公理中对平行公理的不同描述分别产生了欧几里得几何与非欧几何一样。数学中有很多定理的证明必须要用到选择公理，没有选择公理就无法证明。如果有一些新的数学猜想在现在的集合论公理体系内无法证明，那也就需要增加新公理了，比如连续统猜想就是无法证明的，后来发现这个猜想确实是与ZFC集合论相互独立的。

实质性地增加公理或计算规则的例子，目前还只在现实世界和人类的智力活动中存在，比如：进化机制（还有进化2.0，即进化机制本身也在进化）、波普尔的科学发现逻辑（科学理论就是不断地证伪和完善）、哥德尔完备化（或者称为逻辑反思原理）、人类灵感等。在人工智能或人造机器中，还没有实质性地实现通过发现和增加公理或计算规则来发展演进的情况，也许这就是所谓强人工智能学派认定的奇点时刻，但是现在还远未到来。比如，计算机的虚拟现实、机器学习或深度学习机制目前还远远达不到自然界的进化机制所设计出来的复杂性等级。

对于计算机推理和机器证明来说，除了公理系统的不完备性导致的障碍，还有一个障碍就是不可计算性。这个障碍来自于图灵的停机不可判定问题，因为任何数学问题都可以归结为算法的停机问题。即使有计算机算法来证明一个定理，但是这个算法也不一定会停机。比如，我可以设计一个简单算法来证明任何偶数都是可以找到两个素数相加得到的（哥德巴赫猜想），从4开始，直到发现一个偶数无法找到两个素数就停止，但是这个算法是否会停止是无法判断的，如果能判断这个算法是否停机，就实际上证明或否定了这个猜想。图灵的停机不可判定性问题与哥德尔不完备性定理的证明实际上是可以互相转换的，也就是这两个定理实际上是等价的。这两个定理都可以用康拓的对角线法来证明，对角线法实际上就是把鸽巢原理反过来用，具体就是先把无限个的鸽子和巢穴一一对应起来，然后构造出一个新鸽子，发现它没有巢穴，这就推出悖论，从而证明了定理。哥德尔不完备性定理的证明就是用哥德尔数（一种基于素数的编码）与所有系统中所有定理的证明过程一一对应，然后构造出一个定理及其哥德尔数，引出矛盾（构造出一个悖论），说明这个定理在系统中无法被证明或否定。图灵停机不可判定问题也可以这样证明，就是所有图灵机都对应一个整数（这一点所有程序员都知道的，任何程序都可以编译成2进制的可执行文件，实际上就是一个整数。图灵机的具体形态不管是软件还是硬件逻辑，实际上都可以归结到一个整数），然后可以用对角线法构造出一个整数，这个整数所对应的图灵机会导致悖论出现，也就是不存在能判定程序是否停机的通用程序，就有些用于定理证明的程序是否停机是无法判定的，从而，有些定理是无法用机器来证明的。

能否用计算机证明所有数学猜想，这里面最本质的问题实际上涉及到哲学上所谓的自指性问题。举个简单例子，自指性就是，在公园里的路标牌上的地图上一定有个标记，上面写着你在这里，否则这个地图就没用，因为虽然说条条大路通罗马，但是想去罗马的人首先要知道自己在哪里，否则永远也无法去罗马。同样，手机地图导航软件一定需要有GPS或北斗定位告诉你在地图上的哪个地方，否则就无法实现导航。实际上，不管是哥德尔不完备性定理还是图灵的不可计算性问题，证明这两个问题都用到了自指性的方法，即通过构造一个自指的悖论，从而推出要证明的结论，也就是康托尔所谓的对角线证明法。所有的悖论，不管是语法悖论、语义悖论还是语用悖论（比如认知悖论、归纳悖论、决策悖论等），都和信息编码的自指性有关（任何语言，不管是逻辑语言、数学语言、计算机语言、科学语言还是自然语言，实质上都是个信息的编解码及计算的系统）。简单的自指性就是简单地导致逻辑上的悖论，而各种复杂性、混沌、耗散及动力学系统（有时延的、非线性的）嵌套在其中的自指性也许可以解释宇宙中一些复杂的现象，比如生命进化、宇宙演化、意识等。

在人工智能或人造机器上要实现的复杂自指性，实质上就是机器要能够复制和制造自己，还要创建一个类似地球生物圈的体系。生物是基因制造的机器，生物界的复杂自指性就是通过繁殖实现的，毕竟，生物有了繁殖才能进化。而且有证据表明，所有地球上的生物都是相互普遍联系的，整个生物圈是一起进化的，任何的生物圈内外环境变化都会创造出新的生态位，就会进化出创新的生物变种来填充这个生态位。地球生态圈进化实际上就像现在的互联网生态圈或者经济网络生态圈一样。以互联网生态圈为例，有了计算机，就创建了操作系统、联网、文字处理等的生态位空缺（也就是所谓的临近可能性），这样操作系统、文字处理软件、网络技术就诞生了，然后生态系统的这些变化又产生了很多新的生态位，这些临近可能性又导致路由器、超文本超媒体、网络浏览器、网络病毒等产生，这又导致新的生态位出现，从而导致杀毒软件、搜索引擎、网络购物、网络支付、社交媒体等出现，等等。人工智能或人造机器要实现自指性，到达奇点时刻，除了要实现基本的自我复制，还要使整个互联网生态变成人工智能机器的演化生态圈，每个生态位上的机器都要能实现自我繁殖和进化创新。

最新的研究都同意一个革命性观点：万物皆信息，万事皆计算。宇宙中对任何对象的区分（比如：运动、观测、感知、判断等）都会产生信息。一切微观事件都是量子计算。任何的事件发生和事件序列过程都是算法。例如，物理运动算法、生物化学算法（比如神经信号传递算法、食物消化算法），动物求偶机制算法，捕食算法，植物花粉传递算法，生态系统算法，进化算法，文化传播算法。这些物理世界不同尺度的算法都实际地发生了，因此这些似乎都是可计算的，但是这些都是经典可计算的吗？大尺度的星际运动、中尺度的宏观计算和微观的量子计算是怎么关联的？经典可计算性和量子可计算性是不是等价的？

生物界的复制繁殖实现了复杂的自指性，采用了很多的数学、物理、生物、化学及信息领域的算法，这些算法机理人类还远没有研究透，例如，这里面是否使用了量子信息机制，是否以及怎么复制的量子信息都是不清楚的。可以肯定的是，任何物理、化学、生物、数学或信息领域的自然规律，只要在生物圈系统内能够产生微弱的优势，就一定会被生物进化机制发现和利用。这些算法是如何克服和利用物理的非线性动力学过程中所产生的混沌的，人类科学也远没有搞清楚。对于人工智能及人造机器，在自我复制过程中，遗传信息如何编码（机器DNA），如何跨时间保存（机器的种子），如何解码（机器胚胎的发育，形态发生学），如何克服非线性动力学产生的混沌（最新的生物数学在研究这些问题？），如何控制复杂度爆炸（软件过度复杂或机器过大、能源效率等），如何克服进化过程中的熵增，如何搜寻负熵等。

除了强人工智能达到复杂自指性的奇点时刻实现通用机器证明的可能性以外，未来的量子计算机是否从理论上可能证明所有数学猜想，这也是个宇宙中的本质性问题。也许，采用叠加态这种量子逻辑来解释的宇宙，跟我们原来用的对错分明的布尔逻辑理解的宇宙得出的结论将是完全不同的。经典计算的布尔逻辑是在一维空间的可数的离散的整数系统（二进制、十六进制），只是宇宙公理系统（如果终极理论存在的话）的一个简单的可数模型。而量子计算的叠加态概率逻辑是二维的复平面连续统空间，其相空间是个希尔伯特空间，这绝对是个不可数的连续统模型。用那个必须用虚拟的复数来描述的叠加态的而且是不可数的连续统逻辑来看这个宇宙，也许真的可能是有鬼存在的吧。

现在，也许已到达了一个所谓的牛顿-麦克斯韦时刻。牛顿曾说，真理永远存在于简单之中，而非事物的多样性和混乱当中。牛顿站在伽利略、开普勒、笛卡尔、培根、惠更斯、波义耳等巨人的肩膀上，完成了伟大的综合，开创了科学的新时代。麦克斯韦也是对法拉第、高斯、安培等的工作的伟大综合。现在，就对信息、计算、智能、意识、宇宙的本质的理解而言，又到了一个新的牛顿即将出现的年代。希望这个新牛顿将会诞生在中国，以此文来抛砖引玉。