理论计算机科学

理论计算机科学
image
关于计算和计算机械的数学理论，也称为计算理论或计算机科学的数学基础。理论计算机科学主要包括：①自动机论与形式语言理论②程序理论③形式语义学④算法分析和计算复杂性理论。[1]

学科的产生

在几千年的数学发展史中，人们研究了各种各样的计算，创立了许许多多的算法，但以计算或算法本身的性质为研究对象的数学理论却是到20世纪30年代才发展起来的。当时为了要解决数学基础的某些理论问题，即是否有的问题不是算法可解的，数理逻辑学家提出了几种不同的（后来证明是彼此等价的）算法定义，从而建立了算法理论（即可计算性理论）。30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻划为递归性。30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机（称为图灵机）中的一种通用机就是存储程序型的。

学科内容

在这些领域中，自动机理论和形式语言理论是50年代发展起来的。前者的历史还可以上溯到30年代，因为图灵机就是一类自动机(无限自动机)。50年代以来一些学者开始考虑与现实的计算机更相似的理想计算机，J.诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。王浩在50年代中期提出了一种图灵机的变种，这是一种比原来的图灵机更接近现实机器的机器。他还提出一种存储带上的内容不能清除的机器，并证明这种机器是与图灵机等价的。60年代前期，又有人提出具有随机存取存储器的计算机（简称RAM）以及多带图灵机等。