不可解度

不可解度，或圖靈度，是數學邏輯的名詞，尤其套用在可計算性理論中。是從比較計算難易程度出發來研究自然數子集分類的遞歸論分支。在某種標準下計算難度相同的集合形成這種標準下的一個度。

基本介紹

• 中文名：不可解度
• 外文名：degrees of unsolvability
• 別稱：圖靈度
• 套用領域：可計算性理論
• 套用學科：數學
• 性質：數學邏輯名詞

名詞解析

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

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

定義

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

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

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

所有不可解度的蒐集記作。

圖靈跳躍

圖靈跳躍算符是不可解度上的算符。設A為一集合，則其不可解度的圖靈跳躍為所有停機的具備集合A的預言機的集合的不可解度。

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

圖靈錐

設 C為不可解度，則所有可計算C的不可解度的蒐集叫做C上的圖靈錐。