不可判定問題
此條目需要補充更多來源。 (2018年3月12日) |
此條目可參照英語維基百科相應條目來擴充。 |
不可判定問題是可計算性理論和計算複雜性理論中定義的一類決定性問題，此類問題無法總是用單一算法得出正確的是/否的答案。停機問題是這類問題的一個代表：對於停機問題，沒有算法能夠正確判定任意程序是否會終止運行。[1]
背景
決定性問題是一類根據從一個無限集合中選取的輸入值，得出是或否的回答的問題。因此，根據傳統定義，尋求答案為是的輸入值之集合的問題，與決定性問題等價。
與哥德爾不完備定理的關係
不可判定問題舉例
參考資料
- ^ sen., Luo; (1962-), Xu liu tong,; juan., Yang; bin., Wu; 羅森.; (1962-), 徐六通,; 楊娟.; 吳斌. Li san shu xue ji qi ying yong. 离散数学及其应用. Bei jing: Ji xie gong ye chu ban she. 2015. ISBN 9787111453826. OCLC 917593230.