前言
Roger Penrose 在《皇帝新脑》中试图回击强AI观点，即人的思维过程等价于一套及其复杂的算法。他通过若干途径进行反驳，包括证明人脑活动的抽象模型高于算法、人脑活动的物理过程无法计算等等。在算法与人脑关系这部分，penrose主要侧重于阐述算法不能超越人脑。我将其单独抽离出来，作为一个一窥元数学深奥世界的小品。罗素悖论，哥德尔不完备定理，图灵停机问题，看上去都相隔很远，但它们都指向了逻辑系统中一个相似的困难。
罗素悖论
一个集合是否能包含自身？这是集合论风行数学界若年后罗素提出的最有挑战的问题。罗素悖论点出了朴素集合论中存在的问题，即我们在以集合论为基石试图构建严密完整的数学大厦时，对基石本身的认识就是含糊不清的。
设R={所有不包含自己的集合}，问R是否包含自身？如果R不包含自身，那么它就是一个不包含自身的集合，则根据定义R应该包含自身；如果R包含自身，那么根据定义，R不在集合R中。
罗素采用了一个笨拙的办法来避免罗素悖论，即对每一个集合标定层级，每个集合只能包含层级低于自己的集合或元素。
虽然罗素悖论和之后要讨论的主题略有差距，但相信了解了停机问题和不完备性定理后，我们会惊奇地发现，它们之间似乎有某种共通的东西，即数学对象在指向自己时会遇到的困境。
图灵停机问题
事实上，图灵停机问题是晚于哥德尔不完备性定理出现的，图灵本人也承认自己受哥德尔证明的启发，写下了停机问题。
算法与图灵机
希尔伯特提出过其著名的希尔伯特规划，即给定足够的公理，运用机械推导，能否对所有合法表述的表达式提供正误判断。这也是之前一篇文章中形式主义者所怀的梦想，但后来被哥德尔无情地击碎了。
虽然梦不再了，但有新的问题出现。即是否存在能在原则上一个接一个解决所有数学问题的某种一般机械步骤？问题的关键在于什么是“机械推导”，图灵给出了他的定义，并从此打开了新世界的大门。
图灵是这样定义的：想象一台在无限长磁带上的机器，其左侧有无限长的磁带，其右侧也有无限长的磁带。磁带由可以写入数字的格子连接而成，可以用磁头进行读写。机器内部还有一个记录内态的记录仪器，以及一张表，用于查询。现在我们在图灵机的右侧磁带上写入数据（比如打孔），然后打开开关，于是它开始工作了：每一回合，它读出磁头所指的格子内的数，m，并且知道自己的内态n，那么通过查找表格，得到$(n,m) \to (n’,m’,d)$，即将内态改为n’，格子内的数改为m’，并执行移动指令d(left, right or stay)。在机器最终停下来后，机器左侧就是输出的数据。
使用图灵机即便是实现十分简单的运算都是十分麻烦的，但至少它给出了所谓“算法”的一个严格的定义，即能够由图灵机实现的操作。而且，我们可以将它的那张运行表${(n,m) \to (n’,m’,d)| n \in S, m \in Z}$通过一套编码规则一一映射到自然数集合上，也同样可以通过将自然数解码来构造图灵机，因此图灵机的总数和自然数的总数是一样的！即所谓的连续统$\xi_0$。
通用图灵机(Universal Turning Machine)
我们将编码为n的图灵机称为$T_n$
存在一个算法，能够模拟任何其他的图灵机，称为通用图灵机，用U表示。其运行性质为，输入数据分两个部分，$(n, k)$。$U(n,k) = T_n(k)$。事实上，所有现代的计算机都是通用图灵机。
图灵停机问题
是否存在一个算法，能够在有限时间内判定一对（算法，输入）的组合是否停机，我们称之为图灵停机问题。之所以这个问题重要，是因为最终我们将证明不存在这样一个算法，而人脑又能通过在系统之外的洞察判定这一对（算法，输入）的组合是否停机。
假设存在这样一个算法H，能够在有限时间内判定一对（算法，输入）的组合是否停机，并且输出0或1
接下来我们通过将两个算法结合起来生成一个新的的算法：
- 先通过$H(n,k)$判定是否停机
- 如果停机，则输出 $T_n(k)$
- 如果不停机，则输出 $0$
可以表达为 $Q(n,k) = T_n(k) \times H(n, k) = U(n, k) \times H(n, k)$
接下来，定义$T_w(k) = 1 + Q(k,k) = 1 + T_k(k) \times H(k, k)$， 则当计算
$T_w(w)$时，会遇上一个不可调和的矛盾：
- 如果$T_w(w)$会停机，那么最后得到的结果为$T_w(w) = 1 + T_w(w)$
- 如果$T_w(w)$不会停机，那么会和其定义冲突，因为等式右边的表达式总能在有限时间内停机。
所以不存在算法$H$，能够在有限时间内判定一对（算法，输入）的组合是否停机。
哥德尔不完备性
哥德尔的证明思路十分简单，其主要工作量在于将形式系统中的语言顺利地编码，Penrose略过了这一部分，我自然也没有能力去细说，让我们还是将精力集中在哥德尔思想最闪耀的那一点上。
首先，令应用于w的第n个命题函数为$P_n(w)$。哥德尔的证明中主要的工作就是证明对于一套特定的符号系统，如何将其编号，在此我们直接接受其论断，即这样一个命题函数和变量w能够表示任何在这一套符号系统下的命题。
接着，构成这一系统中某一定理证明的一串命题也可以进行编号，令$[\Pi]_n$表示第n个证明。
考虑如下的依赖于w的命题函数：$\neg\exists[\Pi_x \Rightarrow P_w(w)]$，该命题论断不存在$P_w(w)$的证明。哥德尔通过他卓越的技巧证明了这一命题函数同样可以编码进前述的系统，我们姑且将其记为$P_k(w)$。
现在我们来考察一个十分怪异的命题$P_k(k)$。将其展开可以得到 $\neg\exists x[\Pi_x \Rightarrow P_k(k)] = P_k(k)$。这个命题意味着：如果它为真，则不存在它的证明；如果它为假，则存在证明其为真的证明。即要么不完备，要么不一致。
哥德尔定理对于形式系统而言，是一个驱之不散的幽灵。假如我们将通过外部洞察得到的$P_k(k)$作为新的附加公理加入符号系统，记为$G_0$，则会出现新的不一致，我们记为$G_1$。如果接着加下去，我们得到${ G_0, G_1, G_2 …}$ 这样一个无限的公理系统，将其作为附加公理，结果怎样？由于这个不断附加的过程是个完全系统化的方案，可以将其当做通常的公理和步骤法则的有限逻辑系统来重述，所以这个系统也有它自己的哥德尔命题，如$G_w$，那么接下来就有$G_{w+1} …$，我们回到了起点。
个人对于 Penrose 论证的一些想法
Penrose 指出在图灵机上不存在可以判断停机的程序，那就说明人脑高于图灵机，因为他认为人脑可以对停机问题作出判断。然而人脑究竟有没有这样的能力，实在是很难说，事实上也并没有一个人脑能力的严格证明。
Stanford Encyclopedia of Philosophy
Reference: The Emperor’s New Mind, Roger Penrose