低基定理

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

基本介紹

• 中文名：低基定理
• 外文名：Low basis theorem

簡介

低基定理是關於不可解度的定理，不可解度，或圖靈度，是數學邏輯的名詞，尤其套用在可計算性理論中。

定理

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

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

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

不可解度

不可解度，或圖靈度，是數學邏輯的名詞，尤其套用在可計算性理論中。

可計算性理論

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