相信目前很多小伙伴對于停機問題都比較感興趣，那么小搜今天在網(wǎng)上也是收集了一些與停機問題相關(guān)的信息來分享給大家，希望能夠幫助到大家哦。

1、停機問題(英語：halting problem)是邏輯數(shù)學(xué)中可計算性理論的一個問題。

2、通俗地說，停機問題就是判斷任意一個程序是否能在有限的時間之內(nèi)結(jié)束運行的問題。

3、該問題等價于如下的判定問題：是否存在一個程序P，對于任意輸入的程序w，能夠判斷w會在有限時間內(nèi)結(jié)束或者死循環(huán)。

4、 艾倫·圖靈在1936年用對角論證法證明了，不存在解決停機問題的通用算法。

5、這個證明的關(guān)鍵在于對計算機和程序的數(shù)學(xué)定義，這被稱為圖靈機。

6、停機問題在圖靈機上是不可判定問題。

7、這是最早提出的決定性問題之一。

8、 用數(shù)學(xué)語言描述，則其本質(zhì)問題為: 給定一個圖靈機T，和一個任意語言集合S，是否T會最終停機于每一個。

9、其意義相同于可確定語言。

10、顯然任意有限 S 是可判定性的，可數(shù)的(countable)S 也是可停機的。

11、 停機問題包含了自我指涉，本質(zhì)是一階邏輯的不自洽性和不完備性，類似的命題有理發(fā)師悖論、全能悖論等。

本文到此結(jié)束，希望對大家有所幫助。

---

版權(quán)說明：本文由用戶上傳，如有侵權(quán)請聯(lián)系刪除！

---

標簽：