计算理论

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

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

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

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

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

历史

计算理论早在所有计算机发明之前便开始了,当时是使用数理逻辑,在20世纪此理论和数学分离,成为一个独立的学科。

计算理论早期的重要贡献者有阿隆佐·邱奇库尔特·哥德尔艾伦·图灵斯蒂芬·科尔·克莱尼约翰·冯·诺伊曼克劳德·香农等。

参考资料

  1. ^ 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) 
  2. ^ Andrew Hodges. Alan Turing: The Enigma (THE CENTENARY EDITION). Princeton University Press. 2012. ISBN 978-0-691-15564-7. 
  3. ^ Rabin, Michael O. Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View. June 2012 [2017-01-17]. (原始内容存档于2019-06-05). 
  4. ^ Donald Monk. Mathematical Logic. Springer-Verlag. 1976. ISBN 9780387901701. 

参见

外部链接