经典证明：Chaitin定理 不可能编程判断代码的最简性

今天学到一个好玩的东西。仿照停机问题的研究方法，我们可以想出很多有趣的不可解问题。Gregory Chaitin曾经提出过下面这个问题。如果两段代码运行之后能够输出相同的结果，我们就称较短的代码比长一点的那个更简洁（注意，如果程序需要读入数据，读入的数据也算进代码长度）。对于一个指定的输出，一定存在一个“最简的”代码，它是所有能输出此内容的程序代码中最短的一个。在TLE比赛中，参数选手拼了命地缩减每一个字符，写出来的代码一个比一个短。有人或许在想，这些代码究竟能短到什么程度？你如何才能知道你的代码已经不再有改进的空间了？受此启发，我们的问题出来了：你能否编写一个程序，使得该程序能够判断任意一段代码是否是最简的？

Chaitin定理指出，上述问题是一个不可解问题，再牛的人也不可能编写出这样的程序。证明方式与大多数此类问题一样，都是采用反证加构造的方法证明的。你能想到这个证明方法吗？

假设我们有一个程序A，该程序能读入一段代码并且判断该代码是否最简。写一个程序B，该程序读入一个自然数N，然后枚举出所有长度大于N的程序代码并用程序A进行检测，直到找到一个最简的代码；然后运行这个最简代码，输出和这个最简代码一样的输出内容。现在，运行程序B，输入一个比程序B的代码长度更大的数，让程序B去找一个比它自身更长的最简代码。但是，程序B比这个最简代码要短，输出内容却和它相同，于是矛盾就产生了。

但是，有没有可能程序B没有输出呢？换句话说，程序B会不会根本找不到一个比它长的最简代码呢？当然不会，因为最简代码显然有无穷多个。

补充一下：有人没明白这里“最简代码有无穷多个”是什么意思？其实我也很不想说穿它……由于输出结果不同的程序有无穷多种，最简的程序代码显然也有无穷多个；但长度不超过N的代码只有有限多个，因此必然存在长度大于N的最简代码。

再补充一下：有人问到，B程序如何模拟运行一段别的代码？这个问题问的好！事实上，一个程序语言是可以自我解释(http://en.wikipedia.org/wiki/Self-interpreter)的；换句话说，你完全可以写出一个C语言解释器，而它本身就是用C语言来写的。因此，B程序能够“运行”其它代码，并保证跟它的输出结果一样（即使输出结果有无穷多）。显然，即使这样停机问题仍然没有解决，因为你能模拟它运行了也不知道它会不会停机。

“自我解释”听起来很不可思议，但事实上是千真万确的。C语言的自我解释器我不知道有没有，不过用JavaScript写的JavaScript引擎(http://en.wikipedia.org/wiki/Narcissus_(JavaScript_engine))倒是有一个。你甚至能瞻仰到它的源码(http://mxr.mozilla.org/mozilla/source/js/narcissus/)。

补充3：还有人问到，既然输入也要算进代码长度，那会不会出现纯粹的代码长度没超过N，但把N一输进去代码长度就超过N了？其实，当N取到一定大时，纯代码长度加输入长度必然会超过N，因为数字N本身的长度是以log(n)的级别增长的，总有某个时候会有纯代码长度+log(N)<N。

参考资料：http://www.flownet.com/gat/chaitin.html