克萊尼–波斯特定理
克萊尼–波斯特定理（英語：Kleene–Post Theorem）是可計算性理論中關於不可解度的定理，聲稱存在且可從停機問題計算出一對互相不可計算的不可解度。[1]
內容
存在不可解度 ，使 、 且 互不可計算。
相關定理
- 弗里德堡–穆奇尼克定理是克萊尼–波斯特定理的強化形式。
- 波斯特定理
- 克萊尼–波斯特定理
- 波斯納–羅賓遜定理
- 跳躍逆轉定理
參考資料
- ^ Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英語）.[頁碼請求]
 | 這是一篇與電腦相關的小作品。您可以透過編輯或修訂擴充其內容。 |