Chomsky Hierarchy
| 类型 | 名称 | 工具 |
|---|---|---|
| Type 3 | Regular Language | FSM |
| Type 2 | Context-Free Language | CFG + PDA |
| Type 1 | Context-Sensitive | LBA |
| Type 0 | Recursively Enumerable | Turing Machine |
图灵机 = 能模拟“任何程序”的模型
Definition of Turing Machine
图灵机是一个 7 元组：$M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$ 解释：
| 符号 | 含义 |
|---|---|
| Q | 状态集合 |
| Σ | 输入字母表 |
| Γ | 带字母表（包含 Σ + 空白符） |
| δ | 转移函数 |
| q₀ | 初始状态 |
| B | 空白符（blank） |
| F | 接受状态集合 |
转移函数: $\delta(q, a) = (q', b, D)$
含义：当前在状态 q，读到 a：
- 写成 b
- 移动方向 D（L 或 R）
- 转到 q'
Meaning
图灵机是一种具有无限内存、可读写、可回溯的计算模型，能够通过 accept/reject 状态决定输入，并且可能不会停止
- 为什么 TM 比 FSM 强？
- 有无限内存
- 可以读写
- 可以回头
| 特性 | FSM | TM |
|---|---|---|
| 内存 | ❌ 无 | ✅ 无限 |
| 操作 | 读 | 读+写 |
| 移动 | 单向 | 左右 |
| 能力 | 正则语言 | 所有可计算问题 Turing machines capture the intuitive notion of an algorithm |
| 1. 什么是 halting？ | ||
| - 进入 accept/reject 状态并停止 | ||
| - TM 不一定会停下来 可能会无限循环 |
Decider for $A = \{0^{2^n} \mid n \ge 0\}$
- Sweep left to right across tape crossing off every other zero（从左到右扫描磁带，每隔一个0做标记）
- If in step 1, the tape contained a single 0, accept（若扫描后只剩一个0，则接受）
- If in step 2, the tape contained more than one 0 but an odd number of zeros, then reject（若0的个数大于1但为奇数，则拒绝）
- Move tape back to the left end of the tape（将读写头移回磁带最左端）
- Repeat step 1（重复步骤1）
Meaning
A 表示的是若干个数量的 0，这里 0 的数量必须是 2 的幂级数
核心思想就是 从左往右扫描这个字符串，每隔一个 0 就划掉一个 0，一直重复，每次回头重复判断是不是就剩下最后一个 0 了，如果就剩下一个 0 就 accept，如果剩下的是大于 0 的奇数则 reject，否则就继续接着扫描
