[科普中國]-低基定理

低基定理是關于不可解度的定理，不可解度，或圖靈度，是數(shù)學邏輯的名詞，尤其應用在可計算性理論中，低基定理的具體定義請參見正文。

簡介低基定理是關于不可解度的定理，不可解度，或圖靈度，是數(shù)學邏輯的名詞，尤其應用在可計算性理論中。1

定理設為無窮長二進制串的集合，若自然數(shù)的語言中存在遞歸公式θ，使當且僅當為真，則定義A為類。

若將無窮長二進制串的第n位理解成“n是否屬于該集合”，則自然對應了自然數(shù)集合的子集集合。因此上可以引入不可解度的關系。

低基定理表明，若A是一個類，則存在使得。稱G為A的低基。1

不可解度不可解度，或圖靈度，是數(shù)學邏輯的名詞，尤其應用在可計算性理論中。1

可計算性理論在計算機科學中，可計算性理論（Computability theory）作為計算理論的一個分支，研究在不同的計算模型下哪些算法問題能夠被解決。相對應的，計算理論的另一塊主要內(nèi)容，計算復雜性理論考慮一個問題怎樣才能被有效的解決。1

本詞條內(nèi)容貢獻者為:

胡建平 - 副教授 - 西北工業(yè)大學