计算复杂性作业笔记

1. 图灵机

1. 图灵可判定

已知 ATM={⟨M,ω⟩∣M 为图灵机且接受ω}\text{A}_{\text{TM}} = \left\{ \langle M, \omega \rangle \mid M\text{ 为图灵机且接受} \omega \right\} 不可判定，请证明：

  1. HALTTM={⟨M,ω⟩∣M 为图灵机且 M在输入为 ω 时停机}\text{HALT}_{\text{TM}} = \left\{ \langle M, \omega \rangle \mid M\text{ 为图灵机且 } M \text{在输入为 } \omega \text{ 时停机} \right\} 不可判定

  2. ETM={⟨M,ω⟩∣M 为图灵机且 L(M)=∅}\text{E}_{\text{TM}} = \left\{ \langle M, \omega \rangle \mid M\text{ 为图灵机且 } L(M)=\emptyset \right\} 不可判定

  3. REGULARTM={⟨M⟩∣M 为图灵机且 L(M) 为一个正则语言}\text{REGULAR}_{\text{TM}} = \left\{ \langle M \rangle \mid M\text{ 为图灵机且 } L(M) \text{ 为一个正则语言} \right\} 不可判定

  4. EQTM={⟨M1,M2⟩∣M1,M2 均为图灵机且 L(M1)=L(M2)}\text{EQ}_{\text{TM}} = \left\{ \langle M_1, M_2 \rangle \mid M_1, M_2 \text{ 均为图灵机且 } L(M_1) = L(M_2) \right\} 不可判定

1. 证明 HALTTM={⟨M,ω⟩∣M 为图灵机且 M在输入为 ω 时停机}\text{HALT}_{\text{TM}} = \left\{ \langle M, \omega \rangle \mid M\text{ 为图灵机且 } M \text{在输入为 } \omega \text{ 时停机} \right\} 不可判定

证明：反证法，假设上述语言可判定，设其其中一个判定器为 RR，则可以构建如下判定器 SS ：

S="对输入 ⟨M,ω⟩(1)对于输入 ⟨M,ω⟩ 运行图灵机 R(2)如果 R 拒绝，则拒绝(3)如果 R 接受，则模拟图灵机 M 在输入为 ω 时的运行，直至停机(4)如果 M 接受，则接受；若 M 拒绝，则拒绝"\begin{aligned} &S = \text{"对输入 } \langle M, \omega \rangle\\ &\qquad (1) \text{对于输入 } \langle M, \omega \rangle \text{ 运行图灵机 } R\\ &\qquad (2) \text{如果 } R \text{ 拒绝，则拒绝}\\ &\qquad (3) \text{如果 } R \text{ 接受，则模拟图灵机 } M \text{ 在输入为 } \omega \text{ 时的运行，直至停机}\\ &\qquad (4) \text{如果 } M \text{ 接受，则接受；若 } M \text{ 拒绝，则拒绝"}\\ \end{aligned}

由此可见，若 RR 可以判定 HALTTM\text{HALT}_{\text{TM}} ，则 SS 也可以判定 ATM\text{A}_{\text{TM}} ，但由于 ATM\text{A}_{\text{TM}} 不可判定，所以矛盾。
因此 HALTTM\text{HALT}_{\text{TM}} 不可判定。

2. 证明 ETM={⟨M,ω⟩∣M 为图灵机且 L(M)=∅}\text{E}_{\text{TM}} = \left\{ \langle M, \omega \rangle \mid M\text{ 为图灵机且 } L(M)=\emptyset \right\} 不可判定

证明：反证法，假设上述语言可判定，设其其中一个判定器为 RR，则可以构建一个入后所示的判定器 SS 。在构建 SS 之前将构造一个特殊的图灵机 M1M_1 ，使得 M1M_1 能保证拒绝除 ω\omega 外的所有字符串，而对于输入 ω\omega 则正常运行。

具体 M1M_1 构造如下：

M1="对输入 x(1)若 x≠ω 则拒绝 (2)若 x=ω 则接受"\begin{aligned} &M_1 = "\text{对输入 } x\\ &\qquad (1) \text{若 } x\neq \omega \text{ 则拒绝 }\\ &\qquad (2) \text{若 } x=\omega \text{ 则接受}"\\ \end{aligned}

这样的图灵机 M1M_1 最多只能接受 ω\omega ，其识别的语言非空当且仅当 MM 能够接受 ω\omega。这里 M1M_1 将 ω\omega 视为其描述的一部分，它扫描输入 xx 一测试 xx 是否与 ww 相同。这时我们把 M1M_1 作为 RR 的输入就可以构造出如下的判定器 SS ：

