Intro
图灵机最早是作为一种计算模型出现的，目的是讨论在这样一种机器上能解决什么样的问题。
形式化的图灵机定义为七元组 \((Q,\Sigma,\Gamma,\delta,q_0,B,F)\)，含义分别为：状态集、输入符号集、纸带符号集、转移函数、初始状态、空符号、接受状态集。
和 PDA 的最大区别在于
- TM 的纸带两端无限长
- TM 可以读/写纸带
- TM 的读写头可以左右移动
别的没有本质区别。
对于 TM 的 ID \((q,\alpha,\text{Head})\)，寸晷要求可以这么写：\(\gamma q\beta\)，其中 \(\alpha=\gamma\beta\)，且读头在 \(\beta\) 的第一个字符上。
ID 间的转移写作 \(ID\vdash ID'\)
Recursive Enumerable
给定 TM \(M\)，有两种定义其接收语言的方法
- 定义 \(H(M)=\Set{w\mid M(w)\text{ 停机}}\)
- 定义 \(L(M)=\Set{w\mid q_0w\vdash^* ID(q,\alpha,\text{Head})\wedge q\in F}\)
由 TM 定义的语言叫做递归可枚举语言（Recursive Enumerable Language）
定理：
- 任给 \(L=L(M)\)，存在 \(M'\) 使得 \(L(M)=H(M')\)；
- 任给 \(L=H(M)\)，存在 \(M''\) 使得 \(H(M)=L(M'')\)
证明：
- 对 \(M\) 稍作修改即可得到 \(M'\)
- 把所有接收状态的所有后继状态都删掉
- 对于非接收状态的未定义后继状态，设成一个死循环（永远往右走）
- 同样对 \(M\) 稍作修改即可得到 \(M''\)
- 把所有未定义后继状态的转移都重定向到新造的接受状态
注意到1的证明可能会删去一些路径：先进入接收状态，然后走出去，再次进入后停机。在修改过后这样的trace就没法出现了。但是根据定义可知，\(w\in L(M)\) 当且仅当存在一个 \(ID\) 使得 \(q_0w\vdash^* ID\) 且 \(ID\) 是接收状态，因此我们仍然可以接收这个串。即只要有一次进入接收态就算接收。
Recursive
给定 TM \(M\)，且保证 \(M\) 停机，则称 \(L(M)\) 是递归语言（Recursive Language）
这样的 \(M\) 也叫算法（Algorithm）
这样的定义意味着纯粹的 TM 不一定停机，也可能从未进入接收状态。
Variation
这些变体都是等价的，即它们作为整体接收的语言都是同一类语言——递归可枚举语言。
Multiple Tracks
原本纸带上的每个位置只有一个符号，现在纸带上的每个位置可以有 \(k\) 个符号。例如内存是以字节（8位）为单位的。
通过简单的编码就可以证明计算能力（capability）与单个纸带的等价性。
Marks
利用 Multiple Track 可以给不同的位置打上标记
Registers
状态集可以带上寄存器，其中装着有限长度的串。
Semi-infinite Tape
即单边无限的纸带。注意到存在平凡双射 \(\mathbb N\mapsto \mathbb Z\) ，因此正常 TM 的操作同样可以在 ST-TM 上完成。
Multiple Tapes
注意和 Multiple Tracks 的区别，这里是可以有 \(k\) 个读写头独立操作的。
这仍然和一般路过 TM 在计算能力上等价，即单个读写头可以模拟多个读写头并行操作的情况（单核CPU仍然可以跑多任务）。
Nondeterministic
NTM \(N\) 的每一步有多种选择可以走。定义 \(L(N)\) 为所有能走到接收状态的串 \(w\)。
注意到 \(N\) 本身也是可以编码的，可以用一个 TM \(M\) 来 bfs 模拟 \(N\) 的执行，也就是做 model checking。
并且由于前面这些等价的拓展，我们可以假定被编码的 TM 尽可能简单（例如都是 ST-TM），而作为 host 的外层 TM 可以尽可能复杂（例如可以有多个读写头），这样会比较方便。
Key-Value Store
新开两条纸带分别存 Key 和 Value。插入和删除都在纸带上扫。
Closure Property
不加解释说明是递归语言和递归可枚举语言共同具有的特性。
\(L(M_1)\cup L(M_2)\)
构造 \(M\)：
- 有两个纸带，分别跑 \(M_1,M_2\)
- 任意一个接收都接收。
\(L(M_1)\cap L(M_2)\)
和上面是类似的
\(\overline{L(M)}\)
对递归语言而言是封闭的。由终止性可知 \(M\) 必然会给出判定，只需要把结果取反即可。
对递归可枚举语言而言是不封闭的。证明：
若 \(L\) 和 \(\bar L\) 都是递归可枚举的，那么可以取 \(M,\bar M\) 分别为判定 \(L,\bar L\) 的 TM。
- 对于输入 \(w\) 分别喂给 \(M,\bar M\)
- 若 \(M\) 停机，则停机进入接收态
- 若 \(\bar M\) 停机，则停机进入非接收态
这说明 \(L\) 将会是递归语言。
注意到我们的论证仅依赖于 \(L\) 及 \(\bar L\) 是递归可枚举的，因此一切递归可枚举语言都是递归语言。
上面这条很容易举出反例（例如后面会说的停机问题），矛盾；故假设不成立。
\(LR\)
对于递归语言的联，只需要枚举分界线，然后用两个 TM 分别判定就可以了。为了避免麻烦的停机，这里的分界线枚举可以用 NTM。
对于递归可枚举语言需要保证两个 TM 是并行跑的（调度公平即可）
\(L^R\)
只需要用 TM 把输入翻转一次就好了。
\(f^{-1}(L)\)
对于输入 \(w\) 得到 \(f(w)\)，然后放在 \(L\) 的 TM 上跑一下得到结果。