Intro

图灵机最早是作为一种计算模型出现的，目的是讨论在这样一种机器上能解决什么样的问题。

形式化的图灵机定义为七元组 $(Q,\Sigma,\Gamma,\delta,q_0,B,F)$，含义分别为：状态集、输入符号集、纸带符号集、转移函数、初始状态、空符号、接受状态集。

和 PDA 的最大区别在于

1. TM 的纸带两端无限长
2. TM 可以读/写纸带
3. TM 的读写头可以左右移动

别的没有本质区别。

对于 TM 的 ID $(q,\alpha,\text{Head})$，寸晷要求可以这么写：$\gamma q\beta$，其中 $\alpha=\gamma\beta$，且读头在 $\beta$ 的第一个字符上。

ID 间的转移写作 $ID\vdash ID’$

Recursive Enumerable

给定 TM $M$，有两种定义其接收语言的方法

1. 定义 $H(M)=\Set{w\mid M(w)\text{ 停机}}$
2. 定义 $L(M)=\Set{w\mid q_0w\vdash^* ID(q,\alpha,\text{Head})\wedge q\in F}$

由 TM 定义的语言叫做递归可枚举语言（Recursive Enumerable Language）

定理：

1. 任给 $L=L(M)$，存在 $M’$ 使得 $L(M)=H(M’)$；
2. 任给 $L=H(M)$，存在 $M’’$ 使得 $H(M)=L(M’’)$

证明：

1. 对 $M$ 稍作修改即可得到 $M’$
   1. 把所有接收状态的所有后继状态都删掉
   2. 对于非接收状态的未定义后继状态，设成一个死循环（永远往右走）
2. 同样对 $M$ 稍作修改即可得到 $M’’$
   1. 把所有未定义后继状态的转移都重定向到新造的接受状态

注意到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$：

1. 有两个纸带，分别跑 $M_1,M_2$
2. 任意一个接收都接收。

$L(M_1)\cap L(M_2)$

和上面是类似的

$\overline{L(M)}$

对递归语言而言是封闭的。由终止性可知 $M$ 必然会给出判定，只需要把结果取反即可。

对递归可枚举语言而言是不封闭的。证明：

若 $L$ 和 $\bar L$ 都是递归可枚举的，那么可以取 $M,\bar M$ 分别为判定 $L,\bar L$ 的 TM。

1. 对于输入 $w$ 分别喂给 $M,\bar M$
2. 若 $M$ 停机，则停机进入接收态
3. 若 $\bar M$ 停机，则停机进入非接收态

这说明 $L$ 将会是递归语言。

注意到我们的论证仅依赖于 $L$ 及 $\bar L$ 是递归可枚举的，因此一切递归可枚举语言都是递归语言。

上面这条很容易举出反例（例如后面会说的停机问题），矛盾；故假设不成立。

$LR$

对于递归语言的联，只需要枚举分界线，然后用两个 TM 分别判定就可以了。为了避免麻烦的停机，这里的分界线枚举可以用 NTM。

对于递归可枚举语言需要保证两个 TM 是并行跑的（调度公平即可）

$L^R$

只需要用 TM 把输入翻转一次就好了。

$f^{-1}(L)$

对于输入 $w$ 得到 $f(w)$，然后放在 $L$ 的 TM 上跑一下得到结果。