不可解度

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

定義

假設一個圖靈機程序可以隨意獲取自然數函數$g$的值（即使$g$不可計算），且該圖靈機計算自然數函數$f$，則定義函數$f$由函數$g$ 圖靈可計算，記作$f\leq _{T}g$。符合以上特點的圖靈機稱為具備函數$g$的預言機。若集合$B$的特徵函數可計算集合$A$，則$A\leq _{T}B$。

在計算機科學和數理邏輯中，自然數集合的圖靈度或者不可解度是對此集合的算法不可解性的度量。圖靈度在可計算理論中是根本性的概念，在可計算理論里，自然數集合通常被看作一個判定問題，而圖靈度則給出了解決與此集合相連的判定問題的困難程度。

如果兩集合$A,B$有同一不可解度（也即兩者互相圖靈可計算），則稱兩集合為圖靈等價，記作$A\equiv _{T}B$。圖靈等價是一個等價關係，其等價類稱作不可解度。圖靈可計算關係是所有不可解度的搜集上的偏序。所有可計算集合（也即圖靈等價於空集的集合）的不可解度為$\mathbf {0}$（零度）。

所有不可解度的搜集記作${\mathcal {D}}$。

圖靈跳躍

圖靈跳躍算符是不可解度上的算符。設$A$為一集合，則其圖靈跳躍$A^{\prime }$的不可解度，為所有具備集合$A$的停機問題的預言機的集合的不可解度。

零度的圖靈跳躍是停機問題的不可解度，也即$\mathbf {0} ^{\prime }$。

圖靈錐

設$C$為不可解度，則所有可計算$C$的不可解度的搜集$\operatorname {Cone} (C):=\{D\in {\mathcal {D}}\;\vert \;D\geq _{T}C\}$叫做$C$上的圖靈錐。

定理

• 波斯特定理
• 克萊尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯納–羅賓遜定理
• 跳躍逆轉定理

參考資料

• Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 （英語）.