计算理论（英語：Theory of computation）是數學的一個領域，和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题：
這三方面的問題可以用一個問題來總括：「電腦的基礎能力及限制到什麼程度？」[1]
計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過算法來取得一個問題的答案（Computation），因此，計算理論屬於理論計算機科學和應用數學。
為了對計算進行嚴謹的研究，電腦科學家會將計算以數學的方式抽象化，稱為计算模型。有幾種目前在使用的计算模型，其中最出名的是圖靈機[2]。電腦科學家研究圖靈機的原因是它很容易敘述，可以分析，用來證明結果，而且用此模式呈現了許多強而有力的計算模型（參照邱奇－图灵论题）[3]。圖靈機有潛在的，數量無限的記憶能力，這似乎是不可能達到的，不過所有圖靈機解決的可判定性問題[4]都只需要有限量的記憶能力。因此理論上，任何可以用圖靈機解決的（可判定性）問題都只需要有限量的記憶能力。
歷史
编辑計算理論早在所有計算機發明之前便開始了，當時是使用数理逻辑，在20世紀此理論和數學分離，成為一個獨立的學科。
计算理论早期的重要貢獻者有阿隆佐·邱奇、库尔特·哥德尔、艾伦·图灵、斯蒂芬·科尔·克莱尼、约翰·冯·诺伊曼及克劳德·香农等。
分支
编辑自動機理論
编辑| 文法 | 語言 | 自動機 | 產生式（限制） |
|---|---|---|---|
| 0-型文法 | 遞迴可枚舉 | 圖靈機 | （無限制） |
| 1-型文法 | 上下文有關 | 線性有界自動機 | |
| 2-型文法 | 上下文無關 | 非確定性下推自動機 | |
| 3-型文法 | 正則 | 有限狀態機 | 以及 |
自動機理論研究抽象機器（或更貼切地說，抽象的「數學」機器或系統）以及可利用這些機器求解的計算問題。這些抽象機器稱為自動機（automata）。「automata」一詞源自希臘文（Αυτόματα），意指某物能自行運作（自動地完成某項動作）。
自動機理論也與形式語言理論密切相關，[5]因為自動機往往依其能辨識的形式語言類別來分類。一個自動機可以是對某個形式語言的有限表示，而該形式語言本身可能是一個無限集合。自動機被用作計算機器的理論模型，並常用於可計算性相關的證明。
形式語言理論
编辑
形式語言理論是數學的一個分支，關注如何以在字母表上的一組運算來描述語言。它與自動機理論緊密相連，因為自動機可用來生成與辨識形式語言。形式語言存在若干類別，每一類都允許比前一類更複雜的語言規格描述，例如喬姆斯基階層，[6]而且每一類形式語言都對應到一類能辨識它的自動機。由於自動機被用作計算的模型，對任何必須由計算完成的問題而言，形式語言往往是偏好的規格描述方式。
可計算性理論
编辑可計算性理論主要處理一個問題：在多大程度上，一個問題能在電腦上被求解。「停機問題無法由圖靈機求解」這一命題[7]是可計算性理論中最重要的結果之一，因為它提供了一個具體問題的例子：形式化描述相對容易，但卻不可能用圖靈機加以解決。可計算性理論的許多內容都建立在停機問題的結果之上。
可計算性理論的另一個重要里程碑是萊斯定理（Rice's theorem）。該定理指出：對所有偏函數（partial function）的任何非平凡性質，要判定某台圖靈機是否計算出具有該性質的偏函數，是不可判定的。[8]
可計算性理論與數理邏輯中的遞歸論分支關係密切；遞歸論不再侷限於只研究那些可化約至圖靈模型的計算模型。[9]許多研究遞歸論的數學家與計算理論學者，也會將其稱為可計算性理論。
計算複雜性理論
编辑
計算複雜性理論不僅關心一個問題是否能在電腦上被解出，也關心該問題能否被有效率地解出。主要考量時間複雜度與空間複雜度兩個面向，分別對應於完成一次計算所需的步驟數，以及完成該計算所需的記憶體量。
為了分析某個演算法所需的時間與空間，電腦科學家通常把解決問題所需的時間或空間，表示為輸入規模的函數。舉例來說，在一串很長的數列中尋找特定數字，會隨著數列變長而變得更困難。若我們說列表中共有 個數字，且列表既未排序也未以任何方式建立索引，那麼為了找到目標數字，我們可能必須逐一檢查每個數字。因此可以說，解決這個問題所需的步驟數，會隨問題規模以線性方式成長。
為了簡化這類分析，電腦科學家採用大 O 記號，使得我們能以函數的方式來描述並比較效率：不必把機器實作的細節納入考量，而是著重於問題規模變大時的漸近行為。因此在前述例子中，我們會說該問題需要 個步驟才能解決。
或許整個電腦科學中最重要的未解問題是「是否存在高效率的方法來解決一大類記為 NP 的問題」。相關內容可參見P = NP 問題，該問題是克雷數學研究所於2000年公布的七項千禧年大獎難題之一。該問題的官方敘述由圖靈獎得主史蒂芬·庫克提出。
計算模型
编辑除了圖靈機之外，還有其他等價（參見邱奇-圖靈論題）的計算模型在使用。
- -演算
- 一次計算由一個初始的 表達式（若要將函數與其輸入分開，也可以使用兩個）加上一個有限的 項序列所構成；序列中的每個 項，都可由前一個項經由一次 -歸約推導而得。
- 組合子邏輯
- 是一個與 -演算有許多相似之處、但也存在重要差異的概念（例如，不動點組合子 Y 在組合子邏輯中具有正規形，但在 -演算中則沒有）。組合子邏輯是在相當宏大的企圖下發展而來：理解悖論的本質、使數學基礎在概念上更為精簡、消除變數的概念（從而釐清其在數學中的角色）。
- -遞迴函數
- 一次計算由一個 -遞迴函數（亦即其定義序列）、任意輸入值，以及在該定義序列中出現的遞迴函數之輸入與輸出序列所構成。因此，若在遞迴函數 的定義序列中出現函數 與 ，則序列中可能會出現如「g(5)=7」或「h(3,2)=10」之類的項。此序列中的每一個條目必須是某個基本函數的應用，或是由上方條目透過函數合成、原始遞迴或 -遞迴等方式推出。舉例而言，若 ，那麼要讓「f(5)=3」出現，就必須在其先前出現如「g(5)=6」以及「h(5,6)=3」等項。只有在最後一項給出了該遞迴函數對輸入值的計算結果時，計算才會終止。
- 馬爾可夫算法
- 一種字串重寫系統，以類似形式文法的規則對由符號組成的字串進行操作。
- 寄存器機
- 是一種在理論上頗具意義的電腦理想化模型，並有若干變體。在多數變體中，每個寄存器都能儲存一個任意大的自然數，而其指令少又十分簡單，例如：只包含遞減（結合條件跳轉）與遞增（以及停機）等操作。相較於圖靈機所見的無限（或可動態增長的）外部儲存空間，其欠缺可理解為以哥德爾編號技術取代該角色：由於寄存器能保存任意大的自然數，因此可以用哥德爾數來表示複雜的結構（例如序列、矩陣等）。而表示與詮釋的明確性，則可由這些技術的數論基礎加以建立。
除了上述一般性的計算模型之外，某些更簡單的計算模型也適用於特定、受限的應用。例如，正規表示式可在許多情境中用來指定字串模式，從辦公室生產力工具到程式語言皆然。另一種在數學上與正規表示式等價的形式系統是有限狀態自動機，常用於電路設計以及某些類型的問題求解。上下文無關文法用於指定程式語言的語法；非確定性下推自動機則是與上下文無關文法等價的另一種形式系統。原始遞迴函數是遞迴函數的一個已定義子類別。
不同的計算模型能完成不同的任務。衡量某個計算模型能力的一種方式，是研究該模型能生成的形式語言之類別，如此便可得到語言的喬姆斯基階層。
參考資料
编辑- ^ Michael Sipser. Introduction to the Theory of Computation 3rd. Cengage Learning. 2013. ISBN 978-1-133-18779-0.
central areas of the theory of computation: automata, computability, and complexity. (Page 1)
- ^ Andrew Hodges. Alan Turing: The Enigma (THE CENTENARY EDITION). Princeton University Press. 2012. ISBN 978-0-691-15564-7.
- ^ Rabin, Michael O. Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. June 2012 [2017-01-17]. （原始内容存档于2019-06-05）.
- ^ Donald Monk. Mathematical Logic. Springer-Verlag. 1976. ISBN 9780387901701.
- ^ Hopcroft, John E. and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley. 2006. ISBN 978-0-321-45536-9.
- ^ Chomsky, N. Three models for the description of language. IEEE Transactions on Information Theory. 1956, 2 (3): 113–124. Bibcode:1956IRTIT...2..113C. S2CID 19519474. doi:10.1109/TIT.1956.1056813.
- ^ Alan Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society (IEEE). 1937, 2 (42): 230–265 [6 January 2015]. Bibcode:1937PLMS...42..230T. S2CID 73712. doi:10.1112/plms/s2-42.1.230.[失效連結]
- ^ Henry Gordon Rice. Classes of Recursively Enumerable Sets and Their Decision Problems. Transactions of the American Mathematical Society (American Mathematical Society). 1953, 74 (2): 358–366. JSTOR 1990888. doi:10.2307/1990888
.
- ^ Martin Davis. The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. 2004. ISBN 978-0486432281.
參見
编辑外部連結
编辑- Theory of Computation（页面存档备份，存于互联网档案馆） at MIT
- Theory of Computation（页面存档备份，存于互联网档案馆） at Harvard
- Computability Logic - A theory of interactive computation. The main web source on this subject.
