计算理论

计算理论（英語：Theory of computation）是數學的一個領域，和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题：

• 采用什么计算模型（即形式语言、自动机）
• 解决哪些是可计算的、哪些是不可计算的（即可计算性理论及演算法）
• 要用多少时间、要用多少存储（即計算複雜性理論）

藝術化的圖靈機。圖靈機常用在計算的理論模型上

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

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

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

歷史

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

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

參考資料

1. 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) 
2. Andrew Hodges. Alan Turing: The Enigma (THE CENTENARY EDITION). Princeton University Press. 2012. ISBN 978-0-691-15564-7. 
3. Rabin, Michael O. . June 2012 [2017-01-17]. （原始内容存档于2019-06-05）. 
4. Donald Monk. Mathematical Logic. Springer-Verlag. 1976. ISBN 9780387901701. 

參見

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

外部連結

• Theory of Computation（页面存档备份，存于互联网档案馆） at MIT
• Theory of Computation（页面存档备份，存于互联网档案馆） at Harvard
• - A theory of interactive computation. The main web source on this subject.