计算理论初步

通常假设图灵机不存在从终态出发的转移。 被图灵机接受的语言称为递归可枚举语言。

图灵机的停机

若对于某个 ID，图灵机不存在合法移动，则称图灵机停机，ID 称为停机格局。

• 到达终态后总是停机
• 对于不接受的串，图灵机不一定能停机，还可能有无限个推导

对所有输入都能停机的图灵机称为判定器。

• 可以被判定器接受的语言称为递归语言
• 递归语言是递归可枚举语言的真子集

Theorem

$L$ 为递归语言当且仅当 $L$ 和 $\overline{L}$ 均为递归可枚举语言（RE）

• 是否所有语言都是递归可枚举语言？
• 是否所有递归可枚举语言都是递归语言？
• 如果 $X$ 是递归可枚举的但不是递归的，则 $\overline{X}$ 不是递归可枚举的
  • $L$ 不是递归的 $\iff \overline{L}$ 不是递归的

图灵机的编码

假定图灵机：

• 输入字母表为 $\{0,1\}$
• $q_1$ 为初态，$q_2$ 为终态
• $X_1$ 为 0，$X_2$ 为 1，$X_3$ 为 $B$
• $D_1$ 和 $D_2$ 分别代表 $L$ 和 $R$

对于转移规则 $\delta (q_i,X_j)=(q_k,X_l,D_m)$，可以编码为 $0^{i}10^{j}10^{k}10^{l}10^m$ 所有转移规则合并为 $C_{1}11C_{2}11\dots 11C_n$，可以视为图灵机的编码。

非递归可枚举语言

任意 $0,1$ 串 $w$ 用 $1w$ 编码，表示一个二进制数 $M_i$ 代表编码为 $w_i$ 的图灵机

• 如果 $w_i$ 不是有效的图灵机编码，则视为一个有状态但没有转移的图灵机，$L(M_i)=\varnothing$ 则 $\Sigma =\{0,1\}$ 上的递归可枚举语言的集合为 $\{L(M_i)|i\in {\mathbb{N}}^{\ast }\}$ 是一个可数集，但 $\Sigma$ 上所有语言的集合为 $2^{{\Sigma }^{\ast }}=\{L|L\subseteq {\Sigma }^{\ast }\}$，是一个不可数集，因此非递归可枚举语言必然存在。

对角语言

$L_d=\{w_i|w_i\notin L(M_i)\}$ 若 $L_d=L(M_i)$，则 $w_i\notin L(M_i)$，则 $w_i\in L_d=L(M_i)$，矛盾 因此 $L_d$ 为非递归可枚举语言。

非递归语言的递归可枚举语言

图灵机和输入串可以编码为 $C111w$，记为 $⟨M,w⟩$ 定义通用语言

$$L_u=\{⟨M,w⟩|w\in L(M)\}$$

可以构造一个图灵机 $U$，使得 $L_u=L(U)$，模拟图灵机 $M$ 判断是否接受 $w$，称这样的图灵机为通用图灵机

Theorem

$L_u$ 是递归可枚举的，但不是递归的

如果 $L_u$ 是递归的，则 $\overline{L_u}$ 也是递归的。设 $\overline{L_u}=L(M)$，则可以构造图灵机 $M^{\prime }$，使得 $L_d=L(M^{\prime })$，矛盾

问题与归约

与 $L$ 对应的问题是给定一个串 $w$，判定 $w\in L$ 是否成立

• 问题必须找到有限编码的输入

通用语言 $L_u$ 对应的问题：任给图灵机 $M$ 和输入串 $w$，$M$ 是否接受 $w$ 图灵机停机问题： $L_h=\{⟨M,w⟩|对于输入串w，M将停机\}$

可判定性

一个问题对应的语言是递归的，则称问题是可判定的，否则是不可判定的。

• $L_u$ 不是递归的，因此图灵机接受问题是不可判定的。

归约

若存在 $x\to f(x)$ 的算法，使得 $x\in L_1\iff f(x)\in L_2$，则称 $P_1$ 可以归约到 $P_2$

• ! 算法必须是有限步的

• $P_2$ 至少有 $P_1$ 这么难

• 如果 $P_2$ 是可判定的，则 $P_1$ 也是可判定的

• 如果 $P_2$ 是递归可枚举的，则 $P_1$ 也是递归可枚举的

• 常用于证明 $P_2$ 是困难的：将某个困难的问题 $P_1$ 归约到 $P_2$

