查看“停机问题”的源代码

{{copyedit|time=2018-12-19T17:26:03+00:00}}
{{refimprove|time=2018-12-19T17:26:03+00:00}}
{{NoteTA
|G1=IT}}
'''停机问题'''（{{Lang-en|halting problem}}）是[[数理逻辑|逻辑数学]]中[[可计算性理论]]的一个问题。通俗地说，停机问题就是判断任意一个[[程序]]是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。

[[艾伦·图灵]]在1936年用[[對角論證法]]证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为[[图灵机]]。停机问题在图灵机上是[[不可判定的|不可判定问题]]。这是最早提出的[[决定性问题]]之一。

用数学语言描述，则其本质问题为: 给定一个[[图灵机]]'''T'''，和一个任意语言[[集合]]'''S'''，是否'''T'''会最终停机于每一个<math> s \in S</math>。其意义相同于可确定语言。显然任意有限 '''S''' 是[[可判定性]]的，可数的（countable）'''S''' 也是可停机的。

停机问题包含了[[自我指涉]]，本质是[[一阶逻辑]]的[[完备性|不完备性]]，类似的命题有[[理发师悖论]]、[[全能悖论]]等。

==证明==
假设停机问题有解，即：存在过程H(P, I)可以判断对于程序P在输入I的情况下是否可停机。假设P在输入I时可停机，H输出“停机”，反之输出“死循环”，即可-{zh-hans:导出; zh-hant:導出;}-矛盾：

显然，程序本身也是一种数据，因此它可以作为输入（例如Pascal的編譯器本身就可以用Pascal所寫成，所以程式在自己身上執行自己也是合理的），故H应该可以判定当将P作为P的输入时，P是否会停机。然後我们定義一個过程U(P)，其流程如下：

* U(P)调用H(P, P)：
** 如果H(P, P)進入死循环，U(P)就停机。
** 如果H(P, P)停機，U(P)就進入死循环。
** 也就是說，U(P)做的事情就是做出與H(P, P)的输出相反的动作。

[[伪代码]]及其註釋表示如下：
<source lang="c" enclose="div">
int H(procedure,Input); // 这里的H函数有两种返回值，死循环(1) 或 停机(0)
int U(P)
{
    if (H(P,P) == 1){ // 如果H死循环
        return 0; // 此时会停机
    }else{ // 否則
        while(1){} // 此时会死循环
    }
}
</source>

上面把H(P, P)包裝在U(P)內，也就是用U()來模擬H()。H()的輸出可能出現兩種狀況：
* 假設H(U, U)输出停机 -> U(U)進入死循环：由定义知二者矛盾（与过程H的定义相矛盾，因为照H自己本來的定義，H(U, U)的結果應該和U(U)相同，但U()的定義卻是永遠輸出與H()相反的結果。）
* 假設H(U, U)输出死循环 -> U(U)停机：两者一样矛盾。

因此，H不是总能给出正确答案，故前述的假設不成立，不存在解决停机问题的方法。<ref>pp. 179-180，《离散数学及其应用》，Kenneth H. Rosen著，机械工业出版社</ref>

== 相似的悖论 ==
'''[[理发师悖论]]'''：村子里有个理发师，这个理发师有条原则是，对于村子里所有人，[[若且唯若]]这个人不自己刮胡子，理发师就给这个人刮胡子。如果这个人自己刮胡子，理发师就不给这个人刮胡子。无法回答的问题是，理发师给自己刮胡子么？

'''[[停机测试悖论]]'''：计算机里面有个测试程序，这个测试程序的原则是，对于计算机裏所有程序，当且仅当这个程序不递归调用自己（输出停机），测试程序就调用它（对应不停机）。如果这个程序递归调用自己（对应不停机），测试程序就不调用它（对应停机）。无法回答的问题是，测试程序递归调用自己么？

==参见==
*[[理发师悖论]]
*[[哥德尔不完备定理]]
*[[未解決的數學問題]]

==参考文献==
<references />

==外部链接==
*[[顾森]]解释[http://www.matrix67.com/blog/archives/901 停机问题]和[http://www.matrix67.com/blog/archives/55 证明]

[[Category:數理邏輯|T]]
[[Category:計算理論]]
[[Category:递归论]]
[[Category:数学问题]]