今天学到一个好玩的东西。仿照停机问题的研究方法，我们可以想出很多有趣的不可解问题。Gregory Chaitin曾经提出过下面这个问题。如果两段代码运行之后能够输出相同的结果，我们就称较短的代码比长一点的那个更简洁（注意，如果程序需要读入数据，读入的数据也算进代码长度）。对于一个指定的输出，一定存在一个“最简的”代码，它是所有能输出此内容的程序代码中最短的一个。在刚刚结束的TLE比赛中，参数选手拼了命地缩减每一个字符，写出来的代码一个比一个短。有人或许在想，这些代码究竟能短到什么程度？你如何才能知道你的代码已经不再有改进的空间了？受此启发，我们的问题出来了：你能否编写一个程序，使得该程序能够判断任意一段代码是否是最简的？
Chaitin定理指出，上述问题是一个不可解问题，再牛的人也不可能编写出这样的程序。证明方式与大多数此类问题一样，都是采用反证加构造的方法证明的。你能想到这个证明方法吗？
假设我们有一个程序A，该程序能读入一段代码并且判断该代码是否最简。写一个程序B，该程序读入一个自然数N，然后枚举出所有长度大于N的程序代码并用程序A进行检测，直到找到一个最简的代码；然后运行这个最简代码，输出和这个最简代码一样的输出内容。现在，运行程序B，输入一个比程序B的代码长度更大的数，让程序B去找一个比它自身更长的最简代码。但是，程序B比这个最简代码要短，输出内容却和它相同，于是矛盾就产生了。
但是，有没有可能程序B没有输出呢？换句话说，程序B会不会根本找不到一个比它长的最简代码呢？当然不会，因为最简代码显然有无穷多个。
补充一下：有人没明白这里“最简代码有无穷多个”是什么意思？其实我也很不想说穿它……由于输出结果不同的程序有无穷多种，最简的程序代码显然也有无穷多个；但长度不超过N的代码只有有限多个，因此必然存在长度大于N的最简代码。
再补充一下：有人问到，B程序如何模拟运行一段别的代码？这个问题问的好！事实上，一个程序语言是可以自我解释的；换句话说，你完全可以写出一个C语言解释器，而它本身就是用C语言来写的。因此，B程序能够“运行”其它代码，并保证跟它的输出结果一样（即使输出结果有无穷多）。显然，即使这样停机问题仍然没有解决，因为你能模拟它运行了也不知道它会不会停机。
“自我解释”听起来很不可思议，但事实上是千真万确的。C语言的自我解释器我不知道有没有，不过用JavaScript写的JavaScript引擎倒是有一个。你甚至能瞻仰到它的源码。
补充3：还有人问到，既然输入也要算进代码长度，那会不会出现纯粹的代码长度没超过N，但把N一输进去代码长度就超过N了？其实，当N取到一定大时，纯代码长度加输入长度必然会超过N，因为数字N本身的长度是以log(n)的级别增长的，总有某个时候会有纯代码长度+log(N)<N。
莫非可以抢一次沙发？
板凳。。
学习
你好，我数学一般，所以有点看不懂，请解释一下，谢谢：
Lemma: B must produce some output.
Proof: There are an infinite number of elegant programs, as noted earlier. So if ET works as assumed, B must eventually find one of those elegant programs whereupon it will produce that program’s output.
如果对所有枚举的长度大于N的程序，ET都证明了他不是elegant的，那么B将会一直运行，没有输出不是吗？如果ET知道对给定的输出所需要的代码量小于N，那他肯定会对所有的代码输出FALSE的。
所以我的问题是为什么所有长度大于N的程序代码中一定会找到一个最简的代码呢？
前排占位。。。
因为最简代码显然有无穷多个。这句话有点不理解。。。烦请大牛解释。
楼上：这里的“最简代码”是指“不能再简化(缩短)的代码”。所以显然有无穷多个(输出0，1，2，3……的代码)
这让我想起了哥德尔不完备定理和clrs上的素数无限多的定理…
这个证明有问题：
“直到找到一个最简的代码；然后运行这个最简代码，输出和这个最简代码一样的输出内容。”
B如何做到运行这个找到的最简代码并输出内容？这不就等于肯定了The Halting Problem？分析输入的代码，并给出是否会终止的判断（都知道输出的内容了，是否会终止肯定也知道了吧）。
to 凌晨海风, 没问题. 程序A只判断是否最简, 不一定有判断Halting的能力
如果凌晨海风通过程序A来构造一个程序H来能判断Halting那也是对lz的题目的一个很好的证明
PS: LZ漏了最关键一步
“但是，程序B比这个最简代码要短，输出内容却和它相同，于是矛盾就产生了。”
程序B跟”这个最简代码”并不等价, 所以没有矛盾
(因为程序B接受N的时候才跟”这个最简代码”的输出相等,
而”这个最简代码”不接受任何输入
定义程序Fn, Fn为输入n并执行B, Fn的长度|Fn|明显为
|B|, |log(n)| 的线性表达式
所以存在m 使得 m > |Fm|
现在，运行程序B，输入m，于是B找到一个最简程序X
由B的定义知道 程序X等价于Fm, 但是|X| >= m > |Fm|, 矛盾
显然这个证明完全是错的。
1.你的最简代码的定义，只要求程序代码最短，输出结果相同即可，输入数据可以无限长
2.你假设最简代码有无穷多个
如果对不同的输入，输出也必须相同，或者要求程序代码和输入数据加起来最短（相当于压缩文件），那没有问题
但是如果允许无限长的输入数据，只要得出需要的输出即可，就有问题了。这时候不会有无穷多个最简的代码，因为你只要写出一个解释器，或者干脆写一个cat程序，就可以输出任意的内容，所以不会存在比这个程序更长的最简代码。
我觉得有一个地方很有问题，你在一开始就提到了如果程序需要输入那么就把程序的输入也算在代码长度之内。那么显然B程序到底有多长这是不确定的。所以这个N是不确定的，那么你说<N的最简代码有有限个这是很值得商榷的。
一个问题
压缩问题：给一段文字，生成最简的可以生成这段文字的代码。这个问题是不是np问题？
或者说，是否有种可行的压缩算法，使一切通过程序生成的文字序列，经过压缩后长度不会超过程序长度，加上输入数据的长度。。。
比方说，A是这种算法。我用程序B生成了一个长度为10000的字符串，B的本身长度为10。则经过A压缩后得到的字符串长度不超过10。
事实上…我用winrar和fp做了个实验…一段很短的（不超过500bytes）程序，输出的文件居然几乎没法被winrar压缩。。。= =|||
var i:longint;
begin
assign(output,’fxxkrar.txt’);rewrite(output);
randomize;
for i:=1 to 1000000 do write(chr( trunc(sin(99999999 mod i)*1000)mod 256 ));
close(output);
end.
经过rar压缩，原1,000,000字节压到644,592字节…远大于上面的程序大小。
其实很容易就能想到一个算法…那就是遍历所有程序，把它们都运行一遍，能得到正确结果的最小程序就是“被压缩后的文字”…不过这是个指数级时间复杂度的算法。
忽然翻了你的老文章。。发现这个证明还是有问题啊。
既然长度大于N的代码是无穷多的，那么“枚举所有长度大于N的代码”这个工作就是不可能完成的。。。
其实就是那个“最小的不能用二十个汉字表达的数”。
我突然看懂了！(之前看了好几遍)
重复看了几遍，突然明白了一点。
经过仔细的推敲，证明结果明显是错误的。事实上，大于程序B长度的最简程序，就是无。程序A是理论存在的，当然是建立在无限计算能力的前提下。那么，得到一个更神奇的结论，那就是，所有的程序都可以压缩到大小小于等于B长度。
继续看yh秀智商，声称输入数据可以无限长