高中一次英语课上，英语老师问我们，如果你有机会乘坐时光机回到过去，你想利用这次机会来干啥。“人上一百，形形色色”这句老话得到了完美的验证。什么“回去看看四大美女”呀、“看看金字塔是怎么建造的”呀、“回到三年前的那个风雨交加的夜晚握住她的手深情地告诉她其实我不想让你离开我你知道你走了之后我有多么痛苦吗”之类的东西，各种稀奇古怪的想法都被我们说了个遍。我还记得当时我说的啥——一个无比实用的雕虫小技。我说，我就想回到一个星期前，然后去买彩票。发明一个新东西并不是关键，关键是你怎么去使用它。
最奇怪的幻想总是来自于最奇怪的需求。大家有过这种经历吗？看到自己写的程序运行了半天都还没有任何结果，于是开始纠结，到底是再等一会儿呢还是强行终止了检查一下看程序写错没；犹豫了半天决定杀掉进程后，检查了半天又发现程序没有写错。于是开始怨念，早知道程序没有死循环的话刚才就多等一会儿了。此时，你会突然开始幻想，有没有什么编译器能够事先告诉你你的程序是否会无限运行下去？虽然编程判断一段代码是否会无限执行下去很可能会相当的困难，但我们仍然不排除会有某个天才程序员想出了一个比三角恋爱更加复杂的算法，花它五年的功夫为他心爱的编译器写出了这样一个强大的插件。为什么不可能呢？这个东西看上去似乎比时光旅行机更现实一些。或许我们会在某个科幻电影中看到，一个程序员在黑黢黢的屏幕上输入了几个数，敲了一下回车，然后屏幕上立即用高亮加粗字体显示“警告：该输入数据会导致程序无限运行下去，确定执行？(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常数一定是办不到的。
我难道是沙发…
有意思
意思就是哥德巴赫猜想可以证明出来?
我好傻…刚开始没有看懂…
原来还是不可以…
呵呵，如此解释停机问题不可解，有意思…
那不就是Hilbert第二问吗
写一个程序从小到大枚举所有的偶数
这个程序一定会停止。
因为计算机不可能真的枚举“所有的”偶数……最多也就是2^(存储器大小)个偶数。这些以外的数根本无法验证。
你写的这个“枚举所有的偶数的程序”是不需要被运行的，因为你要做的是，找到一个程序，接收一段代码，判断这段代码是否会结束，你写的“枚举所有的偶数的程序”的代码是作为你写的“判断这段代码是否会结束”的代码的输入。
我怎么总觉得这篇我看过。。。
能验证程序是否结束的语句不存在吧，可以用一个很简单的递归判断做出悖论的。
在这样的说法中计算机也是理想的。。。
这个东西强大！
“有了这个概率之后，我们就无敌了！！”
“不存在某种算法能够给出小数点后任意多位的数字。”那么是否还是可以得到有限位的数字呢？那么，精心控制L的大小，让1/(p+1)^L在所求有效数字的误差范围之内，是不是还是可以用来解决很多问题呢（说不定这里面就包括哥德巴赫猜想）？
没有想到超越数之外又出来一个不可计算数，不过你的这段描述的确很有趣。
查阅了一下 http://en.wikipedia.org/wiki/Computable_number#Properties，
fantastic!
确实有检查程序是否会陷入死循环的软件，科学美国人上有过介绍。当然，它不可能解决停机问题，太过复杂的情况下会失败。
有些语言的Chaitin常数可能可以计算
只要这个语言不是Turing完备。
（Game of Life应该是没机会了……）
如果你有机会乘坐时光机回到过去，你想利用这次机会来干啥
==========
如果存在时光机器，那么我就乘坐它回到过去，告诉“过去的那个我”如何制造时光机器。反过来说，“过去的我”不必研究如何制造者时光机器，时光机器就在过去被制造出来了。
过去的我坐着时光机器又来到现在的我面前，那么时空中是不是就有“三个我”存在了？
记得Scientific Amertican中讲量子计算机的时候，提到过证明Goldbach的方法，就是把小于10亿的字符串用量子计算机全都列举出来，然后看看它是否能证明Goldbach。之所以是小于10亿，是因为字符大于10亿的证明人类就懒得看了。
记得Scientific Amertican中讲量子计算机的时候，提到过证明Goldbach的方法，就是把小于10亿的字符串用量子计算机全都列举出来，然后看看它是否能证明Goldbach。之所以是小于10亿，是因为字符大于10亿的证明人类就懒得看了。
这个厉害。。。。。
noip2007初赛：
10. 一个无法靠自身的控制终止的循环称为“死循环” ，例如，在 C 语言程序中，语句“while(1)
printf(“*”” 就是一个死循环， 运行时它将无休止地打印*号。 下面关于死循环的说法中， 只有 （ ）
是正确的。
A. 不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，
任何编译系统都不做死循环检验
B．有些编译系统可以检测出死循环
C. 死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环
D. 死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也是可以检测
的
E. 对于死循环，只能等到发生时做现场处理，没有什么更积极的手段
啊，LS说的记忆犹新。。
1.通过一个错误的前提可以证明出任何东西，这个是废话。
2.写的有点太没逻辑，太主观了，仔细看看大概意思应该是这样，先知道能结束的程序有多少个，然后排除所有能结束的程序，剩下的就是不能结束的。很可惜在知道哥德巴赫猜想这类问题能不能结束之前，你是无法知道能结束的程序有多少个的，你要的概率是猜想之后才能得到的结论。就像我们现在的知识这么多，在这个基础上要重新发现一遍古人的发现是很容易的，但是这个不代表没有这些知识基础的时候你就能发现什么。推荐网站mxdmath数学笑话。
我的智商有限，最后一自然段看不明白。
omega不可计算，等价于Godel第2不完全定理。wiki上有
偶然看到上面我自己的言论感觉我好sb啊。。
如果是我的话，我会把那些重要的专利和论文以及专著都打印出来，然后回到过去，然后你懂的。
有了这个概率之后，我们就无敌了！
我在果壳上看到你新写了一篇类似的文章，里面提出了不可定义数，可是”不可定义数“不是恰好就为一个定义吗（就像”无理数“”超越数“一样），所以自相矛盾，故不存在不可定义数，这样推理对吗？我觉得也不对，因为实数集不可数，可这个推理又错在哪里呢？
哦，我知道我错在哪里了，”不可定义数“只是对一个数集的定义，而不是对单个元素的定义。而像pi一样的可定义数是能单独进行定义的数，比如pi可以定义为使sin(x)=0的最小正实数，而某些数却一定做不到。否则光用”实数“就可以表示很多数了
话说，我们现在知道chaitin常数小数点后的几位数字了？不会连第一位都不知道吧！
无穷小→0
(1-0.99999999······)
∴∝→1/0
可以有结果
24l,这个是智商问题，只要你不是脑残，你不需要知道每个程序是否会停，你只需要等到足够数量的程序停了就好了
31l，我们知道字符串长为i的程序有几个会停，就能知道在p+1进制下第i位是几
定义不可计算数挺容易的，比如busybeaver函数的倒数和
这种哲学问题想起来真是奇妙
另外，17l太可怕了……………………
任何一个运行在有限存储器上的程序,状态时有限的.
一个程序要么陷入循环,要么在遍历所有状态之前停机,这个时间是有限的.
而穷举指定长度的程序也是能在有限步完成的.所以Chaitin常数是可计算的,
只是当程序长度很大时,不可在太阳系毁灭之前算出,而并非数学意义上的不可计算.
问题出在 “写一个Goldbach猜想验证程序。假如这个程序的长度为L” 是不可能的.
用挨个数找反例的方法写一个程序,只能算到存储器长度位的数.
放宽一点限制,存储器无限行不行?照样不行,指针长度限制了寻址范围,而程序长度限制了指针长度.
人类能证明无限的数学问题是因为可以归纳,而其中的关键步骤是不能用程序表示的,计算机无法理解的.这似乎可以扯出自由意志.
计算机这种没有自由意志的东西见鬼去吧.
非确定性图灵机完全可以有自由意志（只不过目前还没有实现一个能构造自由意志的程序），毕竟人的自由意志充其量也就是组成身体的粒子之间的相互作用与随机性的体现而已
那无限长度的程序呢?
对于任意可停机的程序,只要在前面加上while(1);就不可停机了.
对于任意不可停机的程序,只要在前面加上return 1;就可停机了.
似曾相识吧?
对于任意奇数,在他的末尾写个0(或2,4,6,8)就成偶数了.你能说偶数是奇数的5倍吗?
对于任意偶数,在他的末尾写个1(或3,5,7,9)就成奇数了.你能说奇数是偶数的5倍吗?
只能说奇数和偶数的测度相同,而不能说奇数偶数占比多少.
用数学语言,这叫阿列夫0.
同样,全部无限长的程序,可停机的无限长的程序,不可停机的无限长的程序,也都是阿列夫0.
所以,如果不限制程序长度,蔡廷常数是没有意义的.
如果是Haskell写的
好吧我误解了,停机问题要求程序要运行在图灵机上,而不是有限状态机.
如果在有限状态机上运行那个证明停机问题不可解的程序,将会因递归层数过多而爆栈,最终停机或陷入循环,从而证明运行在有限状态机上的停机问题是可解的.
学习了