图灵机接受问题可以归约到图灵机停机问题： 对于实例 $(M,w)$，构造 $M^{\prime }$，使得对于接受的串停机，对于不接受的串无限循环，则 $(M,w)$ 的答案与 $(M^{\prime },w)$ 的答案相同，该构造是一个算法。

• 因此停机问题是不可判定的

记 RE 是所有递归可枚举语言的集合（递归可枚举语言类），递归可枚举语言的性质是 RE 的一个子集 $P$，若 $P$ 是 RE 的非空真子集，则称 $P$ 为非平凡性质。 语言 $L\in RE$ 在某个性质的集合中，就说 $L$ 具有某种性质。 $L$ 是否具有某种性质的问题，就是 $L$ 的图灵机 $M$ 的编码是否在语言 $\{⟨M⟩|L(M)\in P\}$ 中的问题。

Rice 定理

有关递归可枚举语言的任何非平凡性质都是不可判定的。

• 图灵机的语言是否非空的问题是不可判定的
• 同理递归可枚举语言是否为空或正则语言或上下文无关语言也是不可判定的
• 不可判定的是语言 $L(M)$ 的性质，对应的问题应该只涉及语言 $L(M)$

PCP 问题

PCP 的一个实例包含同一字母表上的两组字符串，$A=w_1,w_2,\dots ,w_k$，$B=x_1,x_2,\dots ,x_k$，称 PCP 的该实例有解当且仅当存在整数序列 $i_1,\dots ,i_m$ 使得 $w_{i_1}{w}_{i_2}\dots w_{i_m}=x_{i_1}{x}_{i_2}\dots x_{i_m}$

• PCP 问题是不可判定的
• 可将 $L_u$ 归约到 PCP

构造 CFG $G$，包含以下产生式：

$$\begin{array}{rl}S& \to A|B\\ A& \to w_{1}A{a}_1|\dots |w_{k}A{a}_k|w_1{a}_1|\dots |w_k{a}_k\\ B& \to x_{1}B{a}_1|\dots |x_{k}B{a}_k|x_1{a}_1|\dots |x_k{a}_k\end{array}$$

可知 PCP 的该实例有解当且仅当 G 是歧义的，即 PCP 可以归约到问题是否一个给定的 CFG 是歧义的

时间复杂性

对任何长为 $n$ 的输入串 $w$，$M$ 可在最多 $T(n)$ 步内停机，则称 $M$ 的时间复杂度为 $T(n)$

P & NP

P & NP

若问题 $L$ 满足存在一个图灵机 $M$ 使得 $L=L(M)$ 且 $M$ 的时间复杂度 $T(n)$ 为多项式，则称该问题是 P 问题，即 L 属于 P 若问题 $L$ 满足存在一个非确定型图灵机 $M$ 使得 $L=L(M)$ 且 $M$ 的时间复杂度 $T(n)$ 为多项式，则称该问题是 NP 问题，即 L 属于 NP

• P $\subseteq$ NP

如果问题 $P_1$ 可以在多项式时间内归约到问题 $P_2$

• 若 $P_2$ 为 P 问题，则 $P_1$ 也是 P 问题
• 若 $P_2$ 是 NP 问题，则 $P_1$ 也是 NP 问题
• 若 $P_1$ 不是 P 问题，则 $P_2$ 也不是 P 问题
• 若 $P_2$ 不是 NP 问题，则 $P_2$ 也不是 NP 问题

NP 完全问题

称 $P_C$ 为 NP 完全问题当且仅当

• $P_C$ 是 NP 问题
• 若 $P^{\prime }$ 是任一 NP 问题，则 $P^{\prime }$ 可以多项式时间归约到 $P_C$

• 若 $P_2$ 是 NP 问题，$P_1$ 是 NP 完全问题，$P_1$ 可多项式时间归约到 $P_2$，则 $P_2$ 也是 NP 完全问题
• NP 问题可以理解为可以在多项式时间内验证答案是否正确的问题
• 若可以证明某个 NPC 问题是 P 问题，则可以证明 P = NP（即容易验证的问题均是容易解的问题）

NP 难问题

若可以证明 $P_H$ 满足条件 2，但不能证明条件 1，称 $P_H$ 是 NP 难问题

难度：NP 难 > NP 完全 $\ge$ NP > P

SAT 问题

任给一个布尔表达式，它是否是可满足的？

Cook 定理

SAT 是 NP 完全问题