停机问题
维基百科，自由的百科全书
停机问题（halting problem）是目前逻辑数学的焦点，和第三次数学危机的解决方案。其本质问题是: 给定一个图灵机 T，和一个任意语言集合 S, 是否 T 会最终停机于每一个
。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的(countable) S 也是可停机的，在使用 oracle 输入的帮助下。
通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，可以有一个程序判断其本身是否会停机并做出相反的行为。这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。
停机问题本质是一阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。
目录 |
[编辑] 证明
设停机问题有解，即：存在过程H(P, I)可以给出程序P在输入I的情况下是否可停机。假设若P在输入I时可停机，H输出“停机”，反之输出“死循环”，即可导出矛盾：
显然，程序本身可以被视作数据，因此它可以被作为输入，故H应该可以判定当将P作为P的输入时，P是否会停机。所以我们设过程K(P)的流程如下：首先，它调用H(P, P)，如果H(P, P)输出“死循环”，则K(P)停机，反之K(P)死循环。即K(P)做与H(P, P)的输出相反的动作。
现在假设求K(K)，则若H(K, K)输出停机，K(K)死循环，但由定义知二者矛盾。反之，H(K, K)输出死循环，则K(K)停机，两者一样矛盾。
因此，H不是总能给出正确答案，故而不存在解决停机问题的方法。[1]
[编辑] 证伪
H的返回值并不代表它的能力。比如，H最少可以通过调用另一个程序给出它真正的判断。这对于上述证明过程中的P程序来说，尤其简单。因为它只需随机给出一个真或假值，将它传给被它调用的程序，然后再对这个随机值取反，将它返回给调用它的程序。便可以完成对P程序的正确判定。所以，表面上看上去最困难的判定，其实是最简单的判定。
可以把命题想成这样： 甲要求乙猜测他明天会不会吃饭。且，甲还告诉乙，他的逻辑是这样的：如果乙猜测会，他明天就不吃；如果乙猜测不会，他明天就吃。这样，对于他来说，乙永远也不可能猜对啦。但这并不代表乙不知道他明天到底会不会吃饭。因为根据乙知道（甲告诉他）的甲的逻辑，甲明天到底吃不吃饭，只是取决于乙给他的回答而已（见前述甲的逻辑）。它并不取决于自己的知识。因为乙的知识与他对甲的回答显然不是一回事。他并不需要在他对甲的回答与他自己的知识上取得一致性，这不是此问题的前提。
所以，结论中说H总是不能给出正确答案的陈述是错误的。因为他只是不能给甲正确的陈述。但这并不代表它不能给其它图灵机正确的陈述，或者它不知道正确答案。
证伪成功的结果表明，只要在H（P）启动以前，P已经确定（有限状态），且它并不向H要求其真正的判定结果（命题本身并不要求H输出其真正的判定结果。况且这样的要求其实是毫无意义的。因为H是否掌握一个知识，与其是否向具体的对象输出这个知识并没有关系）。
[编辑] 参见
[编辑] 参考文献
- ^ pp. 179-180，《离散数学及其应用》（中文版），Kenneth H. Rosen著，机械工业出版社
