克莱尼–波斯特定理

克莱尼–波斯特定理（英语：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.wiki.x.io/w/index.php?title=克莱尼–波斯特定理&oldid=55531336”