圖靈歸約

若問題A可圖靈歸約成問題B，是指若問題B的解答已經知道（Rogers 1967, Soare 1987），就可以解問題A，也可以解釋為若一個算法可以用來處理問題B，就可以處理問題A。較正式的説法，可被圖靈歸約成問題B的問題是指若存在問題B的預言機，就可以求解的問題集合。圖靈歸約可以用在決定性問題及功能性問題。 ^[1] 

我們考慮關於圖靈機的可計算性理論。本節中，固定字符集是{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下是否能夠最終停止。

Post對應問題（Post's correspondence problem）。

不可解度的概念定義了不可解的集合之間的相對計算難度。例如，不可解的停機問題顯然比任何可解的集合都要難，然而同樣不可解的“元停機問題”（即所有具備停機問題的預言機的停機問題）卻要難過停機問題，因為具備元停機問題的預言機可以解出停機問題，然而具備停機問題的預言機卻不能解出元停機問題。

在可計算性理論與計算複雜性理論中，所謂的歸約是將某個計算問題轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。

以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程序，則將問題A稱為“可歸約”到問題B，因此求解A並不會比求解B更困難。

一般寫作A ≤_mB，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。

將一組問題歸約到特定類型所產生的數學結構，通常形成預序關係，其等價類可用於定義求解難度和複雜度。