图灵机
字数 2838 2025-12-19 06:37:22
好的，我注意到在已讲过的词条列表中，虽然出现了很多关于λ-演算、类型系统和计算模型的词条，但关于其核心计算模型之一图灵机的具体构造与运行细节尚未系统讲解。因此，我将为您生成这个词条。
图灵机的基本构造与运行
我将把图灵机的知识从最直观的概念开始，逐步深入到其形式化定义和运行机制。
步骤1：核心直觉与物理类比
想象一个非常简单的“理想化计算机”。它由三部分组成：
- 一条无限长的纸带：纸带被划分为一个个连续的格子。每个格子可以写入一个来自某个有限字母表（例如 {0, 1, }，其中 ‘’ 代表空白）的符号。
- 一个读写头：一次对准纸带上的一个格子。它可以做三件事：读取当前格子里的符号、擦除并写入一个新符号、向左或向右移动一格。
- 一个状态寄存器：存储机器当前的“思维状态”。状态的数量是有限的（例如 “q0”， “q1”， “q_accept”， “q_reject”）。
这个机器的运行完全由一套固定的规则（即程序）所决定。这个规则表告诉它：“当你处于状态A，并且读到符号X时，你应该写入符号Y，将读写头向左/右移动，然后切换到状态B。”
步骤2：形式化定义
现在，我们将上述直觉形式化为一个数学对象。一个**（确定型）图灵机** M 是一个七元组：
M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
让我们逐一解释每个部分：
- Q：一个有限的状态集合。
- Σ：输入字母表，一个有限符号集合。它不包含空白符号 ‘_’（或 ‘␣’）。
- Γ：纸带字母表，一个有限符号集合。它满足 Σ ⊆ Γ，并且包含一个特殊的空白符号 ‘_’ ∈ Γ。机器可以在纸带上写入 Γ 中的任何符号。
- δ：转移函数。这是图灵机的“程序”或“大脑”。
- 函数签名：δ: Q × Γ → Q × Γ × {L, R}
- 含义：当机器处于状态 q ∈ Q，并且读写头读到符号 a ∈ Γ 时，转移函数 δ(q, a) = (q’, a’, D) 规定：
- 将状态变为 q’ ∈ Q。
- 在当前格子写入符号 a’ ∈ Γ（覆盖原来的 a）。
- 将读写头移动一个格子，方向由 D 决定：L 表示向左，R 表示向右。
- q₀ ∈ Q：起始状态。机器开始运行时的初始状态。
- q_accept ∈ Q：接受状态。一个特殊的状态。
- q_reject ∈ Q：拒绝状态。另一个特殊的状态，且 q_accept ≠ q_reject。
步骤3：配置与运行过程
要描述图灵机在某一“瞬间”的完整快照，我们引入配置的概念。
一个配置由三部分组成：
- 机器当前的状态 q。
- 纸带上所有非空白内容（但为了完备，我们通常考虑读写头附近有限的一段）。
- 读写头当前位置。
通常记为：u q v
- q 是当前状态。
- uv 是纸带上的内容（u 是读写头左侧的部分，v 是读写头当前位置及右侧的部分）。
- 下划线标记读写头正指向 v 的第一个符号。例如，
01 q3 101表示状态为 q3，纸带内容是01101，读写头正指向第二个1。
运行过程：从初始配置（输入字符串写在纸带上，读写头指向最左端符号，状态为 q₀）开始，反复应用转移函数 δ，从一个配置产生下一个配置。这个过程称为计算。
步骤4：停机与接受/拒绝
计算在以下情况下停止（停机）：
- 机器进入 q_accept 状态。此时，我们称图灵机接受了初始输入字符串。
- 机器进入 q_reject 状态。此时，我们称图灵机拒绝了初始输入字符串。
- （注意：转移函数 δ 可能对某些 (q, a) 没有定义。如果遇到这种情况，机器也会停止，但根据约定，这通常被视为进入拒绝状态。另一种定义是让 δ 成为一个全函数，明确处理所有情况。）
如果计算永不停止，则称图灵机在给定输入上不停机（或进入循环）。
步骤5：一个简单示例
让我们构造一个图灵机 M，它判断一个二进制字符串是否以 0 结尾（即，识别语言 {w | w以0结尾}）。
定义：
- Q = {q₀, q1, q_accept, q_reject}
- Σ = {0, 1}
- Γ = {0, 1, _}
- 转移函数 δ 如下表所示（未列出的组合意味着进入
q_reject）：
| 当前状态 (q) | 读到的符号 (a) | 写入的符号 (a’) | 移动方向 (D) | 新状态 (q’) |
|---|---|---|---|---|
| q₀ | 0 | 0 | R | q₀ |
| q₀ | 1 | 1 | R | q₀ |
| q₀ | _ | _ | L | q1 |
| q1 | 0 | 0 | (不动) | q_accept |
| q1 | 1 | 1 | (不动) | q_reject |
| q1 | _ | _ | (不动) | q_reject |
运行输入 “10”：
- 初始配置：
q₀ 1 0（状态 q₀，读写头在 ‘1’ 上） - 应用 δ(q₀, 1) → (q₀, 1, R)：向右移动，状态不变。新配置：
1 q₀ 0 - 应用 δ(q₀, 0) → (q₀, 0, R)：向右移动，状态不变。新配置：
10 q₀ _ - 应用 δ(q₀, _) → (q1, , L)：写入 ‘’（实际还是空白），向左移动，进入状态 q1。新配置：
1 q1 0 - 应用 δ(q1, 0) → (q_accept, 0, -)：接受！机器停机并接受输入。
通过这个逐步构建的过程，您应该能理解图灵机作为计算模型的基本思想：它通过有限的状态、无限的存储介质（纸带）和确定的局部规则，来模拟一步一步的计算过程。它是现代计算机理论的核心模型，也是讨论“可计算性”和“计算复杂性”的基石。