前置条件与学习目标

这门课程适合谁？

本课程面向希望理解计算的本质与边界，以及想了解软件能力极限的软件工程师和计算机从业者。

先修要求

学习计算理论之前，建议具备典型入门编程课程所需的基础编程知识。此外，若你熟悉以下离散数学基础概念，将更有助于学习：

• 集合
• 关系
• 函数
• 模运算
• 对数的概念
• 一阶谓词逻辑
• 简单有向图的结构

学习目标

本课程涵盖计算理论的核心成果，通过大量实例，有时还结合可运行的 Python 程序进行讲解，在尽量减少数学形式化的前提下保持一定的严谨性。形式化证明较少出现，但构造性论证贯穿始终。虽然会根据需要引入数学符号，但更倾向于使用可视化方式帮助理解概念。课程涵盖的主要内容包括：

• 形式语言与有限状态机
• 确定性与非确定性有限自动机
• 正则表达式与文法
• 正则语言的性质
• 上下文无关语言
• 下推自动机
• 上下文无关文法
• 上下文无关语言的性质
• 图灵机
• 形式语言的分类体系
• 可计算性

课程重点在于形式语言的结构、性质及其应用，并初步介绍可计算性理论。

本课程使用 Python 3，因为 Python 是最易读的编程语言之一，常被称为“可执行的伪代码”。它在众多计算领域中被广泛使用，且具有良好的通用性。Python 语法作为一种有效工具，有助于在可计算性导论章节中简洁地讲解如何将一个不可解问题归约为另一个问题。