计算理论

计算理论（）是數學的一個領域，和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题：
采用什么计算模型（即形式语言、自动机）
解决哪些是可计算的、哪些是不可计算的（即可计算性理论及演算法）
要用多少时间、要用多少存储（即計算複雜性理論）
這三方面的問題可以用一個問題來總括：「電腦的基礎能力及限制到什麼程度？」

計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來取得一個問題的答案（Computation），因此，計算理論屬於理論計算機科學和應用數學。

為了對計算進行嚴謹的研究，電腦科學家會將計算以數學的方式抽象化，稱為计算模型。有幾種目前在使用的计算模型，其中最出名的是圖靈機。電腦科學家研究圖靈機的原因是它很容易敘述，可以分析，用來證明結果，而且用此模式呈現了許多強而有力的計算模型（參照邱奇－图灵论题）。圖靈機有潛在的，數量無限的記憶能力，這似乎是不可能達到的，不過所有圖靈機解決的可判定性問題都只需要有限量的記憶能力。因此理論上，任何可以用圖靈機解決的（可判定性）問題都只需要有限量的記憶能力。

 歷史 
計算理論早在所有計算機發明之前便開始了，當時是使用数理逻辑，在20世紀此理論和數學分離，成為一個獨立的學科。

计算理论早期的重要貢獻者有阿隆佐·邱奇、库尔特·哥德尔、艾伦·图灵、斯蒂芬·科尔·克莱尼、约翰·冯·诺伊曼及克劳德·香农等。

 分支 

 自動機理論 

 文法 語言 自動機 產生式（限制） 0-型文法 遞迴可枚舉 圖靈機 （無限制） 1-型文法 上下文有關 線性有界自動機  2-型文法 上下文無關 非確定性下推自動機  3-型文法 正則 有限狀態機 以及

自動機理論研究抽象機器（或更貼切地說，抽象的「數學」機器或系統）以及可利用這些機器求解的計算問題。這些抽象機器稱為自動機（automata）。「automata」一詞源自希臘文（Αυτόματα），意指某物能自行運作（自動地完成某項動作）。

自動機理論也與形式語言理論密切相關，因為自動機往往依其能辨識的形式語言類別來分類。一個自動機可以是對某個形式語言的有限表示，而該形式語言本身可能是一個無限集合。自動機被用作計算機器的理論模型，並常用於可計算性相關的證明。

 形式語言理論 

形式語言理論是數學的一個分支，關注如何以在字母表上的一組運算來描述語言。它與自動機理論緊密相連，因為自動機可用來生成與辨識形式語言。形式語言存在若干類別，每一類都允許比前一類更複雜的語言規格描述，例如喬姆斯基階層，而且每一類形式語言都對應到一類能辨識它的自動機。由於自動機被用作計算的模型，對任何必須由計算完成的問題而言，形式語言往往是偏好的規格描述方式。

 可計算性理論 

可計算性理論主要處理一個問題：在多大程度上，一個問題能在電腦上被求解。「停機問題無法由圖靈機求解」這一命題是可計算性理論中最重要的結果之一，因為它提供了一個具體問題的例子：形式化描述相對容易，但卻不可能用圖靈機加以解決。可計算性理論的許多內容都建立在停機問題的結果之上。

可計算性理論的另一個重要里程碑是萊斯定理（Rice's theorem）。該定理指出：對所有偏函數（partial function）的任何非平凡性質，要判定某台圖靈機是否計算出具有該性質的偏函數，是不可判定的。

可計算性理論與數理邏輯中的遞歸論分支關係密切；遞歸論不再侷限於只研究那些可化約至圖靈模型的計算模型。許多研究遞歸論的數學家與計算理論學者，也會將其稱為可計算性理論。

 計算複雜性理論 

250px|thumb|right|複雜度類之間關係的示意圖
計算複雜性理論不僅關心一個問題是否能在電腦上被解出，也關心該問題能否被有效率地解出。主要考量時間複雜度與空間複雜度兩個面向，分別對應於完成一次計算所需的步驟數，以及完成該計算所需的記憶體量。

