查看“︁克莱尼–波斯特定理”︁的源代码

'''克莱尼–波斯特定理'''（{{lang-en|'''Kleene–Post Theorem'''}}）是[[可計算性理論]]中關於[[不可解度]]的定理，声称存在且可从[[停机问题]]计算出一对互相不可计算的不可解度。<ref>{{cite book|author=Robert I. Soare|title=''Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets''|publisher=Springer|isbn=9780387152998|language=en|year=2004}}{{page needed}}</ref>

== 内容 ==
存在不可解度 <math>A,B</math>，使 <math>\mathbf0^\prime\ge_TA</math>、<math>\mathbf0^\prime\ge_TB</math> 且 <math>A,B</math> 互不可计算。

== 相关定理 ==
* [[弗里德堡–穆奇尼克定理]]是克莱尼–波斯特定理的强化形式。
* [[波斯特定理]]
* [[克莱尼–波斯特定理]]
* [[波斯纳–罗宾逊定理]]
* [[跳躍逆轉定理]]

== 参考资料 ==
{{references}}

{{Compu-stub}}

{{DEFAULTSORT:Kleene–Post Theorem}}
[[分类:计算理论]]