可計算性理論

研究計算的一般性質的數學理論，也稱演演算法理論或能行性理論。它通過建立計算的數學模型（例如抽象計算機），精確區分哪些是可計算的，哪些是不可計算的。計算的過程就是執行演演算法的過程。可計算性理論的重要課題之一，是將演演算法這一直觀概念精確化。演演算法概念精確化的途徑很多，其中之一是通過定義抽象計算機，把演演算法看作抽象計算機的程序。通常把那些存在演演算法計算其值的函數叫作可計算函數。因此，可計算函數的精確定義為：能夠在抽象計算機上編出程序計算其值的函數。這樣就可以討論哪些函數是可計算的，哪些函數是不可計算的。

產生和歷史 可計算性理論起源於對數學基礎問題的研究。20世紀30年代，為了討論是否對於每個問題都有解決它的演演算法，數理邏輯學家提出了幾種不同的演演算法定義。K.哥德爾和S.C.克林尼提出了遞歸函數的概念，A.丘奇提出λ轉換演算, A.M.圖靈和E.波斯特各自獨立地提出了抽象計算機的概念（後人把圖靈提出的抽象計算機稱為圖靈機），並且證明了這些數學模型的計算能力是一樣的，即它們是等價的。著名的丘奇-圖靈論題也是丘奇和圖靈在這一時期各自獨立提出的。後來，人們又提出許多等價的數學模型，如A.馬爾可夫於40年代提出的正規演演算法（後人稱之為馬爾可夫演演算法），60年代前期提出的隨機存取機器模型（簡稱 RAM）等。50年代末和60年代初，胡世華和J.麥克阿瑟等人各自獨立地提出了定義在字元串上的遞歸函數。

學科內容 若m和n是兩個正整數，並且m≥n時，求m和n的最大公因子的歐幾里得演演算法可表示為

E1［求餘數］以n 除m 得餘數r。

E2［餘數為0嗎?］若r＝0,計算結束,n即為答案；否則轉到步驟E3。

E3［互換］把m的值變為n,n的值變為r，重複上述步驟。

依照這三條規則指示的步驟，可計算出任何兩個正整數的最大公因子。可以把計算過程看成執行這些步驟的序列。我們發現，計算過程是有窮的，而且計算的每一步都是能夠機械實現的（機械性）。為了精確刻劃演演算法的特徵，人們建立了各種各樣的數學模型。

圖靈機 一種在理論計算機科學中廣泛採用的抽象計算機，它是圖靈在1936年提出的，用於精確描述演演算法的特徵。可用一個圖靈機來計算其值的函數是可計算函數，找不到圖靈機來計算其值的函數是不可計算函數。可以證明，存在一個圖靈機U,它可以模擬任何其他的圖靈機。這樣的圖靈機 U稱為通用圖靈機。通用圖靈機正是後來出現的存儲指令的通用數字計算機的理論原型。

λ轉換演算 一種定義函數的形式演算系統，是A.丘奇於1935年為精確定義可計算性而提出的。他引進λ記號以明確區分函數和函數值，並把函數值的計算歸結為按一定規則進行一系列轉換，最後得到函數值。按照λ轉換演算能夠得到函數值的那些函數稱為λ可定義函數（見λ轉換演算）。

丘奇-圖靈論題 可計算性理論的基本論題，也稱圖靈論題，它規定了直觀可計算函數的精確含義。丘奇論題說：λ可定義函數類與直觀可計算函數類相同。圖靈論題說：圖靈機可計算函數類與直觀可計算函數類相同。圖靈證明了圖靈機可計算函數類與λ可定義函數類相同。這表明圖靈論題和丘奇論題講的是一回事，因此把它們統稱為丘奇－圖靈論題。直觀可計算函數不是一個精確的數學概念，因此丘奇-圖靈論題是不能加以證明的。30年代以來，人們提出了許多不同的計算模型來精確刻劃可計算性，並且證明了這些模型都與圖靈機等價。這表明圖靈機和其他等價的模型確實合理地定義了可計算性，因此丘奇－圖靈論題得到了計算機科學界和數學界的公認。

原始遞歸函數自變數值和函數值都是自然數的函數，稱為數論函數。原始遞歸函數是數論函數的一部分。首先規定少量顯然直觀可計算的函數為原始遞歸函數，它們是：函數值恆等於0的零函數C0,函數值等於自變數值加1的後繼函數S，函數值等於第i個自變數值的n元投影函數P嬪。然後規定，原始遞歸函數的合成仍是原始遞歸函數，可以由已知原始遞歸函數簡單遞歸地計算出函數值的函數仍是原始遞歸函數。例如，和函數f(x，y)=x+y可由原始遞歸函數P(1)1和S遞歸地計算出函數值

f(x，0)=P(1)1(x) f(x，S(y))=S(f(x，y))

比如，f(4，2)可這樣計算，首先算出f(4，0)=P(1)1(4)=4，然後計算

f(4，1)=S(f(4，0))=S(4)=5