S="对输入 ⟨M,ω⟩(1)利用 ⟨M,ω⟩ 来构造出上面方法（算法）所描述构造出的 M1(3)对输入 ⟨M1⟩ 运行图灵机 R(4)如果 R 接受，则拒绝；若 R 拒绝，则接受"\begin{aligned} &S = "\text{对输入 } \langle M, \omega \rangle\\ &\qquad (1) \text{利用 } \langle M, \omega \rangle \text{ 来构造出上面方法（算法）所描述构造出的 } M_1\\ &\qquad (3) \text{对输入 } \langle M_1 \rangle \text{ 运行图灵机 } R\\ &\qquad (4) \text{如果 } R \text{ 接受，则拒绝；若 } R \text{ 拒绝，则接受}"\\ \end{aligned}

这样就证明了，若 RR 可以判定 ETM\text{E}_{\text{TM}} ，则 SS 也可以判定 ATM\text{A}_{\text{TM}} ，但由于 ATM\text{A}_{\text{TM}} 不可判定，所以矛盾。
因此 ETM\text{E}_{\text{TM}} 不可判定。

3. REGULARTM={⟨M⟩∣M 为图灵机且 L(M) 为一个正则语言}\text{REGULAR}_{\text{TM}} = \left\{ \langle M \rangle \mid M\text{ 为图灵机且 } L(M) \text{ 为一个正则语言} \right\} 不可判定

证明：反证法，假设上述语言可判定，设其其中一个判定器为 RR，则可以构建如下判定器 SS ：

S="对输入 ⟨M,ω⟩(1)首先构造如下图灵机 M1M1="对输入的字符串 x[1]若 x 是 0n1n 形式的，那么接受；[2]若 x 不具有上述形式，那么将 ω 输入 M ，若 M接受 ω 则接受。 "(2)将 ⟨M1⟩ 输入 R(3)如果 R 接受，则接受；若 R 拒绝，则拒绝"\begin{aligned} &S = \text{"对输入 } \langle M, \omega \rangle\\ &\qquad (1) \text{首先构造如下图灵机 } M_1\\ &\qquad M_1 = "\text{对输入的字符串 } x \\ &\qquad\qquad [1] \text{若 } x \text{ 是 } 0^n1^n \text{ 形式的，那么接受；}\\ &\qquad\qquad [2] \text{若 } x \text{ 不具有上述形式，那么将 } \omega \text{ 输入 } M \text{ ，若 } M \text{接受 } \omega \text{ 则接受。 } "\\ &\qquad (2) \text{将 } \langle M_1\rangle \text{ 输入 } R\\ &\qquad (3) \text{如果 } R \text{ 接受，则接受；若 } R \text{ 拒绝，则拒绝"}\\ \end{aligned}

