[科普中國]-可計算性理論

簡介

可計算性理論，亦稱算法理論或能行性理論，計算機科學的理論基礎之一。是研究計算的一般性質的數(shù)學理論?？捎嬎阈岳碚撏ㄟ^建立計算的數(shù)學模型2，精確區(qū)分哪些是可計算的，哪些是不可計算的。計算的過程是執(zhí)行算法的過程?？捎嬎阈岳碚摰闹匾n題之一，是將算法這一直觀概念精確化。算法概念精確化的途徑很多，其中之一是通過定義抽象計算機，把算法看作抽象計算機的程序。通常把那些存在算法計算其值的函數(shù)叫做可計算函數(shù)。因此，可計算函數(shù)的精確定義為：能夠在抽象計算機上編出程序計算其值的函數(shù)。這樣就可以討論哪些函數(shù)是可計算的，哪些函數(shù)是不可計算的。

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

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

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

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

有關術語可計算性等級在數(shù)學中，可計算性是函數(shù)的一個特性。定義域為D和范 圍為R的函數(shù)f有一個確定的對應關系。通過這個 對應關系使R范圍的單個元素f(x) (稱為 值) 和D定義域的每個元素x(稱為變元)聯(lián)系起來。 如果存在這樣一種算法，給定D中的任意的x，就 能給出f(x)的值，那么說函數(shù)f是可計算的。3

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

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

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

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

相關函數(shù)轉換演算一種定義函數(shù)的形式演算系統(tǒng)，是A.丘奇于1935年為精確定義可計算性而提出的。他引進λ記號以明確區(qū)分函數(shù)和函數(shù)值，并把函數(shù)值的計算歸結為按一定規(guī)則進行一系列轉換，最后得到函數(shù)值。按照λ轉換演算能夠得到函數(shù)值的那些函數(shù)稱為λ可定義函數(shù)（見λ轉換演算）。

遞歸函數(shù)自變量值和函數(shù)值都是自然數(shù)的函數(shù)，稱為數(shù)論函數(shù)。原始遞歸函數(shù)是數(shù)論函數(shù)的一部分。首先規(guī)定少量顯然直觀可計算的函數(shù)為原始遞歸函數(shù)，它們是：函數(shù)值恒等于0的零函數(shù)C0，函數(shù)值等于自變量值加1的后繼函數(shù)S，函數(shù)值等于第i個自變量值的n元投影函數(shù)P嬪。然后規(guī)定，原始遞歸函數(shù)的合成仍是原始遞歸函數(shù)，可以由已知原始遞歸函數(shù)簡單遞歸地計算出函數(shù)值的函數(shù)仍是原始遞歸函數(shù)。例如，和函數(shù)f(x，y)=x+y可由原始遞歸函數(shù)P(1)1和S遞歸地計算出函數(shù)值 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

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

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

應用領域由于可計算理論的建立，才出現(xiàn)了現(xiàn)代的計算機系統(tǒng)，此學科無疑是計算機科學的基礎。 計算機科學分為計算機理論和計算機應用。 計算機基礎理論包含以下幾部分：

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

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

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

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

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

( 6) 數(shù)據(jù)理論( 演繹數(shù)據(jù)庫、關系數(shù)據(jù)庫、面向對象數(shù)據(jù)庫等)

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

( 8) 并行計算( 網(wǎng)絡計算、分布式并行計算、大規(guī)模并行計算、演化算法等)1