用动物做logo的旅游网站,wordpress如何安装主题,线上推广的目的,宣传册设计与制作用什么软件文章目录 本章要点可归约性映射可归约图灵可判定归约证明 H A L T T M HALT_{TM} HALTTM不可判定 E T M E_{TM} ETM不可判定 R E G U L A R T M REGULAR_{TM} REGULARTM不可判定 E Q T M EQ_{TM} EQTM不可判定 图灵可识别的归约性参考 本章要点
可归约性定义#xff… 文章目录 本章要点可归约性映射可归约图灵可判定归约证明 H A L T T M HALT_{TM} HALTTM不可判定 E T M E_{TM} ETM不可判定 R E G U L A R T M REGULAR_{TM} REGULARTM不可判定 E Q T M EQ_{TM} EQTM不可判定 图灵可识别的归约性参考 本章要点
可归约性定义映射可归约若 A ≤ m B A\le_m B A≤mB且 A A A不可判定则 B B B也是不可判定证明 A ≤ m B A \le_m B A≤mB与 A ‾ ≤ m B ‾ \overline A \le_m \overline B A≤mB等价性证明 H A L T T M , E T M , R E G U L A R T M , E Q T M HALT_{TM}, E_{TM}, REGULAR_{TM}, EQ_{TM} HALTTM,ETM,REGULARTM,EQTM的归约 E Q T M EQ_{TM} EQTM和其补都不是图灵可识别的证明。
可归约性
在以图灵机为通用计算机的前提下可判定章节讨论了一些在图灵机上可解的问题并给出了一个图灵机不可解的实例 A T M A_{TM} ATM。
在可归约章节中将进一步给出其他图灵机不可解的实例并通过论证 A T M A_{TM} ATM可以归约到这些实例证明其不可解性。 简单来说就是 A T M A_{TM} ATM问题可以归约到 B B B问题可以使用 B B B问题构造出 A T M A_{TM} ATM的判定器如果 B B B问题可解可判定那么 A T M A_{TM} ATM也会可判定导致矛盾从而反证出 B B B不可判定。 映射可归约 和黑书顺序不同这里先把这个概念明确一下。 映射可归约是一种简单的从一个问题归约到另一个问题的方法。核心理念是通过一个可计算函数将问题 A A A转化为问题 B B B的实例然后解决问题 B B B。这种思想在时间复杂度、空间复杂度的完全性问题以及本章中将要讨论的几个不可解问题中有充分体现。
首先给出可计算函数的定义
定义称 f : Σ ∗ → Σ ∗ f: \Sigma^* \to \Sigma^* f:Σ∗→Σ∗是一个可计算函数如果 f f f对所有的输入 w w w都停机并且停机后只有 f ( w ) f(w) f(w)出现在带子上。
进而定义映射可归约性
定义如果存在可计算函数 f : Σ ∗ → Σ ∗ f:\Sigma^* \to \Sigma^* f:Σ∗→Σ∗对每个 w ∈ A w \in A w∈A都有 w ∈ A ⇔ f ( w ) ∈ B w \in A \Leftrightarrow f(w) \in B w∈A⇔f(w)∈B 则称语言 A A A映射可归约到语言 B B B记 A ≤ m B A \le_m B A≤mB称 f f f为 A A A到 B B B的归约。
定理如果 A ≤ m B A \le_m B A≤mB且 B B B是可判定的则 A A A也是可判定的。
证明已知 B B B可判定使用 B B B的判定器 M M M根据映射可归约的定义构造 A A A的判定器 N N N N “对输入 w : 1. 计算 f ( w ) ; 2. 在 f ( w ) 上运行 M 输出 M 的输出。” \begin{array}{l} N \text{“对输入}w:\\ 1.计算f(w);\\ 2.在f(w)上运行M输出M的输出。\text{”} \end{array} N“对输入w:1.计算f(w);2.在f(w)上运行M输出M的输出。” 推论若 A ≤ m B A\le_m B A≤mB且 A A A不可判定则 B B B也是不可判定的。
证明若 A ≤ m B A\le_m B A≤mB且 A A A不可判定假设 B B B可判定则根据定理可知 A A A应该是可判定的矛盾故 B B B应该是不可判定的。 该推论是证明问题不可判定的常用工具。 由于映射可归约是一种简单的归约方法故不是所有的归约都属于映射可归约对于难以找到可计算函数的归约问题可能采用的就不是映射可归约。事实上下文可判定归约证明中就有不是映射可归约证明的。 图灵可判定归约证明 图灵可归约的证明通常基于构造已经得证的不可判定图灵机进行例如构造若B成立则可由B规约 A T M A_{TM} ATM因为 A T M A_{TM} ATM不可判定所以B不成立。 H A L T T M HALT_{TM} HALTTM不可判定
给出 H A L T T M HALT_{TM} HALTTM的定义并回顾下 A T M A_{TM} ATM的定义 H A L T T M { M , w ∣ M 为图灵机对输入 w 停机 } A T M { M , w ∣ M 为图灵机 M 接受 w } HALT_{TM} \{M, w| M为图灵机对输入w停机\}\\ A_{TM} \{M, w | M为图灵机M接受w\} HALTTM{M,w∣M为图灵机对输入w停机}ATM{M,w∣M为图灵机M接受w} 证明思路 A T M A_{TM} ATM对 M M M拒绝和循环的输出都是拒绝因此首先使用 H A L T T M HALT_{TM} HALTTM的判定器判定是否停机不停机就拒绝然后再在 w w w上模拟 M M M。
证明假设 H A L T T M HALT_{TM} HALTTM是可判定的使用 H A L T T M HALT_{TM} HALTTM归约 A T M A_{TM} ATM设判定 H A L T T M HALT_{TM} HALTTM的图灵机为 R R R构造判定 A T M A_{TM} ATM的图灵机 S S S S “对输入 M , w : 1. 在输入 M , w 上运行 R ; 2. 若 R 拒绝则拒绝 ; 3. 若 R 接受在 w 上运行 M 直到停机 ; 4. 若 M 接受则接受若 M 拒绝则拒绝。” \begin{array}{l} S \text{“对输入}M, w:\\ 1.在输入M,w上运行R;\\ 2.若R拒绝则拒绝;\\ 3.若R接受在w上运行M直到停机;\\ 4.若M接受则接受若M拒绝则拒绝。\text{”} \end{array} S“对输入M,w:1.在输入M,w上运行R;2.若R拒绝则拒绝;3.若R接受在w上运行M直到停机;4.若M接受则接受若M拒绝则拒绝。” 从上面的构造可以看出若 R R R可判定 H A L T T M HALT_{TM} HALTTM则 S S S可判定 A T M A_{TM} ATM因为 A T M A_{TM} ATM是不可判定的故 H A L T T M HALT_{TM} HALTTM也应该是不可判定的。 E T M E_{TM} ETM不可判定
给出 E T M E_{TM} ETM的定义 E T M { M ∣ M 为图灵机 L ( M ) ∅ } E_{TM} \{M | M为图灵机L(M) \varnothing\} ETM{M∣M为图灵机L(M)∅} 证明思路仍然需要构造 A T M A_{TM} ATM的判定器但 E T M E_{TM} ETM与 A T M A_{TM} ATM的联系性是比较难想的。这个联系等价于找到 ∅ \varnothing ∅与 w w w的关系即如果 M M M接受/不接受 w w w应该推导出 ∅ \varnothing ∅。
可以根据 M M M和 w w w的描述尝试构造这样一台新的图灵机 M 1 M_1 M1 M 1 “对输入 x : 1. 若 x ≠ w , 则拒绝 ; 2. 若 x w , 则在 w 上模拟 M 若 M 接受则接受。” \begin{array}{l} M_1 \text{“对输入}x:\\ 1.若x\ne w, 则拒绝;\\ 2.若x w, 则在w上模拟M若M接受则接受。\text{”} \end{array} M1“对输入x:1.若xw,则拒绝;2.若xw,则在w上模拟M若M接受则接受。” 图灵机 M 1 M_1 M1唯一能够识别的串就是 w w w当且仅当 x w x w xw时 L ( M 1 ) ≠ ∅ L(M_1) \ne \varnothing L(M1)∅。如果 E T M E_{TM} ETM是可判定的就可以通过判定 M 1 M_1 M1的语言是否为 ∅ \varnothing ∅得知 M M M是否接受 w w w。设 E T M E_{TM} ETM的判定器为 R R R如果 R R R接受则意味着 L ( M 1 ) ∅ L(M_1) \varnothing L(M1)∅即 M M M不接受 w w w反之则意味着 M M M接受 w w w。
证明假设 E T M E_{TM} ETM是可判定的设其判定器为 R R R构造判定 A T M A_{TM} ATM的判定器 S S S S 对输入 M , w : 1. 使用 M 和 w 的描述构造只接受 w 的图灵机 M 1 ; 2. 使用 R 判定 M 1 ; 3. 若 R 接受则拒绝若 R 拒绝则接受。” \begin{array}{l} S \text{对输入}M, w:\\ 1.使用M和w的描述构造只接受w的图灵机M_1;\\ 2.使用R判定M_1;\\ 3.若R接受则拒绝若R拒绝则接受。\text{”} \end{array} S对输入M,w:1.使用M和w的描述构造只接受w的图灵机M1;2.使用R判定M1;3.若R接受则拒绝若R拒绝则接受。” 从上面的构造可以看出若 R R R可以判定 E T M E_{TM} ETM则 S S S可以判定 A T M A_{TM} ATM由于 A T M A_{TM} ATM是不可判定的故 E T M E_{TM} ETM也应该是不可判定的。 R E G U L A R T M REGULAR_{TM} REGULARTM不可判定
给出 R E G U L A R T M REGULAR_{TM} REGULARTM的定义 R E G U L A R T M { M ∣ M 为图灵机且 L ( M ) 为正则语言 } REGULAR_{TM} \{M| M为图灵机且L(M)为正则语言\} REGULARTM{M∣M为图灵机且L(M)为正则语言} 证明思路与 E T M E_{TM} ETM的思路类似我们需要找到判定正则语言与判定接受 w w w之间的联系即如果 M M M接受 w w w则 L ( M ) L(M) L(M)为正则语言如果 M M M不接受 w w w则 L ( M ) L(M) L(M)为非正则语言。构造图灵机 M 2 M_2 M2来描述这种关系设字母表为 { 0 , 1 } \{0,1\} {0,1} M 2 “对输入 x : 1. 若 x 具有形式 0 n 1 n 则接受此时 M 2 的语言为非正则 ; 2. 若 x 具有形式 Σ ∗ 则在 w 上运行 M 。若 M 接受 w 则接受。此时 M 2 的语言是正则语言。” \begin{array}{l} M_2 \text{“对输入}x:\\ 1.若x具有形式0^n1^n则接受此时M_2的语言为非正则;\\ 2.若x具有形式\Sigma^*则在w上运行M。若M接受w则接受。此时M_2的语言是正则语言。\text{”} \end{array} M2“对输入x:1.若x具有形式0n1n则接受此时M2的语言为非正则;2.若x具有形式Σ∗则在w上运行M。若M接受w则接受。此时M2的语言是正则语言。” 证明假设 R E G U L A R T M REGULAR_{TM} REGULARTM可判定且判定器为 R R R构造判定 A T M A_{TM} ATM的判定器 S S S S 对输入 M , w : 1. 使用 M 和 w 构造上述的图灵机 M 2 ; 2. 在输入 M 2 上运行 R ; 3. 若 R 接受则接受若 R 拒绝则拒绝。 \begin{array}{l} S \text{对输入}M, w:\\ 1.使用M和w构造上述的图灵机M_2;\\ 2.在输入M_2上运行R;\\ 3.若R接受则接受若R拒绝则拒绝。\ \end{array} S对输入M,w:1.使用M和w构造上述的图灵机M2;2.在输入M2上运行R;3.若R接受则接受若R拒绝则拒绝。 从上述构造中可以看出如果 R R R可以判定 R E G U L A R T M REGULAR_{TM} REGULARTM则 S S S可以判定 A T M A_{TM} ATM由于 A T M A_{TM} ATM不可判定故 R E G U L A R T M REGULAR_{TM} REGULARTM应该是不可判定的。 在 M 2 M_2 M2的构造中 x x x的形式没有固定要求只要一个是正则一个是非正则就好因为重点不是 M 2 M_2 M2识别的语言具体是什么而是能否用判定器 R R R判定 M 2 M_2 M2的语言是不是正则语言。 E Q T M EQ_{TM} EQTM不可判定
给出 E Q T M EQ_{TM} EQTM的定义 E Q T M { M 1 , M 2 ∣ M 1 , M 2 都是图灵机且 L ( M 1 ) L ( M 2 ) } EQ_{TM} \{M_1, M_2|M_1, M_2都是图灵机且L(M_1) L(M_2)\} EQTM{M1,M2∣M1,M2都是图灵机且L(M1)L(M2)} 证明思路 E Q T M EQ_{TM} EQTM利用 E T M E_{TM} ETM来进行构造同样是要寻找两者之间的联系令 L ( M 1 ) ∅ L(M_1) \varnothing L(M1)∅若 E Q ( M 1 , M 2 ) EQ(M_1, M_2) EQ(M1,M2)则 M 2 M_2 M2的语言也应该是空的。
证明假设 E Q T M EQ_{TM} EQTM可判定设判定器为 R R R构造判定 E T M E_{TM} ETM的判定器 S S S S 对输入 M : 1. 在输入 M , M 1 上运行 R M 1 为拒绝所有输入的图灵机即 L ( M 1 ) ∅ 2. 如果 R 接受则接受如果 R 拒绝则拒绝。” \begin{array}{l} S \text{对输入}M:\\ 1.在输入M, M_1上运行RM_1为拒绝所有输入的图灵机即L(M_1) \varnothing\\ 2.如果R接受则接受如果R拒绝则拒绝。\text{”} \end{array} S对输入M:1.在输入M,M1上运行RM1为拒绝所有输入的图灵机即L(M1)∅2.如果R接受则接受如果R拒绝则拒绝。” 从上述构造中可以看出如果 R R R可以判定 E Q T M EQ_{TM} EQTM则 S S S可以判定 E T M E_{TM} ETM因为 E T M E_{TM} ETM不可判定故 E Q T M EQ_{TM} EQTM也是不可判定的。
图灵可识别的归约性
映射可归约性对求补运算是敏感的在可判定章节我们提到了补图灵可识别的概念这里对其归约性进行说明。
首先给出图灵可识别的归约定理形式上非常类似映射可归约一节中可判定性的归约定理
定理如果 A ≤ m B A \le_m B A≤mB且 B B B是图灵可识别的的则 A A A也是图灵可识别的。
只需要将上文中证明的判定器改为识别器就可以证明该定理。推论同理
推论若 A ≤ m B A\le_m B A≤mB且 A A A不可识别则 B B B也是不可识别的。
推论 A ≤ m B A \le_m B A≤mB与 A ‾ ≤ m B ‾ \overline A \le_m \overline B A≤mB具有相同含义。
证明已知 A ≤ m B A \le_m B A≤mB则有对应关系 ∀ w ∈ A ⇔ ∀ f ( w ) ∈ B \forall\ w \in A \Leftrightarrow \forall\ f(w) \in B ∀ w∈A⇔∀ f(w)∈B 若 ∃ w ∈ A ‾ \exist\ w \in \overline A ∃ w∈A使得 f ( w ) ∉ B f(w) \notin B f(w)∈/B则意味着该 f ( w ) ∈ B ⇔ w ∈ A f(w) \in B \Leftrightarrow w \in A f(w)∈B⇔w∈A导致矛盾。
故 ∀ w ∈ A ‾ \forall\ w \in \overline A ∀ w∈A都应有 f ( w ) ∈ B ‾ f(w) \in \overline B f(w)∈B。 这个证明记一下可能会考。 上述定理在证明可识别性归约问题有典型的应用因为 A T M ‾ \overline {A_{TM}} ATM不是图灵可识别的因此如果想要证明 B B B不是图灵可识别的可以证明 A T M ≤ m B ‾ A_{TM} \le_m \overline B ATM≤mB就相当于证明 A T M ‾ ≤ m B \overline {A_{TM}} \le_m B ATM≤mB。
定理 E Q T M EQ_{TM} EQTM既不是图灵可识别的也不是补图灵可识别的。
证明 首先证明 E Q T M EQ_{TM} EQTM不可识别给出从 A T M A_{TM} ATM到 E Q T M ‾ \overline {EQ_{TM}} EQTM的归约 F “对输入 M , w , M 为图灵机 w 为串 : 1. 构造图灵机 M 1 , M 2 M 1 “对任何输入 : a . 拒绝。” M 2 “对任何输入 : a . 在 w 上运行 M 若 M 接受则接受。” 2. 输出 M 1 , M 2 。” \begin{array}{l} F \text{“对输入}M, w, M为图灵机w为串:\\ 1.构造图灵机M_1, M_2\\ M_1 \text{“对任何输入}:\\ \ \ \ \ a.拒绝。\text{”}\\ M_2 \text{“对任何输入}:\\ \ \ \ \ a.在w上运行M若M接受则接受。\text{”}\\ 2.输出M_1, M_2。\text{”} \end{array} F“对输入M,w,M为图灵机w为串:1.构造图灵机M1,M2M1“对任何输入: a.拒绝。”M2“对任何输入: a.在w上运行M若M接受则接受。”2.输出M1,M2。” 由于 M 1 M_1 M1什么也不接受若 M M M接受 w w w则 M 2 M_2 M2接受两个机器不等价反之如果 M M M不接受 w w w则两个机器等价。因为 A T M ‾ \overline {A_{TM}} ATM不是图灵可识别的且 A T M ≤ m E Q T M ‾ ⇔ A T M ‾ ≤ m E Q T M A_{TM} \le_m \overline {EQ_{TM}} \Leftrightarrow\overline {A_{TM}} \le_m EQ_{TM} ATM≤mEQTM⇔ATM≤mEQTM故 E Q T M EQ_{TM} EQTM不是可识别的。 同理只需将 M 1 M_1 M1的描述改为对任何输入都接受可以得到 A T M A_{TM} ATM到 E Q T M EQ_{TM} EQTM的归约从而证明补图灵不可识别。
参考
《计算理论导引》第二版机械工业出版社
