標籤: 暫無標籤

不可解度 degrees of unsolvability 從比較計算難易程度出發來研究自然數子集分類的遞歸論分支。在某種標準下計算難度相同的集合形成這種標準下的一個度。

1 不可解度 -不可解度

 

2 不可解度 -正文

  從比較計算難易程度出發來研究自然數子集分類的遞歸論分支。在某種標準下計算難度相同的集合形成這種標準下的一個度。遞歸論中研究得比較多的兩種度是m度與圖靈度。
  設AB是兩個非負整數的子集,假若存在遞歸函數ƒ使得

不可解度

則稱Am歸約於B(見圖1不可解度)並記為

不可解度

如果Am歸約於B,就把判定x是否屬於A的問題化歸為判定ƒ(x)是否屬於B的問題,因為ƒ是可計算函數,所以關於A的判定計算問題不難於B,而且若B是可計算的則A也是可計算的。如果不可解度不可解度,則稱ABm等價的並記為不可解度,類不可解度被稱為Am度。假若B是遞歸可枚舉集且任何遞歸可枚舉集A都可m歸約於B,則稱Bm完備的。關於圖靈機停機問題的集合不可解度就是一個m完備集。
  設B的補集為峫,要判定元素x在不在中,只要判定x在不在B中就可以了,因此直觀上峫應該可歸約於B。但是上面給出的m歸約辦不到這一點。例如,噖 不可m歸約於K。因此需要有新的更一般的歸約標準,圖靈歸約(見圖2不可解度)是其中最重要的一個。
  稱「A圖靈歸約於B」(或「A遞歸於B」,或「A相對於B可計算」)是指:有一個演算法T,當輸入非負整數x時,依據該演算法進行的計算過程中,可以隨時向外息源詢問「y是否屬於B」這樣的問題,並根據外息源的回答來決定下一步計算怎樣進行,直到給出x是否屬於A時為止。
  用「不可解度」表示"A圖靈歸約於B",用「不可解度」表示 「不可解度不可解度」。記不可解度並稱其為A的圖靈度。若不可解度則記作deg(A)≤deg(B)。若deg(A)≤deg(B)但不可解度則記作deg(A)B)。若不可解度不可解度則稱deg(A)與deg(B)為不可比度。若B是遞歸可枚舉集且對任何遞歸可枚舉集A都有AiB,則稱B是(圖靈)完備集。K與噖 是完備集。
  一切遞歸集形成一個度,用Ο表示遞歸集的度。因為任何集B與遞歸集A有關係不可解度,所以對任何度a都有Ο≤a,即Ο是最小的度。用Ο┡表示完備集K的度,顯然任何完備集都在度Ο┡中。因為K不是遞歸集,故有Ο<Ο┡。用【Ο,Ο┡】表示度類{a:Ο≤a≤Ο┡}。
  一個度中若有一個遞歸可枚舉集,則稱這個度為遞歸可枚舉度。因為Ο┡是完備集的度,所以對任何遞歸可枚舉度a都有Ο≤a≤Ο┡。是否有遞歸可枚舉度a使Ο<a<Ο┡呢?這個問題是遞歸論中有名的波斯特問題。1956~1957年,A.A.穆切尼克與R.M.弗里德貝格創造了有窮損害方法證明了在【Ο,Ο┡】中有兩個互不可比的遞歸可枚舉度,從而肯定地解決了波斯特問題。
  稱集合不可解度為集合A的躍變,把A的躍變記為A┡。 度a=deg(A)的躍變度記為a┡=deg(A┡)。度Ο的躍變度是Ο┡。對於任何遞歸可枚舉度a,它的躍變度a┡滿足Ο┡≤a┡≤Ο″,若有Ο┡=a┡則稱遞歸可枚舉度a為低度,若有Ο″=a┡則稱a為高度。
  存在度α使Ο<α<Ο┡且對任何度bb≠Ο則bα,這樣的度a叫極小度。不存在非Ο的遞歸可枚舉度是極小度。【Ο,Ο┡】的基數與實數區間【0,1】的基數相同,【Ο,Ο┡】也存在類似的稠密性質。【Ο,Ο┡】是上半格但不是格,每一個可數分配格都可嵌入 【Ο,Ο┡】中。存在一對非Ο的遞歸可枚舉度,它們的最大下界是Ο;不存在一對非Ο的遞歸可枚舉度,它們的最大下界是Ο而最小上界則是Ο┡。
  研究在【Ο,Ο┡】上的偏序性質特別是代數結構性質是不可解度理論的重要內容。

 

3 不可解度 -配圖

 

4 不可解度 -相關連接

上一篇[最小元]    下一篇 [張文偉]

相關評論

同義詞:暫無同義詞