跳至內容

克萊尼–波斯特定理

維基百科,自由的百科全書

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

內容

存在不可解度 ,使 互不可計算。

相關定理

參考資料

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