计算理论
数学领域
计算理论(英语:Theory of computation)是数学的一个领域,和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题:
这三方面的问题可以用一个问题来总括:“电脑的基础能力及限制到什么程度?”[1]
计算理论的“计算”并非指纯粹的算术运算(Calculation),而是指从已知的输入透过算法来获取一个问题的答案(Computation),因此,计算理论属于理论计算机科学和应用数学。
为了对计算进行严谨的研究,计算机科学家会将计算以数学的方式抽象化,称为计算模型。有几种目前在使用的计算模型,其中最出名的是图灵机[2]。计算机科学家研究图灵机的原因是它很容易叙述,可以分析,用来证明结果,而且用此模式呈现了许多强而有力的计算模型(引用邱奇-图灵论题)[3]。图灵机有潜在的,数量无限的记忆能力,这似乎是不可能达到的,不过所有图灵机解决的可判定性问题[4]都只需要有限量的记忆能力。因此理论上,任何可以用图灵机解决的(可判定性)问题都只需要有限量的记忆能力。
历史
编辑计算理论早在所有计算机发明之前便开始了,当时是使用数理逻辑,在20世纪此理论和数学分离,成为一个独立的学科。
计算理论早期的重要贡献者有阿隆佐·邱奇、库尔特·哥德尔、艾伦·图灵、斯蒂芬·科尔·克莱尼、约翰·冯·诺伊曼及克劳德·香农等。
参考资料
编辑- ^ Michael Sipser. Introduction to the Theory of Computation 3rd. Cengage Learning. 2013. ISBN 978-1-133-18779-0.
central areas of the theory of computation: automata, computability, and complexity. (Page 1)
- ^ Andrew Hodges. Alan Turing: The Enigma (THE CENTENARY EDITION). Princeton University Press. 2012. ISBN 978-0-691-15564-7.
- ^ Rabin, Michael O. Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. June 2012 [2017-01-17]. (原始内容存档于2019-06-05).
- ^ Donald Monk. Mathematical Logic. Springer-Verlag. 1976. ISBN 9780387901701.
参见
编辑外部链接
编辑- Theory of Computation(页面存档备份,存于互联网档案馆) at MIT
- Theory of Computation(页面存档备份,存于互联网档案馆) at Harvard
- Computability Logic - A theory of interactive computation. The main web source on this subject.