上述机器利用了一个先验知识，即语言 {0n1n∣n⩾0}\left\{ 0^n1^n\mid n\geqslant 0 \right\} 是非正则的，且 {{0n1n∣n⩾0}M 不接受 ωΣ∗M 接受 ω\begin{cases}\left\{ 0^n1^n\mid n\geqslant 0 \right\} &M\text{ 不接受 }\omega\\\Sigma^*&M\text{ 接受 }\omega\end{cases}。从而根据上述构造，利用判定器 RR 可以推断出 L(M1)L(M_1) 是否为正则语言，也意味着能够判定 MM 能否接受 ω\omega ，即得 ATM\text{A}_{\text{TM}} 的判定器 SS，矛盾。 因此 REGULARTM\text{REGULAR}_{\text{TM}} 不可判定。

4. EQTM={⟨M1,M2⟩∣M1,M2 均为图灵机且 L(M1)=L(M2)}\text{EQ}_{\text{TM}} = \left\{ \langle M_1, M_2 \rangle \mid M_1, M_2 \text{ 均为图灵机且 } L(M_1) = L(M_2) \right\} 不可判定

证明：反证法，假设上述语言可判定，设其其中一个判定器为 RR，则可以构建如下判定器 SS ：

S="对输入 ⟨M,ω⟩(1)构造图灵机 M′，且 L(M′)=∅，即 M′ 拒绝一切输入(2)将 ⟨M,M′⟩ 输入 R(3)如果 R 接受，则接受；若 R 拒绝，则拒绝"\begin{aligned} &S = \text{"对输入 } \langle M, \omega \rangle\\ &\qquad (1) \text{构造图灵机 } M'\text{，且 } L(M')=\emptyset\text{，即 } M' \text{ 拒绝一切输入}\\ &\qquad (2) \text{将 } \langle M, M'\rangle \text{ 输入 } R\\ &\qquad (3) \text{如果 } R \text{ 接受，则接受；若 } R \text{ 拒绝，则拒绝"}\\ \end{aligned}

即得 ATM\text{A}_{\text{TM}} 的判定器 SS，矛盾。 因此 EQTM\text{EQ}_{\text{TM}} 不可判定。

2. 图灵可识别

证明 EQTM\text{EQ}_{\text{TM}} 不是图灵可识别的，也不是补图灵可识别的。

引理：A⩽mB  ⟺  A‾⩽mB‾A\leqslant_{m} B \iff \overline{A} \leqslant_m \overline{B}

引理的证明：若A⩽mBA\leqslant_m B，则即 ∃f:Σ∗→Σ∗\exists f:\Sigma^* \rightarrow \Sigma^*，

∀ω,ω∈A  ⟺  f(ω)∈B\forall\omega, \omega\in A\iff f(\omega)\in B

也就有

∀ω,ω∉A  ⟺  f(ω)∉B\forall\omega, \omega\not\in A\iff f(\omega)\not\in B

则：

A⩽mB⇒A‾⩽mB‾A\leqslant_m B\Rightarrow \overline{A}\leqslant_m \overline{B}

另一方面，将 A‾\overline{A} 和 B‾\overline{B} 分别作为上述的AA和BB 带入，则也得到：

A‾⩽mB‾⇒A⩽mB\overline{A}\leqslant_m \overline{B} \Rightarrow A\leqslant_m B

综上所述，A‾⩽mB‾  ⟺  A⩽mB\overline{A}\leqslant_m \overline{B} \iff A\leqslant_m B

原命题的证明：

【步骤一】将 ATM‾\overline{\text{A}_{\text{TM}}} 归约到 EQTM\text{EQ}_{\text{TM}} ，从而说明 EQTM\text{EQ}_{\text{TM}} 不是图灵可识别的。

构造可计算函数如下：

F="对输入 ⟨M,ω⟩(1)构造图灵机 ⟨M1,M2⟩ 其中：M1=对任何输入均拒绝M2=对任何输入，将 ω 输入 M，若 M接受这接受(2)输出 ⟨M1,M2⟩"\begin{aligned} &F = "\text{对输入 } \langle M, \omega\rangle\\ &\qquad (1) \text{构造图灵机 } \langle M_1, M_2 \rangle \text{ 其中：}\\ &\qquad\qquad M_1 = \text{对任何输入均拒绝}\\ &\qquad\qquad M_2 = \text{对任何输入，将 }\omega\text{ 输入 } M \text{，若 } M \text{接受这接受}\\ &\qquad (2) \text{输出 } \langle M_1, M_2 \rangle" \end{aligned}

这里的 F:Σ∗→Σ∗F:\Sigma^* \rightarrow \Sigma^* 是可计算的，且 ∀x=⟨M,ω⟩\forall x=\langle M, \omega\rangle，有 x∈ATM‾  ⟺  F(x)∈EQTMx\in\overline{\text{A}_{\text{TM}}} \iff F(x)\in\text{EQ}_{\text{TM}}，因此 ATM‾⩽mEQTM\overline{\text{A}_{\text{TM}}}\leqslant_m \text{EQ}_{\text{TM}}。

由 ATM‾\overline{\text{A}_{\text{TM}}} 不是图灵可识别的可知，EQTM\text{EQ}_{\text{TM}} 也不是图灵可识别的。

【步骤二】证明 EQTM‾\overline{\text{EQ}_{\text{TM}}} 也不是图灵可识别的。（利用 ATM⩽mEQTM  ⟺  ATM‾⩽mEQTM‾\text{A}_{\text{TM}} \leqslant_m \text{EQ}_{\text{TM}} \iff \overline{\text{A}_{\text{TM}}} \leqslant_m \overline{\text{EQ}_{\text{TM}}} ）

构造与【步骤一】类似的可计算函数 F′F'，其中F′F' 恰将 FF 中的 M1M_1 修改为 M1=对任何输入都接受M_1=\text{对任何输入都接受}，则有 F′F' 对 ∀x=⟨M,ω⟩\forall x=\langle M, \omega \rangle 有 x∈ATM  ⟺  F′(x)∈EQTMx\in \text{A}_{\text{TM}} \iff F'(x)\in \text{EQ}_{\text{TM}}。因此：

ATM⩽mEQTM\text{A}_{\text{TM}} \leqslant_m \text{EQ}_{\text{TM}}

利用引理，也就有：

ATM‾⩽mEQTM‾\overline{\text{A}_{\text{TM}}} \leqslant_m \overline{\text{EQ}_{\text{TM}}}

由于 ATM‾\overline{\text{A}_{\text{TM}}} 不是图灵可识别的，从而 EQTM‾\overline{\text{EQ}_{\text{TM}}} 也不是图灵可识别的。

【综上所述】命题得证。

 2025-01-11   计算复杂性  

上一篇  下一篇