計算理論(英語:Theory of computation)是數學的一個領域,和電腦有密切關係。其中的理論是現代密碼協定、電腦設計和許多應用領域的基礎。該領域主要關心三個方面的問題:

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

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

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

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

歷史

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

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

參考資料

參見

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.