计算理论 计算理论英語Theory of computation是數學的一個領域和计算机有密切关系其中的理论是现代密码协议计算机设计和许多应用领域的基础该领域主要关心三个方面的问题 采用什么计算模型即形式语言自动机 解决哪些是可计算的哪些是不可计算的即可计算性理论及演算法 要用多少时间要用多少存储即計算複雜性理論 這三方面的問題可以用一個問題來總括電腦的基礎能力及限制到什麼程度 計算理論的計算並非指純粹的算術運算Calculation而是指從已知的輸入透過算法來取得一個問題的答案Computation因此計算理論屬於理論計算機科學和應用數學 為了對計算進行嚴謹的研究電腦科學家會將計算以數學的方式抽象化稱為计算模型有幾種目前在使用的计算模型其中最出名的是圖靈機電腦科學家研究圖靈機的原因是它很容易敘述可以分析用來證明結果而且用此模式呈現了許多強而有力的計算模型參照邱奇图灵论题圖靈機有潛在的數量無限的記憶能力這似乎是不可能達到的不過所有圖靈機解決的可判定性問題都只需要有限量的記憶能力因此理論上任何可以用圖靈機解決的可判定性問題都只需要有限量的記憶能力