计算机理论研究计算的数学基础。最基本的问题是试图回答哪些问题本质上可以用计算机解决，哪些问题本质上短时间内解决不了。经过半个多世纪的发展，理论计算机科学的研究内容按照来源可以分为三类:
作为数学的一个分支，和数学的其他分支一样，自身逻辑的发展会产生新的子领域、工具和问题。
计算机技术、信息技术等应用的发展会产生新的基础问题，如机器学习理论、编码理论等。
理论处于计算机科学与其他基础学科交叉的前沿，如自然科学中的物理学和生物学，社会科学中的经济学和社会学等。
对于以上三个问题，在类型和动机上都有很大的区别。即使是同一个源，也有不同类型的问题。一些发展起来的子领域已经基本独立，如量子计算和信息处理、密码学等。大部分子领域都形成了自己相对独立的研究群体，都有自己标志性的会议。如复杂性理论的CCC，计算经济学的EC，机器学习理论的COLT，计算几何的SoCG等。这些都说明理论计算机是一个庞大的领域，学科众多，不同子领域的研究人员往往很难相互理解对方的工作。边肖不能讲理论计算机的所有分支，只能围绕理论计算机不同领域的本质共性，讨论其最基本的问题和思维方式。理论计算机有很多特点。与其他计算机学科相比，不仅仅是研究对象的不同。在研究方法、动机、思路上也有很大差异。这里阐述了理论计算机的研究方法、主要动机和目标，以及学科的思维方式。
1.数学的一个分支
理论研究最大的特点就是它是数学的一个分支。因此，它的每一个概念都必须有严格的形式数学定义；它的每一个结果都必须以数学定理的形式出现；而其获得结果的方法也必须是数学证明。“定义”、“定理”、“证明”这三个关键词构成了理论计算机与其他计算机学科的最大区别。比如计算机应用学科也需要设计算法，但证明算法优劣的主要途径是实验和运算的结果，而不是证明和定理。证明和定理是所有理论计算机的不同子领域中最重要的共同点。数学结果的好处是完全符合逻辑。只要没有错误，数学定理就永远是正确的。定理可以被超越，即证明存在比它更强或更广的定理，从而使它成为简单的推论；也可能是判断定义不符合实际应用，在应用中不适用，但逻辑上还是正确的。
当然，这种对形式定义和逻辑证明的严格要求也造成了很多问题，其中最主要的就是理论脱离实际。现实往往是复杂的，形式上的定义通常只是一个简化的模型。在这种模型中，通过逻辑证明得到的结论有时不能直接应用于现实。那么理论和实践统一吗？理论上是，实际上不是。在这方面，理论经济学也有类似的情况。经济学的结论不一定直接适用于个人或公司的每一个决策，但不可否认它在大方向上对我们的经济行为和发展有指导作用。理论和计算机科学的关系是相似的。
数学的另一个突出特点是系统性。一个重要而困难的结果通常是基于许多工作的。这些工作中有些提供了工具和方法，有些提供了有用的定理，目前的结果很可能为更大更重要的结果提供基础和工具。这对于数学家来说是很自然的事情，但是在与计算机应用其他领域的研究人员交流时，会遇到一些问题。比如他们问我最近在做什么，我往往要先介绍一大堆语境，对方还没真正说到工作就已经一头雾水了；另一方面，他们在给我介绍作品的时候，因为问题直接来源于现实生活，所以不管解决方案是否完善，是否实用，至少有一个演示原型可以参考。当然，系统化的工作有其独特的魅力:它就像一群非常聪明的科学家一起建造一座宏伟的知识大厦。
2.探索计算的极限。
计算机科学的大多数分支实际上都在努力使我们的计算机更强大、更有用。如果回到几十年前，很多今天习以为常的技术已经远远超出了人们的想象。我们有理由期待未来的计算机技术会更加强大，这也是计算机科学家和工程师的努力方向。理论科学家也在尝试设计更有效的算法、更安全的密码系统和通信协议。但是理论计算机科学家仍然有一个非常重要的任务，那就是探索计算的极限。也就是说，证明了有些问题是计算机无法完成或者无法有效完成的。为了证明某些问题本质上是不可数的，艾伦·图灵在著名的图灵机论文中给出了严格的定义。
正如物理学试图探索自然和宇宙的真相一样，理论计算机科学试图探索计算和信息的真相。这和计算机应用学科很不一样。计算机应用的最初动机是解决问题，所以我一直希望能给出一个解决方案。对于他们来说，如果证明某个问题在某种意义上无法解决，那么结果就是不满意的。但是对于理论计算机来说，它最初的动机是探索真理，所以如果证明了某个问题在某种意义上无法解决，那也是一个很重要的结果，甚至是某种意义上更深刻的结果。像密码学一样，我们希望从理论上证明破解一个密码系统是很难的。这种安全的口令系统和协议是现代网络通信和网络经济的重要基础。
3.一种思维方式
有时候，对于一篇理论计算机的论文，外人看不出和计算、算法、复杂度有直接关系，但圈内人一眼就能确定是一篇理论计算机论文。原因在于其独特的思维方式。边肖认为，大多数理论上的计算机工作遵循以下三步模型:
什么是X，给个正式严格的定义；
证明什么对X是可行的；
证明什么对x不可行。
只要这个X与计算、信息、通信等有关，就是理论计算机领域的相关研究。例如:
当ⅹ换成“计算”时，就是可计算性理论。计算的形式化定义由图灵机实现。我们可以证明有些问题可以用图灵机计算，更重要的是可以证明其他问题，比如停机时间，是图灵机无法解决的。
当X换成“有效计算”时，就是复杂性理论，是现代理论计算机的核心部分。
当ⅹ换成“学习”的时候，就是机器学习理论。其中，学习的一个正式定义是图灵奖获得者莱斯利·瓦伦蒂(Leslie valente)的可能近似正确学习模型。有了严格的定义，我们就可以讨论哪些概念可以学，哪些不可以。
x换成“学不会”就是密码学。即使第三方得到了密文或者窃听了通信过程，也不可能知道任何隐私信息。
广义地说，理论计算机中的大多数工作都遵循上述三步模型。对于X来说，从现实和应用的角度来看，往往有一些直观的概念，甚至有一些例子说明有些问题是可行的。但由于没有严格的形式定义，我们无法证明任何问题都是不可行的。
