悖论引入

大一刚学数分时，助教讲了如何利用理发师悖论证明一个集合和它的幂集如何不等势。当时我对这个悖论很好奇，上网找了些资料来看，发现了一个更有趣的例子：

任何一个正整数都可以用一段中文文字描述出来，例如“三百六十五”、“六乘三”，那么不能用二十个字以内表示的最小正整数是什么？

这里便蕴含了一个悖论，因为倘若这样的数真的存在，那么“不能用二十个字以内表示的最小正整数”就是它的一个二十字以内描述（不信你自己数）。这里悖论的产生，正如理发师悖论，和“自指”有着千丝万缕的联系。（“能用二十个字描述”在完成对自己的定义之前，已经假定了自己的存在）

背后的相关理论

随着进一步学习，我才了解到这个例子背后的理论。比如今天信息论讲的Komogorov复杂度，完全就是上面例子的严谨表述。从Komogorov复杂度不可计算性的证明中，我突然发现上述悖论是如何被完美规避的。简要证明如下，假设任何串的描述复杂度可以被图灵机H计算，那么我们可以用这个固定长度的H加上一些循环代码，找出第一个复杂度不小于M（M足够大）的串并且输出，这样一来这个复杂度M的串却可以被一个长度小于M的机器H’描述出来，产生矛盾！

上述证明的思想，其实就是来源于之前那个悖论，而悖论被规避的方法就是“不可计算性”。通俗地说，之前我们使用的“不能用二十个字以内表示的最小正整数”描述方法，其实是“不符合规范”的！

在这几个学期的学习中，我逐渐产生一种直觉，即如上所述的“自指”现象，一旦出现，就几乎一定会给一个理论系统引入悖论，因此需要以合适的方式规避。除了上面描述复杂度的例子之外，公理集合论直接强行排除了在定义中引用自己的集合，规避了罗素悖论。

还有一个关于图灵机的例子。上学期我学到了递归定理，即图灵机可以在定义中引用自己的代码（一个现实的例子是可以写出一个C程序打印出自己的代码而不借助IO）。当时我一听到这个定理，便意识到这里存在自指现象，一不小心可能会引入悖论。那么类似前面几个悖论的标准流程，我们只需要引用自己然后再加上否定，就可以像罗素悖论那样找到矛盾。那么真的这样做的结果是什么呢？假设B是一个图灵机，它通过递归定理得到了自己的代码，然后对于任意输入，在输入上模拟自己的运行，但在最后把运行结果（接受/拒绝）取一个反，那不就产生既接受又拒绝的矛盾了！但是我们忽视了这样一点，图灵机除了可以接受/拒绝，还可能永不停机，因此既然接受拒绝都会矛盾，那么为什么不选择永不停机呢，毕竟这种可能不会自相矛盾。因此，利用自指悖论，我们得出来停机问题不可计算的又一证明。反过来看，不可计算性又帮我们规避了自指问题的悖论！

结论

综上所述，允许自指会给一个系统带来内在的矛盾，因此一个完备的理论体系必须用各种显式或隐式方法排除自指现象。在理论计算机中，排除方法是不可计算的概念，而在公理集合论中，排除方法是显式的公理。