计算理论

研究计算过程与功效的数学理论
image
计算理论（英语：Theory of computation）是数学的一个领域，与计算机科学紧密相关，用来研究计算的过程与功效的数学理论。它不仅仅关注纯粹的算术运算，而是涉及从已知输入通过算法得到问题答案的过程。计算理论是现代密码协议、计算机设计以及许多应用领域的基础。

基本介绍

计算理论的研究始于20世纪初的数理逻辑领域，后来发展成为计算机科学的一个独立学科。早期对计算理论做出重要贡献的学者包括阿隆佐·邱奇、库尔特·哥德尔、艾伦·图灵、斯蒂芬·科尔·克莱尼、约翰·冯·诺伊曼及克劳德·香农等。这些科学家的工作为计算理论奠定了坚实的基础，并对后来的计算机科学产生了深远的影响。
1936年，数理逻辑专家提出了计算模型的问题，以解决每个问题是否都有解的疑问。通用图灵机的提出对计算机的设计思想产生了深远影响。计算理论主要包括算法、算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言理论等。作为计算机科学的理论基础，计算理论已经广泛应用于科学的各个领域。程序存储式计算模型就是以图灵机为基础产生的，程序设计中使用了递归函数的思想，自动机作为一种基本工具被广泛应用在程序设计的编译过程中。随着科技的发展，计算理论会更多地应用于其他领域。
为了对计算进行严谨的研究，计算机科学家将计算以数学的方式抽象化，称为计算模型。其中最著名的计算模型是图灵机，它因其易于描述、分析和用于证明结果而被广泛研究，并且展示了许多强大的计算模型。