不可解问题之停机问题(Undecidable Problem Halting Problem)

时间:2021-04-30 23:40:16

计算机技术已运用到人类生活的方方面面,帮助人类解决各种问题。可你是否有想过,计算机是否能为人类解决所有问题呢?

假如你是一个程序猿,你已编写过很多程序。有些程序一下子就能出结果,有些程序则好久都没有显示结果。你不知道这些程序到底最终是否会显示结果。你突然灵光一现---“能不能设计一个程序,用于检测任意程序最终会停止运行还是会无限运行下去”。这样,你就不用为了得到程序的结果而等很久,有时甚至还无法确定到底是不是程序本身出现了问题,导致程序无限循环。

说干就干,你为这一想法设计的思路如下:

定义一个all_mighty_program,其输入参数是需测试的程序本身和其输入

如果该程序最终停止运行,返回True

如果该程序最终无法停止运行,则返回False

然后你根据此写了一段伪代码(pseudocode):

def all_mighty_program (code, code_input):

    if code (code_input) halts:

        return True

    else:

        return False

那么有没有什么测试程序能使上面的这段伪代码失效呢?为此,你需要进行反证。

首先,需测试的程序有两种可能性:

1,该程序最终会返回某值

2,该程序会无限循环下去

对于第一种可能性:在某个条件下,该程序最终会返回某值,也就是说该程序最终会停止运行。

需要把这个条件设计成与上面的伪代码相反。既然上面的伪代码是测试程序最终停止运行返回True,那么把条件设计成:当上面的伪代码返回False时,测试程序最终会停止。

同样,对于第二种可能性:在某个条件下,该程序会无限循环下去,也就是说该程序最终会无限运行下去。

需要把这个条件设计成与上面的伪代码相反。既然上面的伪代码是测试程序最终无法停止运行返回False,那么把条件设计成:当上面的伪代码返回True时,测试程序最终会无限循环下去。

写成伪代码如下:

def code (code_input):

    if all_mighty_program (code, code_input) is False:

        return True

    else:

        loop forever

由此可以看出,这两段伪代码的逻辑是矛盾的。当all_mighty_program (code, code_input)是False时(也就是code会无限循环下去时),code (code_input)是返回True值的(也就是code最终会停止运行)。

停机问题(Halting Probelm)是决定任意程序最终是会停止运行还是会无限运行下去的问题。

Alan Turing在1963年就证明,没有这样一个通用的算法存在,此算法在所有可能的输入参数下可以解决停机问题。