可计算性
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| Turing machine | 图灵机 | tú líng jī |
| halting problem | 停机问题 | tíng jī wèn tí |
| diagonalisation/daɪˌæɡənəlaɪˈzeɪʃn/ | 对角化 | duì jiǎo huà |
算法的形式化
- 图灵机 Turing machine：纸带、读写头、状态——"算法"的形式化。停机问题 halting problem：$M$ 在 $w$ 上停吗？假设判定器 $H$ 存在；造 $D(M)$ = 跑 $H(M,M)$，说"停"就永远循环。让 $D$ 跑 $D$：矛盾。
{exercise:uni-cs1103-tm}
练习
停机问题证明造出的 D(M)——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
D 翻转关于自身的答案——让 D 跑 D 即矛盾。
对角化一遍
- 枚举所有机器与输入；对角化 diagonalisation 造出 $D$ 与每一行的对角元不一致——于是 $D$ 不同于每台机器，却又是机器。同一手法证明实数不可数与 Rice 定理。
- Rice：程序的每个非平凡语义性质都不可判定——"$P$ 会打印 banana 吗"把停机归约到打印（套件跑了包装器）。
{exercise:uni-cs1103-rice}
练习
Rice 定理覆盖——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
关于程序算什么的非平凡性质——不可判定。
可判定的表亲
- "DFA $D$ 接受空语言吗"可判定：从 $q_0$ 标记可达状态（有限图搜索），无可达接受状态即空。有限性让它可搜索——停机问题的无穷纸带正是论证断掉之处。
{exercise:uni-cs1103-decidable}
练习
DFA 空语言可判定，因为——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
有限图、有限搜索：标记可达状态、查接受态。