停機問題
維基百科,自由的 encyclopedia
停機問題(英語:halting problem)是邏輯數學中可計算性理論的一個問題。通俗地說,停機問題就是判斷任意一個程式是否能在有限的時間之內結束執行的問題。該問題等價於如下的判定問題:是否存在一個程式P,對於任意輸入的程式w,能夠判斷w會在有限時間內結束或者無窮迴圈。
此條目需要編修,以確保文法、用詞、語氣、格式、標點等使用恰當。 (2018年12月19日) |
此條目需要補充更多來源。 (2018年12月19日) |
艾倫·圖靈在1936年用對角論證法證明了,不存在解決停機問題的通用演算法。這個證明的關鍵在於對電腦和程式的數學定義,這被稱為圖靈機。停機問題在圖靈機上是不可判定問題。這是最早提出的決定性問題之一。
用數學語言描述,則其本質問題為: 給定一個圖靈機T,和一個任意語言集合S,是否T會最終停機於每一個。其意義相同於可確定語言。顯然任意有限 S 是可判定性的,可數的(countable)S 也是可停機的。