克萊尼–波斯特定理

克萊尼–波斯特定理（英語：Kleene–Post Theorem）是可計算性理論中關於不可解度的定理，聲稱存在且可從停機問題計算出一對互相不可計算的不可解度。^[1]

內容

存在不可解度 $A,B$ ，使 $\mathbf {0} ^{\prime }\geq _{T}A$ 、 $\mathbf {0} ^{\prime }\geq _{T}B$ 且 $A,B$ 互不可計算。

相關定理

參考資料

^ Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英語）. ^{[頁碼請求]}

這是一篇與電腦相關的小作品。您可以透過編輯或修訂擴充其內容。

取自「https://zh.wikipedia.org/w/index.php?title=克莱尼–波斯特定理&oldid=55531336」