按照指定的语法规则来编写代码,你就可以把你想要做的告诉计算机,然后编译运行代码,做出一个个各有所能的程序,这似乎听上去是一件非常有意思的事。不过,程序员也有自己的苦恼。

最奇怪的幻想往往来自于最奇怪的需求。只要是一名爱搞怪的程序员,都一定遇到过这样的事:自己辛辛苦苦编写的代码明明没有任何语法问题,但是运行了半天还是没有任何结果,于是就开始有些动摇了,到底是等会,万一就运行了;还是终止进程看看代码有没有逻辑错误呢。纠结了好大一会,决定终止进程,结果检查半天程序没有错误。于是就开始苦恼:如果刚才再多等一会就好了,估计就成功运行了。

那么,有没有这种可能:一个程序员在编译器里写了一段代码,按下运行之后,屏幕上立即弹出一句话 “运行该程序可能会导致死循环,确认运行[Y / N]?”那会怎么样呢?

这里的死循环并不只是指“令a=1,把a替换为a²,直到a > 100”这种数字不变的循环,也有可能是“令b=100,把b替换为b+1,直到b < 10”这种数值一直在变化的循环。

此时我们就要想象一下,一个程序员耗费十几年的时间为他心爱的编译器和语言写出了一个插件,也不是不可能。不过这有什么用呢?我如果说我可以靠这个赚一大笔钱你信吗?数学界有很多悬而未解的难题,找找其中哪些是有悬赏的,比如哥德巴赫猜想,我就写一段程序让计算机穷举,如果她提示上面那段话,就说明程序会一直运行下去,不就等于证明了哥德巴赫猜想吗;如果计算机没有提示,就说明程序会停下来,我就证否了哥德巴赫猜想。不管怎么样,我都是第一人,拿走奖金。再去找找还有什么别的数学问题有悬赏,几行代码就统统搞定了。哈哈哈哈。不过,上面说的可能吗?

上面说的这种问题就叫做“停机问题”,在计算机理论中是这样叙述的:停机问题是一个不可解的问题。证明也并不复杂。反证法:假设一个程序P(a,b),她就可以预先判断出代码a的初值为b时程序是否会终止。那么我们可以编一个程序Q(x,x)。她首先读取初值并叫做x,然后调用P(x,x),根据其返回的结果执行不同的任务。如果P(x,x)返回的结果是“不会终止”,立即退出程序;否则,任意执行一个死循环任务。现在运行程序Q,然后把程序Q本身的代码作为输入数据传进去,于是程序Q调用P(x,x)时,实际上问的是“运行程序Q并输入Q的代码后会发生什么”,也就是询问他自身的命运。可是根据程序Q的法则,如果P(x,x)认为该程序不会终止,Q就会立即退出;如果P(x,x)认为该程序总有终止的一刻,Q反而陷入死循环。于是,P(x,x)并没有成功预测Q的命运,这说明停机问题是不可解的。

本篇完。

分类: 文章