為了分析某個演算法所需的時間與空間，電腦科學家通常把解決問題所需的時間或空間，表示為輸入規模的函數。舉例來說，在一串很長的數列中尋找特定數字，會隨著數列變長而變得更困難。若我們說列表中共有  個數字，且列表既未排序也未以任何方式建立索引，那麼為了找到目標數字，我們可能必須逐一檢查每個數字。因此可以說，解決這個問題所需的步驟數，會隨問題規模以線性方式成長。

為了簡化這類分析，電腦科學家採用大 O 記號，使得我們能以函數的方式來描述並比較效率：不必把機器實作的細節納入考量，而是著重於問題規模變大時的漸近行為。因此在前述例子中，我們會說該問題需要  個步驟才能解決。

或許整個電腦科學中最重要的未解問題是「是否存在高效率的方法來解決一大類記為 NP 的問題」。相關內容可參見P = NP 問題，該問題是克雷數學研究所於2000年公布的七項千禧年大獎難題之一。該問題的官方敘述由圖靈獎得主史蒂芬·庫克提出。

 計算模型 

除了圖靈機之外，還有其他等價（參見邱奇-圖靈論題）的計算模型在使用。

-演算
一次計算由一個初始的  表達式（若要將函數與其輸入分開，也可以使用兩個）加上一個有限的  項序列所構成；序列中的每個  項，都可由前一個項經由一次-歸約推導而得。
組合子邏輯
是一個與 -演算有許多相似之處、但也存在重要差異的概念（例如，不動點組合子 Y 在組合子邏輯中具有正規形，但在 -演算中則沒有）。組合子邏輯是在相當宏大的企圖下發展而來：理解悖論的本質、使數學基礎在概念上更為精簡、消除變數的概念（從而釐清其在數學中的角色）。
-遞迴函數
一次計算由一個 -遞迴函數（亦即其定義序列）、任意輸入值，以及在該定義序列中出現的遞迴函數之輸入與輸出序列所構成。因此，若在遞迴函數  的定義序列中出現函數  與 ，則序列中可能會出現如「g(5)=7」或「h(3,2)=10」之類的項。此序列中的每一個條目必須是某個基本函數的應用，或是由上方條目透過、原始遞迴或-遞迴等方式推出。舉例而言，若 ，那麼要讓「f(5)=3」出現，就必須在其先前出現如「g(5)=6」以及「h(5,6)=3」等項。只有在最後一項給出了該遞迴函數對輸入值的計算結果時，計算才會終止。
馬爾可夫算法
一種，以類似形式文法的規則對由符號組成的字串進行操作。
寄存器機
是一種在理論上頗具意義的電腦理想化模型，並有若干變體。在多數變體中，每個寄存器都能儲存一個任意大的自然數，而其指令少又十分簡單，例如：只包含遞減（結合條件跳轉）與遞增（以及停機）等操作。相較於圖靈機所見的無限（或可動態增長的）外部儲存空間，其欠缺可理解為以哥德爾編號技術取代該角色：由於寄存器能保存任意大的自然數，因此可以用哥德爾數來表示複雜的結構（例如序列、矩陣等）。而表示與詮釋的明確性，則可由這些技術的數論基礎加以建立。

除了上述一般性的計算模型之外，某些更簡單的計算模型也適用於特定、受限的應用。例如，正規表示式可在許多情境中用來指定字串模式，從辦公室生產力工具到程式語言皆然。另一種在數學上與正規表示式等價的形式系統是有限狀態自動機，常用於電路設計以及某些類型的問題求解。上下文無關文法用於指定程式語言的語法；非確定性下推自動機則是與上下文無關文法等價的另一種形式系統。原始遞迴函數是遞迴函數的一個已定義子類別。

不同的計算模型能完成不同的任務。衡量某個計算模型能力的一種方式，是研究該模型能生成的形式語言之類別，如此便可得到語言的喬姆斯基階層。

參考資料

參見
 計算複雜性理論
 可计算性理论
 圖靈機
 最佳化問題

 外部連結 
 Theory of Computation at MIT
 Theory of Computation at Harvard
 Computability Logic - A theory of interactive computation. The main web source on this subject.

Category:計算理論