计算理论(英語:Theory of computation)是數學的一個領域,和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题:
這三方面的問題可以用一個問題來總括:「電腦的基礎能力及限制到什麼程度?」
計算理論的「計算」並非指純粹的算術運算(Calculation),而是指從已知的輸入透過算法來取得一個問題的答案(Computation),因此,計算理論屬於理論計算機科學和應用數學。
為了對計算進行嚴謹的研究,電腦科學家會將計算以數學的方式抽象化,稱為计算模型。有幾種目前在使用的计算模型,其中最出名的是圖靈機。電腦科學家研究圖靈機的原因是它很容易敘述,可以分析,用來證明結果,而且用此模式呈現了許多強而有力的計算模型(參照邱奇-图灵论题)。圖靈機有潛在的,數量無限的記憶能力,這似乎是不可能達到的,不過所有圖靈機解決的可判定性問題都只需要有限量的記憶能力。因此理論上,任何可以用圖靈機解決的(可判定性)問題都只需要有限量的記憶能力。
計算理論早在所有計算機發明之前便開始了,當時是使用数理逻辑,在20世紀此理論和數學分離,成為一個獨立的學科。
计算理论早期的重要貢獻者有阿隆佐·邱奇、库尔特·哥德尔、艾伦·图灵、斯蒂芬·科尔·克莱尼、约翰·冯·诺伊曼及克劳德·香农等。
This article uses material from the Wikipedia 中文 article 计算理论, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). 除非另有声明,本网站内容采用CC BY-SA 4.0授权。 Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki 中文 (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.