陈晓华 谭浩：终极算法无法超越哥德尔不完全性定理

哥德尔不完全性定理被誉为“逻辑和数学史上的一座里程碑”。由它产生的对“可证明”与“真”的讨论，直到图灵所产生的“可计算”与“不可计算”的讨论，再到如今“计算”与“超计算”、“可计算”与“可学习”的讨论，构成了对心灵、智能研究的一条线索。佩德罗·多明戈斯《终极算法》一书提出的“终极算法”理想，对于解决上述主题的问题提供了一定的思路。

哥德尔不完全性定理视域下早期人工智能的局限性

基于哥德尔不完全性定理的推论，可以得出形式算数本身的不可判定，即给定在形式算数中任意的公式，不存在统一的递归方法来确定它是不是其中的定理或者它是否恒真。在这里，形式算数指初等数论的递归形式化，包括此形式化的形式系统都存在不完全性。

早期的人工智能基于物理符号系统假设，一是任意合理的物理符号系统可以充分地获取智能，二是表现一般智能的主体都必须是物理符号系统的一个实例。也就是说物理系统表现一般智能行为的充分必要条件是一个物理符号系统，这也是人工智能符号学派建立的基础。由此看出，无论对于机器的计算还是人工智能的构建来说，如果包含了初等数论，由于形式化方法原则，它们都要受到哥德尔不完全性定理的制约。也就是说，从符号学派的观点，哥德尔不完全性定理所引发的人工智能的局限性在于人工智能的不完全性。

当前机器学习对人工智能局限性的解答

不可计算问题类的存在，同样也表明人对于此类问题的不可计算。一方面，人类对于不可计算问题的真的确认，可能可以不通过计算的方式到达；另一方面，以上所讲的计算都属于递归计算问题，可能可以找到超越递归计算的计算方法。而对于人工智能而言，物理符号系统假定所展示的智能可计算观点及其局限，或许可以从以上两个方面突破。

机器学习作为当前人工智能研究的热门内容，已经在某些方面突破了固有的局限。连接学派通过模拟生物神经网络来构建人工智能的神经网络系统，通过正向传播算法来获取神经网络每一个神经元的激励节点的值，通过反向传播算法来获取每个激励节点的值的平均误差的下降梯度，通过梯度下降算法来获取每个节点的最优参数（使平均误差最小），最后这一切在最终输出神经元的带领下以获得输出函数的值。输出函数在输入数据作为训练用例的基础上，通过以上方法成为一个能正确预测未知数据的函数，它并不完全依赖于对明确推理和描述世界的符号的预解释。人工智能中的知识不在特定符号中而在整个神经网络的参数中，物理符号系统所假设的知识到符号的必要性映射，在这里就行不通了，因为知识到神经网络参数的映射有可能一对多，也就是说对网络中的参数可以有不同的解释。

神经网络超越物理符号系统假设是可能的，但是它没有在实质意义上超越图灵计算的局限。智能等同于计算，而计算已经不仅仅是图灵计算而是超计算的问题。但是在现实物理世界中，在超计算的指导下制造出来的计算机没有一个能超越通用图灵机。而在超越图灵计算的意义上，自然计算指导下的进化学派从进化论的观点获得启示，主要利用的是遗传算法的涌现模型。遗传算法把问题的候选解决方案之间的关系看作竞争关系，而不是简单组合陈列；通过适应函数评估决定是否对下一代方案的形成作出贡献；最后通过类似染色体基因转换的方法，产生下一代候选解。这是一种对于多个主体间的交互机制的最简单的表达。而涌现模型也探讨单个主体内的达尔文自然选择机制。最简单的表达是细胞自动机，即细胞的下一状态是前一状态和输入数据的函数。显然，已有的状态会产生新的状态，新的状态会产生另一个新的状态，直到无尽。但是如果我们加入适应函数来评估它，单个主体也会受到进化的限制。以上两者加一块便是我们想要的基于遗传与涌现的社会智能模型，在模型中主体自身进化、主体间的交互都受到自然选择机制约束。自然选择机制，不是说它们都按照全局优化的目标去做，而是说在不同的各自目标下，以类似社会的方式涌现智能。

当前机器学习对于上述局限的回答还不尽如人意，却已经产生了新的问题。PAC（probably approximately correct）学习理论表明，对机器可学习的定义不像图灵可计算那样是由算法定义的，而指由从合理数量的训练数据中通过合理的计算量可靠地学习到知识。PAC更是指出机器学习存在训练数据不是非典型的概率和算法找到符合要求的知识的概率，它们之间在机器学习得以成功的概率关系就被称之为“可能近似正确”（PAC）学习理论。这表明，一方面，机器学习如果要达到超越图灵计算的效果可能只是近似的结果；另一方面，对先验知识与正确度期望值的设定将一直影响你的机器学习，从语义上讲，你得到的超越性结果可能也只是你已经为机器设立的目标，而机器自己往上靠的结果。这一结果已经在人的心中存在，而机器并没有证明它，只是承认它。