不可解度

不可解度：數學邏輯名詞，即函數f由函數g圖靈可計算，並且g由f圖靈可計算時，稱f和g具有相同的圖靈不可解性的度。

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

假設一個圖靈機程序可以隨意獲取自然數函數g的值（即使g不可計算），且該圖靈機計算自然數函數 f，則定義函數f由函數g圖靈可計算，記作

。符合以上特點的圖靈機稱為具備函數g的預言機。若集合B的特徵函數可計算集合A，則

。 ^[1] 

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

如果兩集合 A,B有同一不可解度（也即兩者互相圖靈可計算），則稱兩集合為圖靈等價，記作

。圖靈等價是一個等價關係，其等價類稱作不可解度。圖靈可計算關係是所有不可解度的蒐集上的偏序。所有可計算集合（也即圖靈等價於空集的集合）的不可解度為

（零度）。

所有不可解度的蒐集記作

。

圖靈跳躍算符是不可解度上的算符。設A為一集合，則其不可解度的圖靈跳躍

為所有停機的具備集合A的預言機的集合的不可解度。

零度的圖靈跳躍是停機問題的不可解度，也即

。

設 C為不可解度，則所有可計算C的不可解度的蒐集

叫做C上的圖靈錐。