可計算性理論

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

應用計算性理論是計算機科學的理論基礎之一。早在30年代，圖靈對存在通用圖靈機的邏輯證明表明，製造出能編程序來作出任何計算的通用計算機是可能的，這影響了40年代出現的存儲程序的計算機（即馮諾依曼型計算機）的設計思想。可計算性理論確定了哪些問題可能用計算機解決，哪些問題是不可能用計算機解決的。

可計算性理論中的基本思想、概念和方法，被廣泛用用與計算機科學的各個領域。建立數學模型的方法在計算機科學中被廣泛採用。遞歸的思想被用於程序設計，產生了遞歸過程和遞歸數據結構，也影響了計算機的體系結構。

可計算理論的計算模型主要包括: ( 1)Turing 機； ( 2) 遞歸函數 ； ( 3) λ演算 ；( 4) POST 系統；( 5) 正則算法。 第一個模型是程序設計語言 S，該程序語言定義了 1) 變量；2) 標號； 3)語句； 4) 指令；5) 程序； 6) 狀態;；7) 快相； 8) 後繼； 9)計算。 設f(x 1 , x 2 , …, x n )是一個部分函數， 如果存在程序 S 計算 f ，則稱 f 是部分可計算函數。 從而, 一個函數是否是可計算的,只需要判斷是否可以構造對應的程序 S 即可。可計算函數經過原始遞歸運算還是可計算函數。 給出了通用程序的概念， 任意程序和輸入x 1 , x 2 , …( y = # ( ) ), 存在通用程序以 x 1 , x 2 , …, x n 和y 作為輸入 ，計算結果恰好等於程序的計算結果。“ 參數定理” 、“ 遞歸定理”提供了判斷一個函數是否可計算的方法，從基本的可計算函數推道出其他函數是否可計算，而不需要構造程序證明其可計算 。

另一個計算模型是語言 hn, 該模型為字符串運算設計的。 設字母表 A 中有 n 個符號, 如果 A上的m 元部分函數能用程序計算, 則這個函數是可計算的。 Post-Turing 語言也是面向字符串運算的程序設計語言, 要處理的字符串存在一條帶上。Post-Turing 程序ζ計算的 A 上m 元部分函數定義為對任意給定的輸入 x 1 , x 2 , …, x n ∈A, 從初始帶格局開始, 如果計算最終停止, 則部分函數等於計算停止時從帶的內容中刪除不屬於 A 的符號後得到的字符串; 如果計算不停止, 則部分函數無定義。 圖靈機 μ由六部分組成：( 1) 有窮狀態集,，( 2) 字母表，( 3) 動作函數， ( 4)輸入字母表，( 5) 空白符 B， ( 6) 初始態 q1。 上述計算模型等價性的證明， 主要採用將一種模型用另一種模型表示的方法證明。 可計算理論中，計算模型很多, 如有窮自動機, 正則算法在本質上都與圖靈機相似。 Church-Turing 論題指出： 通常説的能行可計算函數等同於部分遞歸函數, 也等同於Turing 機計算的部分函數； 也就是説， Turing 機可計算性與遞歸性是等價的。 因此, 把遞歸函數、Turing 機( 部分) 可計算函數及其等價的概念作為可計算函數的嚴格定義。 ^[1] 

在數學中，可計算性是函數的一個特性。定義域為D和範 圍為R的函數f有一個確定的對應關係。通過這個 對應關係使R範圍的單個元素f(x) (稱為 值) 和D定義域的每個元素x(稱為變元)聯繫起來。 如果存在這樣一種算法，給定D中的任意的x，就 能給出f(x)的值，那麼説函數f是可計算的。 ^[3] 

在計算機中，可計算性（calculability）是指一個實際問題是否可以使用計算機來解決．從廣義上講如“為我烹製一個漢堡”這樣的問題是無法用計算機來解決的（至少在目前）。而計算機本身的優勢在於數值計算，因此可計算性通常指這一類問題是否可以用計算機解決．事實上，很多非數值問題（比如文字識別，圖象處理等）都可以通過轉化成為數值問題來交給計算機處理，但是一個可以使用計算機解決的問題應該被定義為“可以在有限步驟內被解決的問題”，故哥德巴赫猜想這樣的問題是不屬於“可計算問題”之列的，因為計算機沒有辦法給出數學意義上的證明，因此也沒有任何理由期待計算機能解決世界上所有的問題。分析某個問題的可計算性意義重大，它使得人們不必浪費時間在不可能解決的問題上（因而可以儘早轉而使用除計算機以外更加有效的手段），集中資源在可以解決的問題上。

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

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

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

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

自變量值和函數值都是自然數的函數，稱為數論函數。原始遞歸函數是數論函數的一部分。首先規定少量顯然直觀可計算的函數為原始遞歸函數，它們是：函數值恆等於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不終止。

由於可計算理論的建立，才出現了現代的計算機系統，此學科無疑是計算機科學的基礎。 計算機科學分為計算機理論和計算機應用。 計算機基礎理論包含以下幾部分：

( 1) 程序理論( 程序邏輯、程序正確性驗證、形式開發方法等)

( 2) 計算理論( 算法設計與分析、複雜性理論、可計算性理論等)

( 3) 語言理論( 形式語言理論、自動機理論、形式語義學、計算語言學等)

( 4) 人工智能( 知識工程、機器學習、模式識別、機器人等)

( 5) 邏輯基礎( 數理邏輯、多值邏輯、模糊邏輯、模態邏輯、直覺主義邏輯、組合邏輯等)

( 6) 數據理論( 演繹數據庫、關係數據庫、面向對象數據庫等)

( 7) 計算機數學( 符號計算、數學定理證明、計算幾何等）

( 8) 並行計算( 網絡計算、分佈式並行計算、大規模並行計算、演化算法等) ^[1]