2.3 可計算性

可計算性理論起源于20世紀30年代圖靈、丘奇和哥德爾等人的工作。P類與NP類在可計算性方面的早期研究分別是可確定性語言類和可計算枚舉語言類。令L為一個語言，則L是可判定的當且僅當存在某個圖靈機M滿足L=L(M)且M對所有的輸入都停機；L是半可判定的當且僅當存在某個圖靈機M使得L=L(M)，即存在一個可計算的“檢查關系”R(x,y)，使得。

下面從函數的角度探討可計算性，即把語言看作到的函數。這樣，并不是所有的函數都是可計算的。定理2.12說明了不可計算函數的存在性。事實上，該定理證明了值域為的不可計算函數的存在性。值域為的不可計算函數也就是不可判定語言。

定理2.12　存在不能被任意圖靈機計算的函數UC:[23]。　　　　█

停機問題　函數HALT以有序對為輸入，它輸出1當且僅當表示的圖靈機在輸入上會在有限步驟內停機[23]。

HALT是需要計算的函數。因為給定一個計算機程序和輸入之后，人們肯定希望知道該程序在該輸入上是否會陷入無限循環。如果計算機能夠計算函數HALT，則設計無缺陷（bug）的計算機軟件和硬件將變得容易很多。遺憾的是，已經證明計算機無法計算這個函數，即使允許運行足夠長的時間。

定理2.13　函數HALT不能被任意圖靈機計算[23]。　　　　█

定理2.13說明停機問題是不可判定的。但是，停機問題是半可判定的。

下面介紹可計算性理論中基本的概念——可歸約性。

定義2.1　令和分別是符號集和上的兩個語言，即、。那么，是多對一歸約到（或稱多項式時間可歸約到，用表示）的當且僅當存在可計算函數f（存在確定性圖靈機M，使得對任意作為輸入，M都可以在多項式時間內停機且輸出）：使得對于所有的，當且僅當。滿足定義2.1的可計算函數稱為到的多項式時間變換。

如果并且是可判定的，那么容易推出L₁也是可判定的。這種發現可以用來說明語言的不可判定性。例如，若停機問題可以多對一歸約到某個語言L，那么L是不可判定的。多對一歸約具有傳遞性。

定理2.14 設、、分別是字符集、、上的語言，并且、，則 [23]。　　　　█