克莱尼–波斯特定理
克莱尼–波斯特定理（英語：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 （英语）.[页码请求]
 | 这是一篇與计算机相關的小作品。你可以通过编辑或修订扩充其内容。 |