計算理論

計算理論（Theory of computation）是數學的一個領域，和電腦有密切關係。其中的理論是現代密碼協議、電腦設計和許多應用領域的基礎。該領域主要關心三個方面的問題：

- 採用什麼計算模型（即形式語言、自動機）
- 解決哪些是可計算的、哪些是不可計算的（即可計算性理論及演演算法）
- 要用多少時間、要用多少存儲（即計算複雜性理論）

這三方面的問題可以用一個問題來總括：「電腦的基礎能力及限制到什麼程度？」

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

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

## 歷史

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

計算理論早期的重要貢獻者有阿隆佐·邱奇、庫爾特·哥德爾、艾倫·圖靈、史蒂芬·科爾·克萊尼、約翰·馮·諾伊曼及克勞德·香農等。

## 分支

### 自動機理論

文法｜語言｜自動機｜產生式（限制）

0-型文法｜遞迴可枚舉｜圖靈機｜$\alpha \rightarrow \beta$（無限制）

1-型文法｜上下文有關｜線性有界自動機｜$\alpha A \beta \rightarrow \alpha \gamma \beta$

2-型文法｜上下文無關｜非確定性下推自動機｜$A \rightarrow \gamma$

3-型文法｜正則｜有限狀態機｜$A \rightarrow a$以及$A \rightarrow aB$

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

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

#### 形式語言理論

<image>

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

### 可計算性理論

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

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

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

### 計算複雜性理論

<image>

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

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

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

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

## 計算模型

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

$\lambda$-演算：一次計算由一個初始的 $\lambda$ 表達式（若要將函數與其輸入分開，也可以使用兩個）加上一個有限的 $\lambda$ 項序列所構成；序列中的每個 $\lambda$ 項，都可由前一個項經由一次$\beta$-歸約推導而得。

組合子邏輯：是一個與 $\lambda$-演算有許多相似之處、但也存在重要差異的概念（例如，不動點組合子 Y 在組合子邏輯中具有正規形，但在 $\lambda$-演算中則沒有）。組合子邏輯是在相當宏大的企圖下發展而來：理解悖論的本質、使數學基礎在概念上更為精簡、消除變數的概念（從而釐清其在數學中的角色）。

$\mu$-遞迴函數：一次計算由一個 $\mu$-遞迴函數（亦即其定義序列）、任意輸入值，以及在該定義序列中出現的遞迴函數之輸入與輸出序列所構成。因此，若在遞迴函數 $f(x)$ 的定義序列中出現函數 $g(x)$ 與 $h(x,y)$，則序列中可能會出現如「g(5)=7」或「h(3,2)=10」之類的項。此序列中的每一個條目必須是某個基本函數的應用，或是由上方條目透過函數合成、原始遞迴或$\mu$-遞迴等方式推出。舉例而言，若 $f(x)=h(x,g(x))$，那麼要讓「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.