基本介紹
- 中文名：圖靈歸約
- 理論：可計算性理論
- 學科：計算機
- 領域：計算機
簡介,圖靈機的可計算性理論,可計算性等級,停機問題,PCP問題,不可解度,歸約,
簡介
圖靈歸約是可計算性理論中的一種歸約，若問題A可圖靈歸約成問題B，是指若問題B的解答已經知道（Rogers 1967, Soare 1987），就可以解問題A，也可以解釋為若一個算法可以用來處理問題B，就可以處理問題A。較正式的說法，可被圖靈歸約成問題B的問題是指若存在問題B的預言機，就可以求解的問題集合。圖靈歸約可以用在決定性問題及功能性問題。
圖靈機的可計算性理論
我們考慮關於圖靈機的可計算性理論。本節中，固定字元集是{0, 1}，
是所有有限長度字元串的集合。一個語言即是
的一個子集。
一個語言L是可以被圖靈機所枚舉（enumerate）的，如果存在一個圖靈機 M，使得輸入是L中的串時，M輸出“接受”；而對非L中的串，M輸出“拒絕”或不停機。而一個語言L'是可以被圖靈機所決定（decide）的，如果存在一個圖靈機M'，使得輸入是L中的串時，M輸出“接受”；而對非L中的串，M輸出“拒絕”。注意這裡的區別在於，對於圖靈機決定的語言，我們需要在所有輸出上，該圖靈機都要停機。
可計算性等級
這樣我們可以定義可計算性等級：所有的語言的集合，記為All；遞歸可枚舉語言，即可以被圖靈機枚舉的語言的集合，記為RE；遞歸語言，即可以被圖靈機決定的語言的集合，記為R。可見
，即形成可計算性等級。那么產生相關的問題即是兩個包含關係是不是嚴格的，即是否有在All而不在RE中的語言，以及在RE而不在R中的語言。阿蘭·圖靈在1930年代的工作表明這兩個包含關係都是不嚴格的，即可以證明存在語言L_d，是不能被圖靈機所枚舉的，以及存在語言L_u，是不能被圖靈機所決定的。證明的主要思想是對角線法。
停機問題
停機問題就是判斷任意一個程式是否會在有限的時間之內結束運行的問題。該問題等價於如下的判定問題：給定一個程式P和輸入w，程式P在輸入w下是否能夠最終停止。
PCP問題
Post對應問題（Post's correspondence problem）。
不可解度
不可解度的概念定義了不可解的集合之間的相對計算難度。例如，不可解的停機問題顯然比任何可解的集合都要難，然而同樣不可解的“元停機問題”（即所有具備停機問題的預言機的停機問題）卻要難過停機問題，因為具備元停機問題的預言機可以解出停機問題，然而具備停機問題的預言機卻不能解出元停機問題。
歸約
以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程式，則將問題A稱為“可歸約”到問題B，因此求解A並不會比求解B更困難。
一般寫作A ≤mB，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。
將一組問題歸約到特定類型所產生的數學結構，通常形成預序關係，其等價類可用於定義求解難度和複雜度。
