可計算性理論
正文
研究計算的一般性質的數學理論，也稱算法理論或能行性理論。它通過建立計算的數學模型（例如抽象計算機），精確區分哪些是可計算的，哪些是不可計算的。計算的過程就是執行算法的過程。可計算性理論的重要課題之一，是將算法這一直觀概念精確化。算法概念精確化的途徑很多，其中之一是通過定義抽象計算機，把算法看作抽象計算機的程式。通常把那些存在算法計算其值的函式叫作可計算函式。因此，可計算函式的精確定義為：能夠在抽象計算機上編出程式計算其值的函式。這樣就可以討論哪些函式是可計算的，哪些函式是不可計算的。產生和歷史 可計算性理論起源於對數學基礎問題的研究。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.
