可計算性理論（Computability theory）作為計算理論的一個分支，研究在不同的計算模型下哪些算法問題能夠被解決。相對應的，計算理論的另一塊主要內容，計算複雜性理論考慮一個問題怎樣才能被有效的解決。可計算理論的研究對象有三個 ： ( 1) 判定問題； ( 2) 可計算函式；( 3) 計算複雜性。
基本介紹
- 中文名：可計算性理論
- 外文名：computability theory
- 學科：計算機、數學
- 又稱：算法理論
- 基礎：算法設計與分析的基礎
- 套用領域：並行計算、人工智慧
簡介,計算模型,有關術語,可計算性等級,停機問題,不可解度,相關函式,轉換演算,遞歸函式,部分函式,套用領域,
簡介
可計算性理論，亦稱算法理論或能行性理論，計算機科學的理論基礎之一。是研究計算的一般性質的數學理論。可計算性理論通過建立計算的數學模型，精確區分哪些是可計算的，哪些是不可計算的。計算的過程是執行算法的過程。可計算性理論的重要課題之一，是將算法這一直觀概念精確化。算法概念精確化的途徑很多，其中之一是通過定義抽象計算機，把算法看作抽象計算機的程式。通常把那些存在算法計算其值的函式叫做可計算函式。因此，可計算函式的精確定義為：能夠在抽象計算機上編出程式計算其值的函式。這樣就可以討論哪些函式是可計算的，哪些函式是不可計算的。
套用計算性理論是計算機科學的理論基礎之一。早在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 機( 部分) 可計算函式及其等價的概念作為可計算函式的嚴格定義。
有關術語
可計算性等級
在數學中，可計算性是函式的一個特性。定義域為D和范 圍為R的函式f有一個確定的對應關係。通過這個 對應關係使R範圍的單個元素f(x) (稱為 值) 和D定義域的每個元素x(稱為變元)聯繫起來。 如果存在這樣一種算法，給定D中的任意的x，就 能給出f(x)的值，那么說函式f是可計算的。
在計算機中，可計算性（calculability）是指一個實際問題是否可以使用計算機來解決．從廣義上講如“為我烹製一個漢堡”這樣的問題是無法用計算機來解決的（至少在目前）。而計算機本身的優勢在於數值計算，因此可計算性通常指這一類問題是否可以用計算機解決．事實上，很多非數值問題（比如文字識別，圖象處理等）都可以通過轉化成為數值問題來交給計算機處理，但是一個可以使用計算機解決的問題應該被定義為“可以在有限步驟內被解決的問題”，故哥德巴赫猜想這樣的問題是不屬於“可計算問題”之列的，因為計算機沒有辦法給出數學意義上的證明，因此也沒有任何理由期待計算機能解決世界上所有的問題。分析某個問題的可計算性意義重大，它使得人們不必浪費時間在不可能解決的問題上（因而可以儘早轉而使用除計算機以外更加有效的手段），集中資源在可以解決的問題上。
這樣我們可以定義可計算性等級：所有的語言的集合，記為All；遞歸可枚舉語言，即可以被圖靈機枚舉的語言的集合，記為RE；遞歸語言，即可以被圖靈機決定的語言的集合，記為R。可見，即形成可計算性等級。那么產生相關的問題即是兩個包含關係是不是嚴格的，即是否有在All而不在RE中的語言，以及在RE而不在R中的語言。阿蘭·圖靈在1930年代的工作表明這兩個包含關係都是不嚴格的，即可以證明存在語言L_d，是不能被圖靈機所枚舉的，以及存在語言L_u，是不能被圖靈機所決定的。證明的主要思想是對角線法。
停機問題
停機問題就是判斷任意一個程式是否會在有限的時間之內結束運行的問題。該問題等價於如下的判定問題：給定一個程式P和輸入w，程式P在輸入w下是否能夠最終停止。
不可解度
不可解度的概念定義了不可解的集合之間的相對計算難度。例如，不可解的停機問題顯然比任何可解的集合都要難，然而同樣不可解的“元停機問題”（即所有具備停機問題的預言機的停機問題）卻要難過停機問題，因為具備元停機問題的預言機可以解出停機問題，然而具備停機問題的預言機卻不能解出元停機問題。
相關函式
轉換演算
一種定義函式的形式演算系統，是A.丘奇於1935年為精確定義可計算性而提出的。他引進λ記號以明確區分函式和函式值，並把函式值的計算歸結為按一定規則進行一系列轉換，最後得到函式值。按照λ轉換演算能夠得到函式值的那些函式稱為λ可定義函式（見λ轉換演算）。
遞歸函式
比如，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) 並行計算( 網路計算、分散式並行計算、大規模並行計算、演化算法等)
