![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/640px-Maquina.png&w=640&q=50)
计算理论
数学领域 / 维基百科,自由的 encyclopedia
计算理论(英语:Theory of computation)是数学的一个领域,和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题:
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/640px-Maquina.png)
这三方面的问题可以用一个问题来总括:“电脑的基础能力及限制到什么程度?”[1]
计算理论的“计算”并非指纯粹的算术运算(Calculation),而是指从已知的输入透过算法来取得一个问题的答案(Computation),因此,计算理论属于理论计算机科学和应用数学。
为了对计算进行严谨的研究,电脑科学家会将计算以数学的方式抽象化,称为计算模型。有几种目前在使用的计算模型,其中最出名的是图灵机[2]。电脑科学家研究图灵机的原因是它很容易叙述,可以分析,用来证明结果,而且用此模式呈现了许多强而有力的计算模型(参照邱奇-图灵论题)[3]。图灵机有潜在的,数量无限的记忆能力,这似乎是不可能达到的,不过所有图灵机解决的可判定性问题[4]都只需要有限量的记忆能力。因此理论上,任何可以用图灵机解决的(可判定性)问题都只需要有限量的记忆能力。