谁能给我一些计算机理论知识？ 谁能给我一篇论文"论计算机网络基础的"?
2024-05-31m.verywind.com
~
理论计算机科学
theoretical computer science
关于计算和计算机械的数学理论，也称为计算理论或计算机科学的数学基础。
学科的产生 在几千年的数学发展史中，人们研究了各种各样的计算，创立了许许多多的算法，但以计算或算法本身的性质为研究对象的数学理论却是到20世纪30年代才发展起来的。当时为了要解决数学基础的某些理论问题，即是否有的问题不是算法可解的，数理逻辑学家提出了几种不同的（后来证明是彼此等价的）算法定义，从而建立了算法理论（即可计算性理论）。30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻划为递归性。30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机（称为图灵机）中的一种通用机就是存储程序型的。
学科内容 理论计算机科学主要包括：①自动机论与形式语言理论;②程序理论(包括程序正确性证明、程序验证等);③形式语义学；④算法分析和计算复杂性理论。在这些领域中，自动机理论和形式语言理论是50年代发展起来的。前者的历史还可以上溯到30年代，因为图灵机就是一类自动机(无限自动机)。50年代以来一些学者开始考虑与现实的计算机更相似的理想计算机，J.诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。王浩在50年代中期提出了一种图灵机的变种，这是一种比原来的图灵机更接近现实机器的机器。他还提出一种存储带上的内容不能清除的机器，并证明这种机器是与图灵机等价的。60年代前期，又有人提出具有随机存取存储器的计算机（简称RAM）以及多带图灵机等。
形式语言理论 导源于数理语言学中的乔姆斯基理论。在这种理论中,形式语言分为四种:①0型语言；②1型语言;③2型语言;④3型语言。相应地存在着0型、1型、2 型、3型四种形式文法。1型语言又名上下文有关语言，2型语言又名上下文无关语言，3型语言又名正则语言。其中2型语言最受人注意。60年代中期,还发现了这四类语言与四类自动机之间的对应关系（见表）
在上表中，左边所列的语言恰好是右边与之对应的自动机所能识别的语言（见形式语言理论）。
程序设计理论 包括程序正确性证明和程序验证，它的一些基本概念和方法是40年代后期诺伊曼和图灵等人提出的。诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。后来图灵又证明了一个子程序的正确性。他的方法是：设有一给定的程序，且有变量X1，X2，…，Xn以及输入谓词P(X1，…，Xn)与输出谓词Q(X1，…，Xn)。如果能证明下列事实：若在程序执行前谓词P（X1，…，Xn）成立，则在程序执行后,谓词Q(X1，…，Xn)成立，程序的正确性得证。
图灵的这一结果长期未引起注意，一直到P.瑙尔在1963年和E.F.费洛伊德在1966年重新提出这一方法后，才引起计算机科学界的重视。此后，有不少理论工作者在从事这方面的研究。但正如E.W.戴克斯特拉在70年代中期曾指出的，实际有效的方法是边设计边验证，在设计完毕时证明或验证的过程也同时结束。J.T.施瓦兹和M.戴维斯70年代后期提出了一种他们称之为“正确程序技术”的软件技术。这种方法是先选定成千种基本程序模块，并借助已知的各种验证方法（包括程序正确性证明）来保证这些基本程序的正确性。然后再提出一组能保持正确性的程序组合规则。这样，就可以通过不断的组合，生成各种各样的程序。
有人指出，程序正确性证明技术所发展出来的“循环不变式”，即一个程序中的某一循环的入口或出口点上所附的谓词，有些文献中称作“归纳断言”，可以用来供程序研究用。也就是说，不像过去那样，对一个给定的程序找出其若干个循环不变式，然后借助这些不变式来证明这个程序的正确性；而是在编制这个程序之前，根据对这一程序的要求，找出若干个循环不变式，然后根据这些不变式来生成这个程序。
自动程序设计的概念也是从40年代提出的。图灵在1947年的一篇论文中，提出借助定理证明的方法来设计程序。他的想法大致如下:设要求设计一个程序,使成为计算一个给定的递归函数F(X)的程序，并令F(n)=m（这里n是任一自然数，m是自然数），需要找到一个证明F(n)=m的构造性证明。在有了这样一个构造性证明以后，就可以从这个证明中提取出F(X)的求值算法，然后生成所需要的程序。图灵的这一思想长时间不为人所知。1969年又有人独立地提出了这一想法。
程序语言的形式语法的研究，从50年代中期起有了较大的发展。而形式语义的研究自60年代以来虽有不少研究工作者从事这方面的工作，提出几种不同的语义理论，主要是操作语义学、指称语义学或称数学语义学、公理语义学和代数语义学，但仍没有一种公认在软件技术中够用的形式语义学，因而需要提出一种更适于用到实际计算中的新的语义学。
在程序正确性证明和形式语义学中应用的程序逻辑，是60年代末发展起来的。这是谓词逻辑的一种扩充。原来的谓词逻辑中是没有时间概念的，所考虑的推理关系是在同一时间里的关系。程序是一种过程，一个程序的输入谓词与输出谓词之间的逻辑关系就不是同一时间里的关系。因此，在有关程序性质的推理中，原来的谓词逻辑不够用，需要有一种新的逻辑。
60年代末，E.恩格勒等人创立了算法逻辑。C.A.R.霍尔也创立了一种程序逻辑。这种逻辑是在原来的逻辑上增加一个程序算子而得到的。例如，可以将程序作为一种新的算子置于一个谓词公式的前面，如表达式 ｛S｝P(X1，…，Xn)表示在程序S执行完毕时,谓词P(X1，…，Xn)成立（这里的）X1，…，Xn是程序S 中的变量）。
算法分析和计算复杂性理论 关于算法的复杂性的研究。关于这一领域的名称曾有争论。一般认为，各类具体算法的复杂性的研究称作算法分析，而一般算法复杂性的研究称作计算复杂性理论。计算复杂性理论原是可计算理论的一支，是以各种可计算函数(即递归函数)的计算复杂性（在早期称作“计算难度”）为其研究对象的。可计算性分为理论可计算性和实际可计算性两种。作为可计算性理论一支的计算复杂性理论，是以前者的复杂程度为其研究对象的；而作为计算机科学一个领域的复杂性理论，则是以后者的复杂程度为其研究对象的。
这一分支的基本问题是要弄清楚实际可计算函数类的结构和一些性质。实际可计算性是一个直观的概念。如何对这一概念进行精确的描述，是一个并不容易的问题。60年代中期以来，有关的研究工作者一般是以计算时间多项式有界的函数作为实际可计算的函数。这实际上是一个论题，而不是一个可以在数学中加以证明或否证的命题。有人指出，在有关的多项式次数较高时（如n100的情形），很难说是实际可计算的。
另一个带根本性的问题是：确定性机器与非确定性机器的解题能力的比较问题。人们早已知道，确定性图灵机与非确定性图灵机的解题能力是相等的。因为非确定性机器虽比确定性机器效率高，而如果计算时间没有限制，则确定性机器总可以用穷举的方法来模拟非确定性机器。因此，二者的解题能力是一样的。但在计算时间多项式有界时，二者的解题能力是否相等，这就是有名的P=? NP问题。
关于计算和算法（包括程序）的研究，对串行计算的性质研究较多，而对并行计算性质的研究则还很不够（特别是对异步的并行计算更是如此）。因此，关于并行计算的研究很可能将成为计算机理论的研究重点。
[编辑]补充
关于计算和计算机械的数学理论，也称为计算理论或计算机科学的数学基础。
学科的产生 在几千年的数学发展史中，人们研究了各种各样的计算，创立了许许多多的算法，但以计算或算法本身的性质为研究对象的数学理论却是到20世纪30年代才发展起来的。当时为了要解决数学基础的某些理论问题，即是否有的问题不是算法可解的，数理逻辑学家提出了几种不同的（后来证明是彼此等价的）算法定义，从而建立了算法理论（即可计算性理论）。30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻划为递归性。30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机（称为图灵机）中的一种通用机就是存储程序型的。
学科内容 理论计算机科学主要包括：①自动机论与形式语言理论;②程序理论(包括程序正确性证明、程序验证等);③形式语义学；④算法分析和计算复杂性理论。在这些领域中，自动机理论和形式语言理论是50年代发展起来的。前者的历史还可以上溯到30年代，因为图灵机就是一类自动机(无限自动机)。50年代以来一些学者开始考虑与现实的计算机更相似的理想计算机，J.诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。王浩在50年代中期提出了一种图灵机的变种，这是一种比原来的图灵机更接近现实机器的机器。他还提出一种存储带上的内容不能清除的机器，并证明这种机器是与图灵机等价的。60年代前期，又有人提出具有随机存取存储器的计算机（简称RAM）以及多带图灵机等。
形式语言理论 导源于数理语言学中的乔姆斯基理论。在这种理论中，形式语言分为四种:①0型语言；②1型语言;③2型语言;④3型语言。相应地存在着0型、1型、2 型、3型四种形式文法。1型语言又名上下文有关语言，2型语言又名上下文无关语言，3型语言又名正则语言。其中2型语言最受人注意。60年代中期，还发现了这四类语言与四类自动机之间的对应关系（见表）
在上表中，左边所列的语言恰好是右边与之对应的自动机所能识别的语言（见形式语言理论）。
程序设计理论 包括程序正确性证明和程序验证，它的一些基本概念和方法是40年代后期诺伊曼和图灵等人提出的。诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。后来图灵又证明了一个子程序的正确性。他的方法是：设有一给定的程序，且有变量X1，X2，…，Xn以及输入谓词P(X1，…，Xn)与输出谓词Q(X1，…，Xn)。如果能证明下列事实：若在程序执行前谓词P（X1，…，Xn）成立，则在程序执行后，谓词Q(X1，…，Xn)成立，程序的正确性得证。
图灵的这一结果长期未引起注意，一直到P.瑙尔在1963年和E.F.费洛伊德在1966年重新提出这一方法后，才引起计算机科学界的重视。此后，有不少理论工作者在从事这方面的研究。但正如E.W.戴克斯特拉在70年代中期曾指出的，实际有效的方法是边设计边验证，在设计完毕时证明或验证的过程也同时结束。J.T.施瓦兹和M.戴维斯70年代后期提出了一种他们称之为“正确程序技术”的软件技术。这种方法是先选定成千种基本程序模块，并借助已知的各种验证方法（包括程序正确性证明）来保证这些基本程序的正确性。然后再提出一组能保持正确性的程序组合规则。这样，就可以通过不断的组合，生成各种各样的程序。
有人指出，程序正确性证明技术所发展出来的“循环不变式”，即一个程序中的某一循环的入口或出口点上所附的谓词，有些文献中称作“归纳断言”，可以用来供程序研究用。也就是说，不像过去那样，对一个给定的程序找出其若干个循环不变式，然后借助这些不变式来证明这个程序的正确性；而是在编制这个程序之前，根据对这一程序的要求，找出若干个循环不变式，然后根据这些不变式来生成这个程序。
自动程序设计的概念也是从40年代提出的。图灵在1947年的一篇论文中，提出借助定理证明的方法来设计程序。他的想法大致如下:设要求设计一个程序，使成为计算一个给定的递归函数F(X)的程序，并令F(n)=m（这里n是任一自然数，m是自然数），需要找到一个证明F(n)=m的构造性证明。在有了这样一个构造性证明以后，就可以从这个证明中提取出F(X)的求值算法，然后生成所需要的程序。图灵的这一思想长时间不为人所知。1969年又有人独立地提出了这一想法。
程序语言的形式语法的研究，从50年代中期起有了较大的发展。而形式语义的研究自60年代以来虽有不少研究工作者从事这方面的工作，提出几种不同的语义理论，主要是操作语义学、指称语义学或称数学语义学、公理语义学和代数语义学，但仍没有一种公认在软件技术中够用的形式语义学，因而需要提出一种更适于用到实际计算中的新的语义学。
在程序正确性证明和形式语义学中应用的程序逻辑，是60年代末发展起来的。这是谓词逻辑的一种扩充。原来的谓词逻辑中是没有时间概念的，所考虑的推理关系是在同一时间里的关系。程序是一种过程，一个程序的输入谓词与输出谓词之间的逻辑关系就不是同一时间里的关系。因此，在有关程序性质的推理中，原来的谓词逻辑不够用，需要有一种新的逻辑。
60年代末，E.恩格勒等人创立了算法逻辑。C.A.R.霍尔也创立了一种程序逻辑。这种逻辑是在原来的逻辑上增加一个程序算子而得到的。例如，可以将程序作为一种新的算子置于一个谓词公式的前面，如表达式
｛S｝P(X1，…，Xn)表示在程序S执行完毕时，谓词P(X1，…，Xn)成立（这里的）X1，…，Xn是程序S 中的变量）。
算法分析和计算复杂性理论 关于算法的复杂性的研究。关于这一领域的名称曾有争论。一般认为，各类具体算法的复杂性的研究称作算法分析，而一般算法复杂性的研究称作计算复杂性理论。计算复杂性理论原是可计算理论的一支，是以各种可计算函数(即递归函数)的计算复杂性（在早期称作“计算难度”）为其研究对象的。可计算性分为理论可计算性和实际可计算性两种。作为可计算性理论一支的计算复杂性理论，是以前者的复杂程度为其研究对象的；而作为计算机科学一个领域的复杂性理论，则是以后者的复杂程度为其研究对象的。
这一分支的基本问题是要弄清楚实际可计算函数类的结构和一些性质。实际可计算性是一个直观的概念。如何对这一概念进行精确的描述，是一个并不容易的问题。60年代中期以来，有关的研究工作者一般是以计算时间多项式有界的函数作为实际可计算的函数。这实际上是一个论题，而不是一个可以在数学中加以证明或否证的命题。有人指出，在有关的多项式次数较高时（如n的情形），很难说是实际可计算的。
另一个带根本性的问题是：确定性机器与非确定性机器的解题能力的比较问题。人们早已知道，确定性图灵机与非确定性图灵机的解题能力是相等的。因为非确定性机器虽比确定性机器效率高，而如果计算时间没有限制，则确定性机器总可以用穷举的方法来模拟非确定性机器。因此，二者的解题能力是一样的。但在计算时间多项式有界时，二者的解题能力是否相等，这就是有名的P=? NP问题。
关于计算和算法（包括程序）的研究，对串行计算的性质研究较多，而对并行计算性质的研究则还很不够（特别是对异步的并行计算更是如此）。因此，关于并行计算的研究很可能将成为计算机理论的研究重点。
大学计算机基础知识点归纳是什么? 答：二进制的0和1可以与逻辑代数中的“真”和“假”对应，便于应用逻辑代数理论研究计算机理论；14、进位计数：按进位的原则进行计数，简称数制。15、十进制和二进制、八进制、十六进制间的相互转换。16、数据：指所有能输入到计算机中并被计算机识别、存储和加工处理的符号的总称。数据分为数值型数据和非数值...
计算机安全理论基础知识 答：计算机安全理论基础知识 每个人必须认识到计算机病毒的危害性，了解计算机病毒的基本特征，增强预防计算机病毒的意识，掌握清除计算机病毒的操作技能。我整理了相关的内容，欢迎欣赏与借鉴。一、计算机系统面临的威胁和攻击 计算机系统面临的威胁和攻击,大体上可以分成两大类:一类是对实体的威胁和攻击,另一类是...
计算机理论知识 答：仅供参考 有些可能不对 31、一组计算机指令或者程序代码 32、内存地址 33、- 34、旧密码值 35、剪贴板 36、另存为 37、关系型 38、browse 39、LAN 40、电子邮箱 41、计算机工作时执行一条指令的全过程分为三个阶段：取出指令，分析指令，执行指令。取出指令阶段的任务是从内存取出指令放到指令寄存器...
计算机系统的基本知识,操作系统的使用。 答：1. 掌握计算机系统和计算机软件的基本概念、计算机网路的基本知识和应用知识、信息安全的基本概念。 2. 掌握数据结构与算法的基本知识并能熟练应用。 3. 掌握并能熟练运用操作系统的基本知识。 4. 掌握数据库的基本概念,深入理解关系数据库模型、关系数据理论和关系数据库系统,掌握关系数据语言。 5. 掌握数据库设计...
计算机应用基础知识点有哪些? 答：计算机应用基础知识点如下：1、计算机应包括运算器、存储器、控制器、输入设备和输出设备五大基本部件。2、1946年2月15日世界上第一台电子计算机ENIAC（埃尼阿克）在美国宾州大学研制成功。3、计算机内部采用二进制来表达指令和数据。4、1945年，冯·诺依曼提出的，是现代计算机的理论基础。现代计算机已经发展...
电脑基础知识。 答：在使用电脑时，我们常常需要对操作系统进行一些必要的设置，以便让电脑更好地为我们服务。而这些设置往往是在操作系统里的“桌面”、“开始菜单”、“控制面板”等处进行的。学到的知识点：★认识开始菜单★认识控制面板★桌面常用设置 4.1 认识和设置开始菜单 利用开始菜单按钮可以进行所有的Windows操作,...
电脑理论知识 答：计算机屏幕上的文本信息可以反复阅读,从容理解,不时间、空间的限制,但是,在阅读屏幕上显示的文本信息,特别是信息量较大时容易引起视觉疲劳,使学习者产生厌倦情绪。另外,文本信息具有一定的抽象性,阅读者在阅读时,必须会?quot;译码"工作,即抽象的文字还原为相应事物,这就要多媒体教学软件使用者有一定的抽象思维能力和...
帮我做几道关于计算机的理论知识 答：15，正确； 可参看系统调用，题中截短应为截断吧？16，正确；17，错误； 中断是指计算机在执行程序的过程中，当出现异常情况或特殊请求时，计算机停止现行程序的运行，转向对这些异常情况或特殊请求的处理，处理结束后再返回现行程序的间断处，继续执行原程序。计算机暂停现行程序运行而非结束。18，错误...
明天考计算机一级了,谁能发给我一些知识点,,,急急急 谢谢啦 答：考点 1.1 集成电路的基本知识 微电子技术是实现电子电路和电子系统超小型化及微型化的技术，以集成电路为核心。集成电路：20世纪50年代出现。以半导体单晶片作为材料，经平面工艺加工制造，将大量的晶体管、电阻、电容等元器件及互相连线构成的电子线路集成在基片上，构成一个微型化的电路或者系统。集成电路...
电子计算机的知识 答：1938: 柏林的Konrad Zuse 和他的助手们完成了一个机械可编程二进制形式的计算机,其理论基础是Boolean代数。后来命名为Z1。它的功能比较强大,用类似电影胶片的东西作为存储介质。可以运算七位指数和16位小数。可以用一个键盘输入数字,用灯泡显示结果。 1939 1月1日: 加利福尼亚的David Hewlet和William Packard 在他...
theoretical computer science
关于计算和计算机械的数学理论，也称为计算理论或计算机科学的数学基础。
学科的产生 在几千年的数学发展史中，人们研究了各种各样的计算，创立了许许多多的算法，但以计算或算法本身的性质为研究对象的数学理论却是到20世纪30年代才发展起来的。当时为了要解决数学基础的某些理论问题，即是否有的问题不是算法可解的，数理逻辑学家提出了几种不同的（后来证明是彼此等价的）算法定义，从而建立了算法理论（即可计算性理论）。30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻划为递归性。30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机（称为图灵机）中的一种通用机就是存储程序型的。
学科内容 理论计算机科学主要包括：①自动机论与形式语言理论;②程序理论(包括程序正确性证明、程序验证等);③形式语义学；④算法分析和计算复杂性理论。在这些领域中，自动机理论和形式语言理论是50年代发展起来的。前者的历史还可以上溯到30年代，因为图灵机就是一类自动机(无限自动机)。50年代以来一些学者开始考虑与现实的计算机更相似的理想计算机，J.诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。王浩在50年代中期提出了一种图灵机的变种，这是一种比原来的图灵机更接近现实机器的机器。他还提出一种存储带上的内容不能清除的机器，并证明这种机器是与图灵机等价的。60年代前期，又有人提出具有随机存取存储器的计算机（简称RAM）以及多带图灵机等。
形式语言理论 导源于数理语言学中的乔姆斯基理论。在这种理论中,形式语言分为四种:①0型语言；②1型语言;③2型语言;④3型语言。相应地存在着0型、1型、2 型、3型四种形式文法。1型语言又名上下文有关语言，2型语言又名上下文无关语言，3型语言又名正则语言。其中2型语言最受人注意。60年代中期,还发现了这四类语言与四类自动机之间的对应关系（见表）
在上表中，左边所列的语言恰好是右边与之对应的自动机所能识别的语言（见形式语言理论）。
程序设计理论 包括程序正确性证明和程序验证，它的一些基本概念和方法是40年代后期诺伊曼和图灵等人提出的。诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。后来图灵又证明了一个子程序的正确性。他的方法是：设有一给定的程序，且有变量X1，X2，…，Xn以及输入谓词P(X1，…，Xn)与输出谓词Q(X1，…，Xn)。如果能证明下列事实：若在程序执行前谓词P（X1，…，Xn）成立，则在程序执行后,谓词Q(X1，…，Xn)成立，程序的正确性得证。
图灵的这一结果长期未引起注意，一直到P.瑙尔在1963年和E.F.费洛伊德在1966年重新提出这一方法后，才引起计算机科学界的重视。此后，有不少理论工作者在从事这方面的研究。但正如E.W.戴克斯特拉在70年代中期曾指出的，实际有效的方法是边设计边验证，在设计完毕时证明或验证的过程也同时结束。J.T.施瓦兹和M.戴维斯70年代后期提出了一种他们称之为“正确程序技术”的软件技术。这种方法是先选定成千种基本程序模块，并借助已知的各种验证方法（包括程序正确性证明）来保证这些基本程序的正确性。然后再提出一组能保持正确性的程序组合规则。这样，就可以通过不断的组合，生成各种各样的程序。
有人指出，程序正确性证明技术所发展出来的“循环不变式”，即一个程序中的某一循环的入口或出口点上所附的谓词，有些文献中称作“归纳断言”，可以用来供程序研究用。也就是说，不像过去那样，对一个给定的程序找出其若干个循环不变式，然后借助这些不变式来证明这个程序的正确性；而是在编制这个程序之前，根据对这一程序的要求，找出若干个循环不变式，然后根据这些不变式来生成这个程序。
自动程序设计的概念也是从40年代提出的。图灵在1947年的一篇论文中，提出借助定理证明的方法来设计程序。他的想法大致如下:设要求设计一个程序,使成为计算一个给定的递归函数F(X)的程序，并令F(n)=m（这里n是任一自然数，m是自然数），需要找到一个证明F(n)=m的构造性证明。在有了这样一个构造性证明以后，就可以从这个证明中提取出F(X)的求值算法，然后生成所需要的程序。图灵的这一思想长时间不为人所知。1969年又有人独立地提出了这一想法。
程序语言的形式语法的研究，从50年代中期起有了较大的发展。而形式语义的研究自60年代以来虽有不少研究工作者从事这方面的工作，提出几种不同的语义理论，主要是操作语义学、指称语义学或称数学语义学、公理语义学和代数语义学，但仍没有一种公认在软件技术中够用的形式语义学，因而需要提出一种更适于用到实际计算中的新的语义学。
在程序正确性证明和形式语义学中应用的程序逻辑，是60年代末发展起来的。这是谓词逻辑的一种扩充。原来的谓词逻辑中是没有时间概念的，所考虑的推理关系是在同一时间里的关系。程序是一种过程，一个程序的输入谓词与输出谓词之间的逻辑关系就不是同一时间里的关系。因此，在有关程序性质的推理中，原来的谓词逻辑不够用，需要有一种新的逻辑。
60年代末，E.恩格勒等人创立了算法逻辑。C.A.R.霍尔也创立了一种程序逻辑。这种逻辑是在原来的逻辑上增加一个程序算子而得到的。例如，可以将程序作为一种新的算子置于一个谓词公式的前面，如表达式 ｛S｝P(X1，…，Xn)表示在程序S执行完毕时,谓词P(X1，…，Xn)成立（这里的）X1，…，Xn是程序S 中的变量）。
算法分析和计算复杂性理论 关于算法的复杂性的研究。关于这一领域的名称曾有争论。一般认为，各类具体算法的复杂性的研究称作算法分析，而一般算法复杂性的研究称作计算复杂性理论。计算复杂性理论原是可计算理论的一支，是以各种可计算函数(即递归函数)的计算复杂性（在早期称作“计算难度”）为其研究对象的。可计算性分为理论可计算性和实际可计算性两种。作为可计算性理论一支的计算复杂性理论，是以前者的复杂程度为其研究对象的；而作为计算机科学一个领域的复杂性理论，则是以后者的复杂程度为其研究对象的。
这一分支的基本问题是要弄清楚实际可计算函数类的结构和一些性质。实际可计算性是一个直观的概念。如何对这一概念进行精确的描述，是一个并不容易的问题。60年代中期以来，有关的研究工作者一般是以计算时间多项式有界的函数作为实际可计算的函数。这实际上是一个论题，而不是一个可以在数学中加以证明或否证的命题。有人指出，在有关的多项式次数较高时（如n100的情形），很难说是实际可计算的。
另一个带根本性的问题是：确定性机器与非确定性机器的解题能力的比较问题。人们早已知道，确定性图灵机与非确定性图灵机的解题能力是相等的。因为非确定性机器虽比确定性机器效率高，而如果计算时间没有限制，则确定性机器总可以用穷举的方法来模拟非确定性机器。因此，二者的解题能力是一样的。但在计算时间多项式有界时，二者的解题能力是否相等，这就是有名的P=? NP问题。
关于计算和算法（包括程序）的研究，对串行计算的性质研究较多，而对并行计算性质的研究则还很不够（特别是对异步的并行计算更是如此）。因此，关于并行计算的研究很可能将成为计算机理论的研究重点。
[编辑]补充
关于计算和计算机械的数学理论，也称为计算理论或计算机科学的数学基础。
学科的产生 在几千年的数学发展史中，人们研究了各种各样的计算，创立了许许多多的算法，但以计算或算法本身的性质为研究对象的数学理论却是到20世纪30年代才发展起来的。当时为了要解决数学基础的某些理论问题，即是否有的问题不是算法可解的，数理逻辑学家提出了几种不同的（后来证明是彼此等价的）算法定义，从而建立了算法理论（即可计算性理论）。30年代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论，将数论函数的算法可计算性刻划为递归性。30年代中期，A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的概念，将问题的算法可解性刻划为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机（称为图灵机）中的一种通用机就是存储程序型的。
学科内容 理论计算机科学主要包括：①自动机论与形式语言理论;②程序理论(包括程序正确性证明、程序验证等);③形式语义学；④算法分析和计算复杂性理论。在这些领域中，自动机理论和形式语言理论是50年代发展起来的。前者的历史还可以上溯到30年代，因为图灵机就是一类自动机(无限自动机)。50年代以来一些学者开始考虑与现实的计算机更相似的理想计算机，J.诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。王浩在50年代中期提出了一种图灵机的变种，这是一种比原来的图灵机更接近现实机器的机器。他还提出一种存储带上的内容不能清除的机器，并证明这种机器是与图灵机等价的。60年代前期，又有人提出具有随机存取存储器的计算机（简称RAM）以及多带图灵机等。
形式语言理论 导源于数理语言学中的乔姆斯基理论。在这种理论中，形式语言分为四种:①0型语言；②1型语言;③2型语言;④3型语言。相应地存在着0型、1型、2 型、3型四种形式文法。1型语言又名上下文有关语言，2型语言又名上下文无关语言，3型语言又名正则语言。其中2型语言最受人注意。60年代中期，还发现了这四类语言与四类自动机之间的对应关系（见表）
在上表中，左边所列的语言恰好是右边与之对应的自动机所能识别的语言（见形式语言理论）。
程序设计理论 包括程序正确性证明和程序验证，它的一些基本概念和方法是40年代后期诺伊曼和图灵等人提出的。诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。后来图灵又证明了一个子程序的正确性。他的方法是：设有一给定的程序，且有变量X1，X2，…，Xn以及输入谓词P(X1，…，Xn)与输出谓词Q(X1，…，Xn)。如果能证明下列事实：若在程序执行前谓词P（X1，…，Xn）成立，则在程序执行后，谓词Q(X1，…，Xn)成立，程序的正确性得证。
图灵的这一结果长期未引起注意，一直到P.瑙尔在1963年和E.F.费洛伊德在1966年重新提出这一方法后，才引起计算机科学界的重视。此后，有不少理论工作者在从事这方面的研究。但正如E.W.戴克斯特拉在70年代中期曾指出的，实际有效的方法是边设计边验证，在设计完毕时证明或验证的过程也同时结束。J.T.施瓦兹和M.戴维斯70年代后期提出了一种他们称之为“正确程序技术”的软件技术。这种方法是先选定成千种基本程序模块，并借助已知的各种验证方法（包括程序正确性证明）来保证这些基本程序的正确性。然后再提出一组能保持正确性的程序组合规则。这样，就可以通过不断的组合，生成各种各样的程序。
有人指出，程序正确性证明技术所发展出来的“循环不变式”，即一个程序中的某一循环的入口或出口点上所附的谓词，有些文献中称作“归纳断言”，可以用来供程序研究用。也就是说，不像过去那样，对一个给定的程序找出其若干个循环不变式，然后借助这些不变式来证明这个程序的正确性；而是在编制这个程序之前，根据对这一程序的要求，找出若干个循环不变式，然后根据这些不变式来生成这个程序。
自动程序设计的概念也是从40年代提出的。图灵在1947年的一篇论文中，提出借助定理证明的方法来设计程序。他的想法大致如下:设要求设计一个程序，使成为计算一个给定的递归函数F(X)的程序，并令F(n)=m（这里n是任一自然数，m是自然数），需要找到一个证明F(n)=m的构造性证明。在有了这样一个构造性证明以后，就可以从这个证明中提取出F(X)的求值算法，然后生成所需要的程序。图灵的这一思想长时间不为人所知。1969年又有人独立地提出了这一想法。
程序语言的形式语法的研究，从50年代中期起有了较大的发展。而形式语义的研究自60年代以来虽有不少研究工作者从事这方面的工作，提出几种不同的语义理论，主要是操作语义学、指称语义学或称数学语义学、公理语义学和代数语义学，但仍没有一种公认在软件技术中够用的形式语义学，因而需要提出一种更适于用到实际计算中的新的语义学。
在程序正确性证明和形式语义学中应用的程序逻辑，是60年代末发展起来的。这是谓词逻辑的一种扩充。原来的谓词逻辑中是没有时间概念的，所考虑的推理关系是在同一时间里的关系。程序是一种过程，一个程序的输入谓词与输出谓词之间的逻辑关系就不是同一时间里的关系。因此，在有关程序性质的推理中，原来的谓词逻辑不够用，需要有一种新的逻辑。
60年代末，E.恩格勒等人创立了算法逻辑。C.A.R.霍尔也创立了一种程序逻辑。这种逻辑是在原来的逻辑上增加一个程序算子而得到的。例如，可以将程序作为一种新的算子置于一个谓词公式的前面，如表达式
｛S｝P(X1，…，Xn)表示在程序S执行完毕时，谓词P(X1，…，Xn)成立（这里的）X1，…，Xn是程序S 中的变量）。
算法分析和计算复杂性理论 关于算法的复杂性的研究。关于这一领域的名称曾有争论。一般认为，各类具体算法的复杂性的研究称作算法分析，而一般算法复杂性的研究称作计算复杂性理论。计算复杂性理论原是可计算理论的一支，是以各种可计算函数(即递归函数)的计算复杂性（在早期称作“计算难度”）为其研究对象的。可计算性分为理论可计算性和实际可计算性两种。作为可计算性理论一支的计算复杂性理论，是以前者的复杂程度为其研究对象的；而作为计算机科学一个领域的复杂性理论，则是以后者的复杂程度为其研究对象的。
这一分支的基本问题是要弄清楚实际可计算函数类的结构和一些性质。实际可计算性是一个直观的概念。如何对这一概念进行精确的描述，是一个并不容易的问题。60年代中期以来，有关的研究工作者一般是以计算时间多项式有界的函数作为实际可计算的函数。这实际上是一个论题，而不是一个可以在数学中加以证明或否证的命题。有人指出，在有关的多项式次数较高时（如n的情形），很难说是实际可计算的。
另一个带根本性的问题是：确定性机器与非确定性机器的解题能力的比较问题。人们早已知道，确定性图灵机与非确定性图灵机的解题能力是相等的。因为非确定性机器虽比确定性机器效率高，而如果计算时间没有限制，则确定性机器总可以用穷举的方法来模拟非确定性机器。因此，二者的解题能力是一样的。但在计算时间多项式有界时，二者的解题能力是否相等，这就是有名的P=? NP问题。
关于计算和算法（包括程序）的研究，对串行计算的性质研究较多，而对并行计算性质的研究则还很不够（特别是对异步的并行计算更是如此）。因此，关于并行计算的研究很可能将成为计算机理论的研究重点。
