克萊尼–波斯特定理(英語:Kleene–Post Theorem)是可計算性理論中關於不可解度的定理,聲稱存在且可從停機問題計算出一對互相不可計算的不可解度。[1]
內容
存在不可解度 ,使 、 且 互不可計算。
Remove ads
相關定理
- 弗里德堡–穆奇尼克定理是克萊尼–波斯特定理的強化形式。
- 波斯特定理
- 克萊尼–波斯特定理
- 波斯納–羅賓遜定理
- 跳躍逆轉定理
參考資料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
Remove ads