計算理論
計算理論（英語：Theory of computation）是數學的一個領域，和電腦有密切關係。其中的理論是現代密碼協定、電腦設計和許多應用領域的基礎。該領域主要關心三個方面的問題：
這三方面的問題可以用一個問題來總括：「電腦的基礎能力及限制到什麼程度？」[1]
計算理論的「計算」並非指純粹的算術運算（Calculation），而是指從已知的輸入透過演算法來取得一個問題的答案（Computation），因此，計算理論屬於理論電腦科學和應用數學。
為了對計算進行嚴謹的研究，電腦科學家會將計算以數學的方式抽象化，稱為計算模型。有幾種目前在使用的計算模型，其中最出名的是圖靈機[2]。電腦科學家研究圖靈機的原因是它很容易敘述，可以分析，用來證明結果，而且用此模式呈現了許多強而有力的計算模型（參照邱奇－圖靈論題）[3]。圖靈機有潛在的，數量無限的記憶能力，這似乎是不可能達到的，不過所有圖靈機解決的可判定性問題[4]都只需要有限量的記憶能力。因此理論上，任何可以用圖靈機解決的（可判定性）問題都只需要有限量的記憶能力。
歷史
[編輯]計算理論早在所有計算機發明之前便開始了，當時是使用數理邏輯，在20世紀此理論和數學分離，成為一個獨立的學科。
計算理論早期的重要貢獻者有阿隆佐·邱奇、庫爾特·哥德爾、艾倫·圖靈、斯蒂芬·科爾·克萊尼、約翰·馮·諾伊曼及克勞德·香農等。
參考資料
[編輯]- ^ 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.
參見
[編輯]外部連結
[編輯]- Theory of Computation（頁面存檔備份，存於互聯網檔案館） at MIT
- Theory of Computation（頁面存檔備份，存於互聯網檔案館） at Harvard
- Computability Logic - A theory of interactive computation. The main web source on this subject.
