基本介紹
名詞解析,定義,圖靈跳躍,圖靈錐,
名詞解析
不可解度:數學邏輯名詞,即函式f由函式g圖靈可計算,並且g由f圖靈可計算時,稱f和g具有相同的圖靈不可解性的度。
在計算機科學和數理邏輯中,自然數集合的圖靈度或者不可解度是對此集合的算法不可解性的度量。圖靈度在可計算理論中是根本性的概念,在可計算理論里,自然數集合通常被看作一個判定問題,而圖靈度則給出了解決與此集合相連的判定問題的困難程度。
定義
假設一個圖靈機程式可以隨意獲取自然數函式g的值(即使g不可計算),且該圖靈機計算自然數函式 f,則定義函式f由函式g圖靈可計算,記作。符合以上特點的圖靈機稱為具備函式g的預言機。若集合B的特徵函式可計算集合A,則。
在計算機科學和數理邏輯中,自然數集合的圖靈度或者不可解度是對此集合的算法不可解性的度量。圖靈度在可計算理論中是根本性的概念,在可計算理論里,自然數集合通常被看作一個判定問題,而圖靈度則給出了解決與此集合相連的判定問題的困難程度。
如果兩集合 A,B有同一不可解度(也即兩者互相圖靈可計算),則稱兩集合為圖靈等價,記作。圖靈等價是一個等價關係,其等價類稱作不可解度。圖靈可計算關係是所有不可解度的蒐集上的偏序。所有可計算集合(也即圖靈等價於空集的集合)的不可解度為(零度)。
所有不可解度的蒐集記作。
圖靈跳躍
零度的圖靈跳躍是停機問題的不可解度,也即。
圖靈錐
設 C為不可解度,則所有可計算C的不可解度的蒐集叫做C上的圖靈錐。