停机问题

停机问题(The halting problem) 是可计算理论(Computability theory)中至关重要的一个问题。简单的来说,它要解决:给定一个输入,需要确定一个计算机程序是否能停机(产生问题的解)或者陷入死循环。究竟是否存在一个机器,能够检查给定任何输入的任何程序,确定程序是否在有限时间里停机了?

通常,使用Turning Machines(图灵机)来证明该理论:停机意味着图灵机接受或者拒绝一个输入,而如果一个程序在图灵机上陷入了死循环,则说明该图灵机不能在给定的输入上产生解。早在1936年,Alan Turing就证明了,停机问题是不可判定的,因而不可解。如果停机问题存在解,则其他许多计算机科学的难题也会得到解答,如 Kolmogorov compexity, the Busy Beaver function等。

参考文献