计算理论

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

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

艺术化的图灵机。图灵机常用在计算的理论模型上

这三方面的问题可以用一个问题来总括：“电脑的基础能力及限制到什么程度？”^[1]

计算理论的“计算”并非指纯粹的算术运算（Calculation），而是指从已知的输入透过算法来获取一个问题的答案（Computation），因此，计算理论属于理论计算机科学和应用数学。

为了对计算进行严谨的研究，计算机科学家会将计算以数学的方式抽象化，称为计算模型。有几种目前在使用的计算模型，其中最出名的是图灵机^[2]。计算机科学家研究图灵机的原因是它很容易叙述，可以分析，用来证明结果，而且用此模式呈现了许多强而有力的计算模型（引用邱奇－图灵论题）^[3]。图灵机有潜在的，数量无限的记忆能力，这似乎是不可能达到的，不过所有图灵机解决的可判定性问题^[4]都只需要有限量的记忆能力。因此理论上，任何可以用图灵机解决的（可判定性）问题都只需要有限量的记忆能力。