计算的本质
本文是对 Tom Stuart 所著《Understanding Computation》一书核心概念的梳理与延伸，围绕两个主题展开：程序语义的形式化描述方法，以及计算模型的层次分类。
语义
程序的"含义"（meaning）可以通过不同的形式化方法来定义。这些方法统称为形式语义学（formal semantics），主要分为以下几类。
小步语义（Small-Step Semantics）
小步语义也称为结构化操作语义（Structural Operational Semantics, SOS），由 Gordon Plotkin 提出。其核心思想是：定义一组规约规则（reduction rules），每次只对表达式做一步化简，逐步迭代直到得到最终值。
例如，对表达式 (1 + 2) * 3 的求值过程：
1 | |
小步语义的优势在于能够精确描述求值的每一个中间状态，适合分析程序的执行顺序、副作用和并发行为。
大步语义（Big-Step Semantics）
大步语义也称为自然语义（Natural Semantics），由 Gilles Kahn 提出。与小步语义不同，大步语义直接定义"表达式 e 在环境 σ 下求值为结果 v"这一关系，记作 ⟨e, σ⟩ ⇓ v。
对于复合表达式，大步语义的处理方式是：先递归求值子表达式，再将子结果组合得到最终结果。这种方式更接近递归下降解释器的实现。
| 维度 | 小步语义 | 大步语义 |
|---|---|---|
| 求值粒度 | 每次一步 | 一步到位 |
| 中间状态 | 可观察 | 不可观察 |
| 实现方式 | 迭代/循环 | 递归 |
| 适用场景 | 并发分析、调试 | 编译器优化、类型推导 |
操作语义（Operational Semantics）
操作语义是小步语义和大步语义的统称。其核心思想是：想象一台理想的抽象机器，然后为程序在这台机器上的执行定义精确的规则。操作语义关注的是"程序如何执行"。
指称语义（Denotational Semantics）
指称语义由 Dana Scott 和 Christopher Strachey 提出。其核心思想是：将程序的含义映射到某个数学对象（通常是函数），用一种更底层、更形式化的数学语言来解释当前编程语言的语义。
指称语义关注的是"程序是什么"（即程序表示的数学对象），而非"程序如何执行"。例如，一个排序程序的指称语义就是"一个将无序序列映射为有序序列的函数"，不关心具体使用了快排还是归并排序。
公理语义（Axiomatic Semantics）
公理语义由 Tony Hoare 提出，以 Hoare 三元组 {P} S {Q} 为核心工具：前置条件 P 成立时，执行语句 S 后，后置条件 Q 必然成立。
公理语义关注的是"程序的性质"，适合用于程序验证和正确性证明。
语义方法对比
| 方法 | 核心问题 | 代表人物 | 典型应用 |
|---|---|---|---|
| 操作语义 | 程序如何执行 | Plotkin, Kahn | 解释器实现、语言规范 |
| 指称语义 | 程序是什么 | Scott, Strachey | 语言设计、等价性证明 |
| 公理语义 | 程序的性质 | Hoare | 程序验证、形式化证明 |
状态机与计算模型的层次
计算理论的核心问题是：什么问题是可计算的？不同的计算模型具有不同的计算能力，形成一个从弱到强的层次结构。
确定性有限自动机（DFA）
DFA（Deterministic Finite Automaton）是最简单的计算模型。它由有限个状态、一个输入字母表、一个转移函数、一个起始状态和一组接受状态组成。
关键特征：
- 确定性：在任何状态下，对于任何输入符号，下一个状态是唯一确定的
- 无记忆：除了当前状态本身，没有额外的存储空间
- 识别能力：能识别正则语言（Regular Language），如
a*b+、邮箱格式等
在工程实践中，领域模型的状态机（如订单状态流转、审批流程）通常设计为 DFA，因为确定性使得系统行为可预测、可测试。
非确定性有限自动机（NFA）
NFA（Nondeterministic Finite Automaton）与 DFA 的区别在于：在某个状态下，对于同一个输入符号，可以有多个可能的下一状态；此外，NFA 允许 ε-转移（不消耗输入符号的状态转换）。
关键定理：任何 NFA 都可以转换为等价的 DFA（子集构造法）。这意味着 NFA 和 DFA 的计算能力相同，都只能识别正则语言。NFA 的价值在于它通常比等价的 DFA 更简洁，更容易构造。
能被一台特定自动机接受的字符串集合称为一种语言——这台机器识别了这种语言。
确定性下推自动机（DPDA）
DPDA（Deterministic Pushdown Automaton）在 DFA 的基础上增加了一个栈（stack）作为辅助存储。栈提供了"后进先出"的无限存储能力，使得 DPDA 能够处理需要"匹配"和"计数"的问题。
识别能力：能识别确定性上下文无关语言（Deterministic Context-Free Language），如：
- 括号匹配：
((())) - HTML/XML 标签嵌套
- 编程语言的语法结构
非确定性下推自动机（NPDA）的能力严格强于 DPDA，能识别所有上下文无关语言。这与有限自动机不同——NFA 和 DFA 等价，但 NPDA 和 DPDA 不等价。
确定型图灵机（DTM）
DTM（Deterministic Turing Machine）由 Alan Turing 于 1936 年提出，是理论计算机科学中最重要的计算模型。它在下推自动机的基础上，将栈替换为一条无限长的纸带（tape），读写头可以在纸带上左右移动。
关键特征：
- 通用性：图灵机可以模拟任何其他计算模型（Church-Turing 论题）
- 可计算性边界：图灵机能解决的问题就是所有可计算问题的边界
停机问题
停机问题（Halting Problem）是图灵在 1936 年证明的第一个不可判定问题：不存在一个通用算法，能够判断任意程序在给定输入上是否会终止。
这一结论的深远意义在于：存在一些问题是任何计算机都无法解决的，无论硬件多强大、时间多充裕。
计算模型层次总结
| 计算模型 | 存储能力 | 识别的语言类 | 典型应用 |
|---|---|---|---|
| DFA/NFA | 无额外存储 | 正则语言 | 正则表达式、词法分析、状态机 |
| DPDA/NPDA | 栈（无限） | 上下文无关语言 | 语法分析、括号匹配、编译器 |
| 图灵机 | 纸带（无限） | 递归可枚举语言 | 通用计算、可计算性理论 |
这个层次结构对应 Chomsky 语言层次（Chomsky Hierarchy）：
1 | |
理解这个层次结构的实践意义：当面对一个问题时，先判断它属于哪个层次，就能选择最合适（最简单但足够强大）的计算模型来解决。例如，用正则表达式解析 HTML 是不可行的，因为 HTML 的嵌套结构属于上下文无关语言，超出了正则语言的表达能力。