计算理论简介

计算理论是计算机科学的基石，它试图从根本上回答三个关于“计算”这一过程的终极问题：

• 能做什么？什么是算法？（可计算性, 不可判定性）
• 用什么模型来做？（自动机与模型）
• 能多快/多好地做？（复杂性）(本课程未涉及)

这门学科本质上是数学的一个分支，它使用严谨的、抽象的数学模型来探索计算的本质、能力和极限

该课程安排在大三秋冬学期, 参考课本为《Elements of the Theory of Computation》. 课程的宏观框架如下:

一、 数学预备知识（基础）

在深入探讨计算理论之前，课程首先介绍了所需的基础数学语言和概念。这部分对应课本的第1章。

核心内容：集合、关系、函数、有穷与无穷集合 、基本的证明技术（如数学归纳法、鸽巢原理和对角化方法）、字母表与语言，以及算法的初步介绍 。

二、 形式语言与自动机理论

这是计算理论的第一大核心板块。它主要研究“受限制的计算模型” ，探索它们的能力边界，这些模型在电路设计和编译器（如词法分析）等领域有实际应用 。这部分对应第2章和第3章。

正则语言 (Regular Languages)：

• 计算模型：使用有穷自动机 (Finite Automata) ，包括确定型（DFA）和非确定型（NFA） 。
• 语言表示：使用正则表达式 (Regular Expressions) 。
• 关键结果：证明了非确定型有穷自动机、确定型有穷自动机和正则表达式三者在表达能力上是等价的 。
• 研究问题：状态最小化 、正则语言的泵定理（Pumping Lemma）以及如何证明一个语言不是正则的 。

上下文无关语言 (Context-Free Languages)：

• 计算模型：使用下推自动机 (Pushdown Automata) 。这是一种比有穷自动机更强，增加了“栈”（一种下推存储器）的计算模型 。
• 语言表示：使用上下文无关文法 (Context-Free Grammars) 。

上下文无关语言 (Context-Free Languages)：

• 计算模型：使用下推自动机 (Pushdown Automata) 。这是一种比有穷自动机更强，增加了“栈”（一种下推存储器）的计算模型 。
• 语言表示：使用上下文无关文法 (Context-Free Grammars) 。
• 研究问题：语法分析（Parsing）与语法分析树（Parse Trees） 、文法的歧义性（Ambiguity）、以及上下文无关语言的泵定理。

三、 可计算性理论 (Computability Theory)

这是计算理论的第二大核心板块。它旨在建立一个“算法的一般模型”，并利用这个模型来回答计算机科学的根本问题：什么是可计算的？什么是不可计算的？这部分对应第4章和第5章。

通用计算模型 (General Model of Computation)： - 核心模型：Turing 机 (Turing Machine) 。图灵机被视为描述任意算法的通用框架 。 - 研究内容：引入Turing机的变种（如多带Turing机、随机存取Turing机） ，并证明它们在计算能力上都等价于基本的Turing机模型 。这也引出了 Church-Turing 论题 。

不可判定性 (Undecidability)： - 核心问题：研究那些被证明“根本不可能用计算机解决”的问题 。 - 关键结果：证明停机问题 (The Halting Problem) 是不可判定的 。 - 研究内容：讨论其他不可判定的问题，如与文法或铺砖问题相关的不可解问题 。

最后一部分是计算复杂性理论 (Complexity Theory), 这是计算理论的第三大核心板块。它研究那些可计算的问题，并根据其解决所需的资源（主要是时间或空间）来对其进行分类，探讨哪些问题存在“实际可行的算法”; 这部分定义了计算复杂性的概念，如P类问题、NP类问题、NPC问题和NP完全问题等, 由于课时安排暂且按下不表.