克萊尼–波斯特定理

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

內容

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

相關定理

• 弗里德堡–穆奇尼克定理是克萊尼–波斯特定理的強化形式。
• 波斯特定理
• 克萊尼–波斯特定理
• 波斯納–羅賓遜定理
• 跳躍逆轉定理