可計算性理論

在計算機科學中，可計算性理論（Computability theory）作為計算理論的一個分支，研究在不同的計算模型下哪些算法問題能夠被解決。相對應的，計算理論的另一塊主要內容，計算複雜性理論考慮一個問題怎樣才能被有效的解決。

歷史與遞歸論的聯繫

計算模型

圖靈機的可計算性理論

我們考慮關於圖靈機的可計算性理論。本節中，固定字符集是{0, 1}， ${0,1}^{*}$ 是所有有限長度字符串的集合。一個語言即是 ${0,1}^{*}$ 的一個子集。

一個語言L是可以被圖靈機所枚舉（enumerate）的，如果存在一個圖靈機 $M$ ，使得輸入是L中的串時，M輸出「接受」；而對非L中的串，M輸出「拒絕」或不停機。而一個語言L'是可以被圖靈機所決定（decide）的，如果存在一個圖靈機M'，使得輸入是L中的串時，M輸出「接受」；而對非L中的串，M輸出「拒絕」。注意這裡的區別在於，對於圖靈機決定的語言，我們需要在所有輸出上，該圖靈機都要停機。

可計算性等級

這樣我們可以定義可計算性等級：所有的語言的集合，記為All；遞歸可枚舉語言，即可以被圖靈機枚舉的語言的集合，記為RE；遞歸語言，即可以被圖靈機決定的語言的集合，記為R。可見 $R\subseteq RE\subseteq All$ ，即形成可計算性等級。那麼產生相關的問題即是兩個包含關係是不是嚴格的，即是否有在All而不在RE中的語言，以及在RE而不在R中的語言。阿蘭·圖靈在1930年代的工作表明這兩個包含關係都是嚴格的，即可以證明存在語言L_d，是不能被圖靈機所枚舉的，以及存在語言L_u，是不能被圖靈機所決定的。證明的主要思想是對角論證法。

停機問題

停機問題就是判斷任意一個程序是否會在有限的時間之內結束運行的問題。該問題等價於如下的判定問題：給定一個程序P和輸入w，程序P在輸入w下是否能夠最終停止。

PCP問題

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

不可解度

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

更強的模型

帶神諭的圖靈機（預言機）

定理

外部連結

可計算性理論^{[永久失效連結]}