halting
停机问题、Chaitin常数与万能证明方法
Program Impossible | 2008-10-12 1:45| 22 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com
高中一次英语课上，英语老师问我们，如果你有机会乘坐时光机回到过去，你想利用这次机会来干啥。“人上一百，形形色色”这句老话得到了完美的验证。什么“回去看看四大美女”呀、“看看金字塔是怎么建造的”呀、“回到三年前的那个风雨交加的夜晚握住她的手深情地告诉她其实我不想让你离开我你知道你走了之后我有多么痛苦吗”之类的东西，各种稀奇古怪的想法都被我们说了个遍。我还记得当时我说的啥——一个无比实用的雕虫小技。我说，我就想回到一个星期前，然后去买彩票。发明一个新东西并不是关键，关键是你怎么去使用它。
最奇怪的幻想总是来自于最奇怪的需求。大家有过这种经历吗？看到自己写的程序运行了半天都还没有任何结果，于是开始纠结，到底是再等一会儿呢还是强行终止了检查一下看程序写错没；犹豫了半天决定杀掉进程后，检查了半天又发现程序没有写错。于是开始怨念，早知道程序没有死循环的话刚才就多等一会儿了。此时，你会突然开始幻想，有没有什么编译器能够事先告诉你你的程序是否会无限运行下去？虽然编程判断一段代码是否会无限执行下去很可能会相当的困难，但我们仍然不排除会有某个天才程序员想出了一个比三角恋爱更加复杂的算法，花它五年的功夫为他心爱的编译器写出了这样一个强大的插件。为什么不可能呢？这个东西看上去似乎比时光旅行机更现实一些。或许我们会在某个科幻电影中看到，一个程序员在黑黢黢的屏幕上输入了几个数，敲了一下回车，然后屏幕上立即用高亮加粗字体显示“警告：该输入数据会导致程序无限运行下去，确定执行？(Y/N)”。如果有一天，这一切真的成为了现实，那么你能利用这个玩意儿来做些什么实用的、有价值的事情？如果我说你能靠这玩意儿发大财你相信么？
永远不要说什么“看看当年我NOIp第二题的第四个数据是不是真的因为死循环了才超时的”之类的东西。如果是我的话，我一定会用点别人想不到的雕虫小技干出一番惊天动地的大事。我上来就先写一个Goldbach猜想的验证程序。我写一个程序从小到大枚举所有的偶数，看是不是有两个质数加起来等于它：如果找到了，继续枚举下一个偶数；否则输出这个反例并结束程序。然后我编译它。这个编译器不是可以判断我这程序能否终止么？如果编译器说我这个程序会无限执行下去的话……我不就相当于把Goldbach猜想证到了吗？或者，编译器说程序最终会终止，那Goldbach猜想不就直接被推翻了吗？反正，那个证Goldbach猜想的奖金肯定是我的了。拿下Goldbach猜想的奖金后，我接着写程序看是不是真的有无穷多个孪生素数，顺便利用前面那几个程序把Mersenne素数是否无穷多的问题也给解决了。写个证明Riemann假设的程序似乎有点麻烦，但是写一个验证Collatz猜想（3x+1问题）的程序只是一两分钟的事情。永远不要怕没有事情做，大不了把Hilbert的23个问题或者什么千禧年七大数学难题之类的全部翻出来，或者直接去Wikipedia的Unsolved Problems in Mathematics词条，看看哪些命题是离散的，写几个程序就可以把它们统统解决了……
还是从幻想中清醒过来吧，能判断一个程序能否无限运行下去的程序是否真的存在我们还不知道呢。不过仔细回想一下上面的讨论，你会意识到这种程序的存在该是多么的不可思议啊。即使这样的程序真的存在，实现它的难度也绝对不亚于解决上述的任何一个数学猜想，不然的话大家都转而向这个神奇的“万能证明方法”进攻了。
而事实上，科学家们已经从理论上证明了，这种程序是永远不可能实现出来的。这就是著名的停机问题(The Halting Problem)，它是一个不可解问题。停机问题不可解的证明并不复杂，并且非常有趣。你可以在这里看到整个证明过程。我们刚才那些美好的梦想被这一个简短的证明摔成了碎片。
永远不要小瞧人类的想象力。对“万能证明方法”的进攻并没有就此结束。虽然判断一段代码运行后是否会终止的程序是不存在的，但这个“万能证明法”的思路是非常值得借鉴的。下面，我来提出一个绝对存在的东西，它同样可以用于我们的“程序证明”。它就是指定的编程语言中任意一段代码运行后最终会停止下来的概率。假如说这种编程语言有p种字符（包括代码结束的符号共p+1种），长度为n的代码中有T(n)个不会无限运行下去，那么我们定义这个概率就是Σ(n=1..∞) T(n)/(p+1)^n。考虑两种极端的情况：如果所有代码都永不终止，则这个概率值为0；如果所有代码运行后最终都能停下来（包括语法错误根本不能编译的情况），则概率为Σ(n=1..∞) p^(n-1)/(p+1)^n，其中p^(n-1)表示除去那个结束符号后所有可能的n-1位代码。利用等比数列求和公式容易得出这个值等于1。当然，在实际情况下，这个概率值是一个介于0和1之间的确定的数。
有了这个概率之后，我们就无敌了！！我们故技重施，写一个Goldbach猜想验证程序。假如这个程序的长度为L。注意到Σ(n=k+1..∞) p^(n-1)/(p+1)^n=(p/(p+1))^k，当k足够大时必然有某个时刻(p/(p+1))^k比1/(p+1)^L小。我们再用一个程序来生成所有可能的长度不超过k的代码（这让我想起了《诗云》中的“啊啊啊啊啊，啊啊啊啊啊”）。然后，壮观的一幕发生了：我们同时运行所有这Σ(n=1..k) p^(n-1)个程序！这里面，有些程序根本就不能跑（编译都通不过），有些程序运行后闪一下就退出来了，有些程序可能得等个好几天才能退出；当然也有将要无限运行下去的程序。不过可以肯定的是，受到上面那个概率值的限制，最终停止下来的程序是有一个上限的。随着越来越多的程序停止下来，总有某个时刻会达到这样一种状态：终止的程序所占的比例与我们那个概率值的误差不到1/(p+1)^L（因为我们没有考虑的那些代码即使全部都会终止也只占(p/(p+1))^k的分量，而k值的选择保证了这个分量不足1/(p+1)^L），此时只要再有一个长度不超过L的程序终止，实际比例（将增加至少1/(p+1)^L）就超过那个概率了。这时，我们就可以肯定，到时候还没有停止的程序必然将无限运行下去。如果届时我们的Goldbach猜想还没找出反例，这就意味着这个程序永远找不出反例了，Goldbach猜想也就得到了证实。显然，这种算法并不要求我们所提到的概率值要达到无限精确，我们只需要概率公式的前k项的和就足够了。
或许，这个工程确实有点庞大，需要耗费大量的时间和金钱。不过，为了证明那么多悬而未解的数学之谜，投入再多的时间和资金也值得啊！我们还可以采取SETI@home的办法，邀请全球的计算机一起来参与计算啊！那么，为什么我们不这样做呢？真实的情况到底如何呢？
这或许会有些不合常理：我们上面提到的那个概率值是一个“不可计算数字”(uncomputable number)。它是一个可以严格定义出来，并且也确实存在的数，但我们永远无法计算出它的值（即不存在某种算法能够给出小数点后任意多位的数字）。这个概率是有一个名字的，它叫做Chaitin常数，它是以数学家和计算机科学家Gregory Chaitin的名字命名的。我们可以证明出，Chaitin常数确实是不可计算的。不妨反过来想，假如我们有一个算法能够给出小数点后任意多位的值，那么我们就能用上面那种“等足够多的程序终止”的方法判断出一个代码长为n的程序是否会无限运行下去，这相当于我们有了一个解决停机问题的算法；但我们前面已经证明了，停机问题是不可解的，因此我们可以肯定地说，想要算出Chaitin常数一定是办不到的。
Program Impossible | 2008-10-12 1:45| 22 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com
高中一次英语课上，英语老师问我们，如果你有机会乘坐时光机回到过去，你想利用这次机会来干啥。“人上一百，形形色色”这句老话得到了完美的验证。什么“回去看看四大美女”呀、“看看金字塔是怎么建造的”呀、“回到三年前的那个风雨交加的夜晚握住她的手深情地告诉她其实我不想让你离开我你知道你走了之后我有多么痛苦吗”之类的东西，各种稀奇古怪的想法都被我们说了个遍。我还记得当时我说的啥——一个无比实用的雕虫小技。我说，我就想回到一个星期前，然后去买彩票。发明一个新东西并不是关键，关键是你怎么去使用它。
最奇怪的幻想总是来自于最奇怪的需求。大家有过这种经历吗？看到自己写的程序运行了半天都还没有任何结果，于是开始纠结，到底是再等一会儿呢还是强行终止了检查一下看程序写错没；犹豫了半天决定杀掉进程后，检查了半天又发现程序没有写错。于是开始怨念，早知道程序没有死循环的话刚才就多等一会儿了。此时，你会突然开始幻想，有没有什么编译器能够事先告诉你你的程序是否会无限运行下去？虽然编程判断一段代码是否会无限执行下去很可能会相当的困难，但我们仍然不排除会有某个天才程序员想出了一个比三角恋爱更加复杂的算法，花它五年的功夫为他心爱的编译器写出了这样一个强大的插件。为什么不可能呢？这个东西看上去似乎比时光旅行机更现实一些。或许我们会在某个科幻电影中看到，一个程序员在黑黢黢的屏幕上输入了几个数，敲了一下回车，然后屏幕上立即用高亮加粗字体显示“警告：该输入数据会导致程序无限运行下去，确定执行？(Y/N)”。如果有一天，这一切真的成为了现实，那么你能利用这个玩意儿来做些什么实用的、有价值的事情？如果我说你能靠这玩意儿发大财你相信么？
永远不要说什么“看看当年我NOIp第二题的第四个数据是不是真的因为死循环了才超时的”之类的东西。如果是我的话，我一定会用点别人想不到的雕虫小技干出一番惊天动地的大事。我上来就先写一个Goldbach猜想的验证程序。我写一个程序从小到大枚举所有的偶数，看是不是有两个质数加起来等于它：如果找到了，继续枚举下一个偶数；否则输出这个反例并结束程序。然后我编译它。这个编译器不是可以判断我这程序能否终止么？如果编译器说我这个程序会无限执行下去的话……我不就相当于把Goldbach猜想证到了吗？或者，编译器说程序最终会终止，那Goldbach猜想不就直接被推翻了吗？反正，那个证Goldbach猜想的奖金肯定是我的了。拿下Goldbach猜想的奖金后，我接着写程序看是不是真的有无穷多个孪生素数，顺便利用前面那几个程序把Mersenne素数是否无穷多的问题也给解决了。写个证明Riemann假设的程序似乎有点麻烦，但是写一个验证Collatz猜想（3x+1问题）的程序只是一两分钟的事情。永远不要怕没有事情做，大不了把Hilbert的23个问题或者什么千禧年七大数学难题之类的全部翻出来，或者直接去Wikipedia的Unsolved Problems in Mathematics词条，看看哪些命题是离散的，写几个程序就可以把它们统统解决了……
还是从幻想中清醒过来吧，能判断一个程序能否无限运行下去的程序是否真的存在我们还不知道呢。不过仔细回想一下上面的讨论，你会意识到这种程序的存在该是多么的不可思议啊。即使这样的程序真的存在，实现它的难度也绝对不亚于解决上述的任何一个数学猜想，不然的话大家都转而向这个神奇的“万能证明方法”进攻了。
而事实上，科学家们已经从理论上证明了，这种程序是永远不可能实现出来的。这就是著名的停机问题(The Halting Problem)，它是一个不可解问题。停机问题不可解的证明并不复杂，并且非常有趣。你可以在这里看到整个证明过程。我们刚才那些美好的梦想被这一个简短的证明摔成了碎片。
永远不要小瞧人类的想象力。对“万能证明方法”的进攻并没有就此结束。虽然判断一段代码运行后是否会终止的程序是不存在的，但这个“万能证明法”的思路是非常值得借鉴的。下面，我来提出一个绝对存在的东西，它同样可以用于我们的“程序证明”。它就是指定的编程语言中任意一段代码运行后最终会停止下来的概率。假如说这种编程语言有p种字符（包括代码结束的符号共p+1种），长度为n的代码中有T(n)个不会无限运行下去，那么我们定义这个概率就是Σ(n=1..∞) T(n)/(p+1)^n。考虑两种极端的情况：如果所有代码都永不终止，则这个概率值为0；如果所有代码运行后最终都能停下来（包括语法错误根本不能编译的情况），则概率为Σ(n=1..∞) p^(n-1)/(p+1)^n，其中p^(n-1)表示除去那个结束符号后所有可能的n-1位代码。利用等比数列求和公式容易得出这个值等于1。当然，在实际情况下，这个概率值是一个介于0和1之间的确定的数。
有了这个概率之后，我们就无敌了！！我们故技重施，写一个Goldbach猜想验证程序。假如这个程序的长度为L。注意到Σ(n=k+1..∞) p^(n-1)/(p+1)^n=(p/(p+1))^k，当k足够大时必然有某个时刻(p/(p+1))^k比1/(p+1)^L小。我们再用一个程序来生成所有可能的长度不超过k的代码（这让我想起了《诗云》中的“啊啊啊啊啊，啊啊啊啊啊”）。然后，壮观的一幕发生了：我们同时运行所有这Σ(n=1..k) p^(n-1)个程序！这里面，有些程序根本就不能跑（编译都通不过），有些程序运行后闪一下就退出来了，有些程序可能得等个好几天才能退出；当然也有将要无限运行下去的程序。不过可以肯定的是，受到上面那个概率值的限制，最终停止下来的程序是有一个上限的。随着越来越多的程序停止下来，总有某个时刻会达到这样一种状态：终止的程序所占的比例与我们那个概率值的误差不到1/(p+1)^L（因为我们没有考虑的那些代码即使全部都会终止也只占(p/(p+1))^k的分量，而k值的选择保证了这个分量不足1/(p+1)^L），此时只要再有一个长度不超过L的程序终止，实际比例（将增加至少1/(p+1)^L）就超过那个概率了。这时，我们就可以肯定，到时候还没有停止的程序必然将无限运行下去。如果届时我们的Goldbach猜想还没找出反例，这就意味着这个程序永远找不出反例了，Goldbach猜想也就得到了证实。显然，这种算法并不要求我们所提到的概率值要达到无限精确，我们只需要概率公式的前k项的和就足够了。
或许，这个工程确实有点庞大，需要耗费大量的时间和金钱。不过，为了证明那么多悬而未解的数学之谜，投入再多的时间和资金也值得啊！我们还可以采取SETI@home的办法，邀请全球的计算机一起来参与计算啊！那么，为什么我们不这样做呢？真实的情况到底如何呢？
这或许会有些不合常理：我们上面提到的那个概率值是一个“不可计算数字”(uncomputable number)。它是一个可以严格定义出来，并且也确实存在的数，但我们永远无法计算出它的值（即不存在某种算法能够给出小数点后任意多位的数字）。这个概率是有一个名字的，它叫做Chaitin常数，它是以数学家和计算机科学家Gregory Chaitin的名字命名的。我们可以证明出，Chaitin常数确实是不可计算的。不妨反过来想，假如我们有一个算法能够给出小数点后任意多位的值，那么我们就能用上面那种“等足够多的程序终止”的方法判断出一个代码长为n的程序是否会无限运行下去，这相当于我们有了一个解决停机问题的算法；但我们前面已经证明了，停机问题是不可解的，因此我们可以肯定地说，想要算出Chaitin常数一定是办不到的。