f(4，2)=S(f(4，1))=S(5)=6

因此，和函數是原始遞歸函數。顯然，一切原始遞歸函數都是直觀可計算的。許多常用的處處有定義的函數都是原始遞歸函數，但並非一切直觀可計算的、處處有定義的函數都是原始遞歸函數。

部分遞歸函數 為了包括所有的直觀可計算函數，需要把原始遞歸函數類擴充為部分遞歸函數類。設g(x1，…,xn,z)是原始遞歸函數，如果存在自然數z使g(x1,…，xn,z)=0,就取f(x1,…,xn)的值為滿足g(x1,…,xn,z)=0的最小的自然數z；如果不存在使g(x1,…,xn,z)=0的自然數z,就稱f(x1,…,xn)無定義。把如上定義的函數f加到原始遞歸函數類中，就得到部分遞歸函數類。因為不能保證如上定義的f在一切點都有定義，故稱其為部分函數。處處有定義的部分遞歸函數稱為遞歸函數。部分遞歸函數類與圖靈機可計算函數類相同。對於每個n元部分遞歸函數f,可以編一個計算機程序P,以自然數x1,…，xn作為輸入，若f(x1,…,xn)有定義，則P函數值執行終止並輸出的f(x1,…,xn)，否則P不終止。

遞歸集 遞歸集最初是對於元素都是自然數的集合定義的，它們是有演演算法確定每個自然數是否為其元素的集合。可以將遞歸集的概念推廣到其他集合。所討論的對象的全體稱為域，如果有演演算法確定域中任意元素是否屬於A，則稱A為遞歸集。對於每個遞歸集，可以編一個計算機程序，以域中任意元素作為輸入，計算執行該程序都可給出適當的輸出，表明該元素是否屬於這個遞歸集。有許多集合不是遞歸集。

遞歸可枚舉集 如果對於集合A可以編一個程序P，輸入域中任意元素x，若x∈A，則P的執行將終止並輸出“是”,否則P 的執行不終止，就稱A為遞歸可枚舉集。A為遞歸可枚舉集的充分必要條件是可以編一個程序枚舉A的元素，即列印A的元素，使得對於 A中任意元素，只要時間足夠長總會在列印紙上出現。遞歸集都是遞歸可枚舉集，但有些遞歸可枚舉集不是遞歸集。有許多集合不是遞歸可枚舉集。

可判定性和半可判定性 判定問題是無窮多個同類個別問題的總稱。例如，2是不是素數？6是不是素數？這些都是個別問題，把這類個別問題概括起來，就得到一個判定問題：任意給定的正整數是不是素數？這裡的正整數集合稱為該判定問題的域，給定域中的一個元素，判定問題就對應一個個別問題。對於一個判定問題，如果能夠編出一個程序，以域中任意元素作為輸入，執行該程序就能給出相應的個別問題的答案，就稱該判定問題為可判定的。例如，“任意正整數是不是素數”這個問題就是可判定的。對於集合A,域中任意元素是否屬於它的問題稱為集合 A對應的判定問題。集合是遞歸集的充分必要條件為對應的判定問題是可判定的。因此，全體素數的集合是遞歸集。

對於一個判定問題，如果能夠編出一個程序P,以域中任意元素作為輸入，當相應的個別問題的解答是肯定的時候,P 的執行將終止並輸出“是”,否則P 的執行不終止，就稱該判定問題為半可判定的。可判定的問題總是半可判定的。集合是遞歸可枚舉集的充分必要條件為對應的判定問題是半可判定的。

圖靈在1936年證明，圖靈機的停機問題是不可判定的，即不存在一個圖靈機能夠判定任意圖靈機對於任意輸入是否停機。圖靈機的停機問題是半可判定的。圖靈機的停機問題是很重要的，由它可以推出計算機科學、數學、邏輯學中的許多問題是不可判定的。

應用 可計算性理論是計算機科學的理論基礎之一。早在30年代，圖靈對存在通用圖靈機的邏輯證明表明，製造出能編程序來作出任何計算的通用計算機是可能的，這影響了40年代出現的存儲程序計算機（即諾伊曼型計算機）的設計思想。可計算性理論確定了哪些問題可能用計算機解決，哪些問題不可能用計算機解決。例如，圖靈機的停機問題是不可判定的表明，不可能用一個單獨的程序來判定任意程序的執行是否終止，避免了人們為編製這樣的程序而無謂地浪費精力。

可計算性理論中的基本思想、概念和方法，被廣泛應用於計算機科學的各個領域。建立數學模型的方法在計算機科學中被廣泛採用。遞歸的思想被用於程序設計，產生了遞歸過程和遞歸數據結構，也影響了計算機的體系結構。λ演算被用於研究程序設計語言的語義，例如，表處理語言就以λ轉換演算為理論基礎。

參考書目

H.Rogers, Theory　of　Recursive　Functions and Effective　Computability, McGraw－Hill, New York,1967.

F. Hennie,Introduction to Computability,Addison-Wesley, Masschusetts,1977.