计算理论 第5章 可归约性.

Presentation on theme: "计算理论 第5章 可归约性."— Presentation transcript:

1 计算理论 第5章 可归约性

2 前言 归约旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。
在第4章已经确定采用图灵机作为通用计算器机的模型，并介绍了几个在图灵机上可解的问题，还给出了一个计算机不可解的问题 ，即ATM。本章讨论另外几个不可解的问题 。在讨论过程 中，将介绍一个基本方法，可用来证明问题是计算上不可解的，这个方法称为可归约性。 归约旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。

3 前言 例如，在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。
可归约性总是涉及两个问题，称之为A和B。如果A可归约到B，就可用B的解来解A。在上述例子中，A是城市认路问题，B是得到地图问题。注意，可归约性说的不是怎样去解A或B，而是在知道B的解时怎么去解A。

4 主要内容 5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 5.3.1 可计算函数
5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 可计算函数 映射可归约性的形式定义

5 语言理论中的不可判定问题 ATM是不可判定的，即确定个图灵机是否接受一个给定的输入问题是不可判定的。
下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定输入是否停机（通过接受或拒绝）问题。若将ATM归约到HALTTM，就可以利用ATM的不可判定性证明HALTTM的不可判定性。设: HALTTM={<M, w>| M是一个TM, 且对输入w停机}

6 反证法，假设可判定，证明ATM是可判定的。
语言理论中的不可判定问题 反证法，假设可判定，证明ATM是可判定的。 定理 5.1 HALTTM是不可判定的。 为得到矛盾，假设TM R判定HALTTM，由之可以构造TM S来判定 ATM, 其构造如下： S=“在输入<M，w >上，此处<M，w >是TM M和串w 的编码： 1) 在输入<M，w >上运行TM R。 2)如果R拒绝，则拒绝。 3)如果R接受，则在w 上模拟M，直到它停机。 4)如果M已经接受，则接受；如果M已经拒绝，则拒绝。 显然，如果R判定HALTTM，则S判定ATM。因为ATM是不可判定的， 故HALTTM也必定是不可判定的。

7 反证法，假设可判定，证明ATM是可判定的。
语言理论中的不可判定问题 反证法，假设可判定，证明ATM是可判定的。 定理 5.2 ETM 是不可判定的。 除w外M1拒绝所有串 先用标准术语来写在证明思路中描述的那上修改型机器M1. M1=“在输入x上： 1)如果x≠w，则拒绝。 2)如果x=w，则在x上运行M，当M接受时，就接受。” 这个机器以w作为它的描述的一部分。检查x=w是否成立的方法很 显然， 即扫描输入并用一个字符一个字符地将它与w进行比较，就可确定它们 是否相同。

8 语言理论中的不可判定问题 再假设TM R判定ETM。如下构造判定ATM的TM S:
S=“在输入<M，w >上，此处<M，w >是TM M和串w的编码： 1) 用M和w的描述来构造上述TM M1。 2)在输入< M1 >上运行R。 3)如果R接受，则拒绝；如果R拒绝，则接受。” 不空，M接受w 说明L(M1)是空集，因此M1不接受w

9 语言理论中的不可判定问题 另一个与图灵机有关的计算问题也很有意思，该问题是： 给定一个图灵机和一个可由某个更简单的计算模型识别的
语言，测定此图灵机是否识别此语言。 例如：令REGULARTM是测定一个给定的图机是否有一个与 之等价的有穷自动机问题，则这个问题与测定一个给定的图 灵机是否识别一个与此正则语言的问题相同。设： REGULARTM={<M>| M是一个TM，且L(M)是一个正则语言}

10 语言理论中的不可判定问题 定理 5.3 设R是判定REGULARTM 的一个TM，下面构造判定ATM的TM S。 S的运行方式如下：
S=“对于输入<M，w>，其中M是TM，w是串： 1)构造下述TM M2： M2=“在输入x上： a) 如果x具有形式0n1n，则接受。 b)如果x不具有此形式，则在输入w上运行M。如果M接受w，则接受。” 2)在输入<M2>上运行R。 3) 如果R接受，则接受；如果R拒绝，则拒绝。”

11 语言理论中的不可判定问题 定理 EQTM是不可判定的。 5.4 设TM R判定EQTM。如下构造判定ETM 的TM S：
S=“对于输入<M>，其中M是TM： 1)在输入<M，M1>上运行R，其中M1是拒绝所有输入的图 灵机。 2)如果R接受，则接受；如果R拒绝，则拒绝。 如果R判定EQTM，则S判定ETM。但由定理5.2，ETM是不可 判定的，故EQTM也是不可判定的。

12 语言理论中的不可判定问题 定义 接受计算历史是一个格局序列C1，C2，．．．,Cl， 5.5
设M是一个图灵机，w是一个串。M在w上的一个 接受计算历史是一个格局序列C1，C2，．．．,Cl， 其中C1是M在w上的起始格局，Cl是M的一个接受 格局，且每个Ci都是Ci-1的合法结果，即符合M的 规则。M在w上的一拒绝计算历史可类似定义，只是 Cl应是一个拒绝格局。 定义 5.5

13 语言理论中的不可判定问题 线性界限自动机是一种受到限制的图灵机，它不允 定义 定义 许其读写头离开包含输入的带区域。如果此机器 5.6
试图将它的读写头移出输入的两个端点，则读写 头就保持在原地不动。这与普通图灵机的读写头 不会离开带子的左端点的方式一样。 定义 5.6 定义 5.6 a b 控制器

14 语言理论中的不可判定问题 设M是有q个状态和g个带符号的LBA。对于长度为 引理 定义 n的带子，M恰有qngn个不同的格局。 5.6
5.7 定义 5.6 M的格局就像计算中间的一快照。格局由控制状态、读写 头位置和带内容组成。这里，M有q个状态。它的带长度是 n，所以读写头可能处于n个位置之一，且gn多个带符号串 可能出现在带上。此三个量的乘积就是带长为n的M的格局 总数。

15 语言理论中的不可判定问题 定理 定义 ALBA是可判定的。 5.6 5.8 证明 判定ALBA的算法如下：
L=“对于输入<M，w >，其中M是LBA，w 是串： 1)在w 上模拟M qngn步，或者直到它停机。 2)如果M停机，则当它接受时接受，拒绝时拒绝。如果它还没 有停机，就拒绝。” 如果M在w 上运行qngn步还没有停机，根据引理5.7，它必定 在重复某个格局，即陷入了循环。这就是算法为什么在此情 形下拒绝的原因。

16 语言理论中的不可判定问题 定理 定义 ELBA是不可判定的。 5.9 5.6 现在构造从ATM到ELBA的归约。假设TM R判定ELBA。
# … C1 C2 C3 Cl 现在构造从ATM到ELBA的归约。假设TM R判定ELBA。 如下构造判定ATM的TM S： S=“对于输入<M，w >，其中M是TM，w 是串： 1) 如在证明思路中所描述的那样从M和w 构造LBA B。 2) 在输入<B >上运行R。 3) 如果R拒绝，则接受；如果R接受，则拒绝。”

17 语言理论中的不可判定问题 如果R接受<B >，则L(B)= 。这样，M在w 上就没接受计算
历史，M也就不接受w. 因此，S也就拒绝<M，w >。类似地， 如果R拒绝<B>，则B的语言不空。B能够接受的唯一串是M在 w 上的接受计算历史。这样，M必定接受w 。相应地，S也就 接受<M，w >。下图是检查这样一个TM计算历史的示意图。 q3 a b # x q5 … B Ci Ci+1

18 语言理论中的不可判定问题 使用利用计算历史的归约技术，还能建立有关上下文无关文 法和下推自动机问题的不可判定性。加快一下，定理4.7介绍
了一个算法来判定一个上下文无关文法是否派生串，即判定 L(G)= 是否成立。与此相关，现在要证明问题“测定一个上 下文无关文法是否派生所有可能的串”是不可判定的。证明这 个问题不可判定是证明上下文无关文法等价性问题不可判定 的重要步骤。设: ALLCFG={<G >| G是 一个CFG且L(G)= *}

19 语言理论中的不可判定问题 定理 5.10 定义 5.6 ALLCFG是不可判定的。
明ATM是可判定的。其证明与定理5.9的证明类似，只是稍微复杂一些， 绕了一点点弯。这是一个从ATM出发利用计算历史的归约。 但由于技术 上的原因，对计算历史的表示做了些修改，后面将解释这样做的原因。 现在来描述怎样运用ALLCFG的判定过程来判定ATM。对于TM M和 输入串w，首先构造一个CFG G ，使得它派生所有串当且仅当M不接受w 。所以，如果M接受w，则存在一个特别的串，G不派生它。这个串应该 是M在w上的计算历史。即：设计G ，使之派生所有不是M在w上接受计算 历史的串。

20 语言理论中的不可判定问题 为了使得CFG G派生所有不是M在w上接受计算历史的串，采用下的策略。
一个串不能成为M在w上的接受计算历史的原因可能有多个。将M在w上的 接受计算历史表示成#C1 #C2#...#Cl# ，其中Ci是M在w上计算的第i步的格 局。然后G派生出满足下述条件的所有串： 1) 不以Cl开始。 2) 不以一个接受格局结束 3) 在M的规则下，某个Ci不恰好派生Ci+1。 如果M不接受w，就没有接受计算历史存在，故所有串都因为这样或那样的 问题而不能成为接受计算历史，因此G将派生所有串，这正是所希望的。

21 语言理论中的不可判定问题 这个思路存在的问题是：当D将Ci弹出栈时，它处于相反的左右
种方法来写接受计算历史，使得每隔一个格局就以相反的顺序出 现。奇数位置保持以向前的顺序写，但偶数位置向后写。这种形 式的一个接受计算历史如下图所示： # … C1 C2R C3 C4R Cl

22 主要内容 5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 5.3.1 可计算函数
5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 可计算函数 映射可归约性的形式定义

23 一个简单的不可判定问题 本节将证明：不可判定性现象不仅能仅能局限于有限自动机的问题，我们将
给出一个关于串操作的不可判定问题，称为波斯特对应问题。 可以很容易地将这个问题描述成一种游戏，多米诺骨牌。每个骨牌由两个串 构成，一边一个，单个骨牌看上去像 一簇骨牌看起来像 任务是将这些骨牌进行排列(允许重复)，使得在总计顶部符号后得到的串 与总计询问符号后得到的串相同。这样的排列称为一个匹配。例如，下面 的排列就是这个游戏的一个匹配。 a ab b ca a ab abc c ,

24 一个简单的不可判定问题 阅读顶部后得到的串abcaaabc，与总计询问后得到的本同。可以
将骨牌变形使得和询问对应符号整齐地排列，以此更容易表示匹 配。 a b c

25 一个简单的不可判定问题 不可能包含匹配，因为顶部的每个串都比询问对应 的串长。 波斯特对应问题是：确定一簇骨牌是否有一个匹配。这个问
对某些骨牌簇，不可能找到这样的匹配。例如，簇 不可能包含匹配，因为顶部的每个串都比询问对应 的串长。 波斯特对应问题是：确定一簇骨牌是否有一个匹配。这个问 题在算法上是不可解的。 abc ab ca c acc ba ,

26 一个简单的不可判定问题 在形式描述这个问题和给出它的证明之前，先来精确地描述这个 问题，然后表示成一个。骨牌簇P是pcp的一个实例：
匹配是一个序列i1，i2，．．．，il，使ti1ti2．．．til=bi1bi2bil. 问题是确定P是否有匹配。 令PCP={<G >| P是波斯特对应问题的一个实例，且P有匹配} t1 b1 t2 b2 tk bk , P = …

27 一个简单的不可判定问题 定理 5.11 定义 5.6 PCP是不可判定的。 假设TM R判定 PCP。构造S来判定ATM。令
M=(Q, , , , q0, qaccept, qreject) 其中Q, , , 分别是M的状态集、输入字母表、带字母表和 转移函数。 S构造PCP的一个实例P，使得P有一个匹配当且仅当M接受w。 为此，S首先构造MPCP 的一个实例P’。下面以七个部分来描述 这个构造。每个部分完成在w上模拟M的一个特定方面。在构造 过程中，为了解释我们正在做什么，用一个例子插在构造中。

28 一个简单的不可判定问题 第1部分：构造以下方式开始： 将 放入p’作为第一张骨牌
因为P’是MPCP的一个实例，故匹配必须以这张骨牌开始。底部串以M在w 上接受计算历史中的第一个格局C1= q0w1w2．．．wn开始。 如图所示: # #q0w1w2…wn# t1 b1 # … q0 w1 w2 wn

29 一个简单的不可判定问题 ＃q0w1w2．．．wn＃构成，顶部串只有#。为获得匹配，盘面 扩展串来匹配询问串。用新骨牌来作这样的扩展。这些新的
到目前为止，只得到一个部分匹配，其询问串由C1= ＃q0w1w2．．．wn＃构成，顶部串只有#。为获得匹配，盘面 扩展串来匹配询问串。用新骨牌来作这样的扩展。这些新的 骨牌强迫模拟M的一次单步运行，使得M的一下个格局出现 在询问串的扩展中。 第2、3、4部分在P’中增加的骨牌在模拟中起主要作用。第2 部分处理读写向右运动，第3部分处理读写头向左运动，第4 部分处理不与读写关相邻的带方格。

30 一个简单的不可判定问题 第2部分 ：对于第一个a,b∈和q,r ∈Q，其中q≠qreject，如果
(q,a)=(r,b,R),则将 放入P’中。 第3部分 ：对于第一个a,b,c∈和q,r ∈Q，其中q≠qreject，如果 (q,a)=(r,b,L)，则将 放入p’中。 第4部分 ：对于每一个a ∈，将 放入p’中。 这样，第2、3和4部分的骨牌，使得我们能够通过“在第一个格局 之后增加第二个格局”的方法来扩展匹配。希望这个过程能够继续 下去，即增加第三个格局，然后第四个格局，等等。为此，需要 增加一个新的骨牌来复制符号#。 qa br cqa rcb a

31 一个简单的不可判定问题 第5部分 ：将 和 放入P’中 接着上面的例子。假设在状态q7且读1时，M进入状q5，在带上
写下0，并将读写头向右移到。即(q7,1)=(q5,0,R)。则在P’中有 骨牌 最后的那个匹配被扩展到 # # _# q71 0q5 2 q5 # q7 1 …

32 一个简单的不可判定问题 再假设在状态q5且读0时，M进入状态q9，在带上写下2，并将它
的读写头向左移动。故(q5,1)=(q9,2,L)。则有骨牌 第一个骨牌与本构造部分有关，因为读写头左边的符号是0。前 面的部分匹配就被扩展成 0q50 q902 1q50 q912 2q50 q922 _q50 q9_2 , 和 2 q9 # q5 …

33 一个简单的不可判定问题 注意，构造匹配就是在w上模拟M，这个过程要一直进行到M到 达停机状态。如果出现了接受状态，希望这个部分匹配的顶部
“赶上”底部，从而使得这个匹配得以完成。为此，再增加加下骨 牌。 第6部分 ：对于第一个a ∈，将 和 放入P’中 这个步骤的效果是：在图灵机停机后增加一些“伪步骤”。这里， 读写头“吃掉”一些邻近的符号直到没有符号剩下。再继续前面 的例子，假设到机器以接受状态停机的地方为止的部分匹配是 aqaccept qaccept qaccepta qaccept

34 一个简单的不可判定问题 # … 2 1 qaccept 刚才增加的骨牌允许匹配如下继续进行： 2 1 qaccept # …

35 一个简单的不可判定问题 第7部分： 最的增加如下骨牌 来完成匹配： # #q0w1w2…wn# # qaccept …

36 一个简单的不可判定问题 * 设u=u1u2…un是一个长串为n的串。定义如下三个串：
★ u = * u1 u2 u3 … un 为将p’转换为PCP的一个实例P，做下面的事情：如果P’是如下 的簇: t1 b1 t2 b2 tk bk , … t3 b3

37 一个简单的不可判定问题 * 就令P是如下的簇 此时若再将P看PCP的实例，就可以看到，可能形成匹配的唯一的 骨牌是第一个骨牌 ★t1
★ b1 ★ ★ t1 b1 ★ ★ t3 b3 ★ , … ★ t2 b2 ★ ★ tk bk ★ ◇ * 此时若再将P看PCP的实例，就可以看到，可能形成匹配的唯一的 骨牌是第一个骨牌 ★t1 ★ b1 ★

38 一个简单的不可判定问题 * 因为它是顶部和底部以相同符号，即*，开始的唯一的骨牌。除
了强迫匹配以第一个骨牌开始以外，*的使用并不影响可能的匹 配，因为它们被原来的符号相互隔开，原来的符号现在出现在匹 配的偶数们。骨牌 是用来让顶部在匹配的最后再增加一个*。 ◇ *

39 主要内容 5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 5.3.1 可计算函数
5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 可计算函数 映射可归约性的形式定义

40 §5.3 映射可归约性 使用规约技术可以证明各种问题的不可判定性。本节将规约性概念形式化，这样就能更精确地使用它。
§5.3 映射可归约性 使用规约技术可以证明各种问题的不可判定性。本节将规约性概念形式化，这样就能更精确地使用它。 将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方式要根据具体应用情况。我们的选择是一种简单方式的可归约性，叫做映射可归约性。 粗略地说，“用映射可归约性将问题A归约为问题B”是指，存在一个可计算函数，它将问题A的实例转换成问题B的实例。 如果有了这样一个转换函数，就能用B的解决方案来解A 。原是，A 的任何一个实例可以这样来解：首先用这个归约将A转换为B的一个实例，然后应用B的解决方案。

41 §5.3 映射可归约性 图灵机计算函数的方式是：将函数的输入放在带子上，开始运行，并以停机后的带子作为函数的输出。
§5.3 映射可归约性 图灵机计算函数的方式是：将函数的输入放在带子上，开始运行，并以停机后的带子作为函数的输出。 函数f： * * 是一个可计算函数，如果有图灵机 M，使得在每个输入w上 停机，且此时只有f(w)出 现在带上。 定义 5.12 定义 5.6 例5.13 整数上所有通常的算术运算都是可计算函数。 例如，可以制造一个机器，它以<m,n>为输入且返回 m与n的和m+m。

42 §5.3 映射可归约性 例5.14可计算函数可以是机器的描述之间的变换。例如， 如果w=<M>是图灵机的编码，可以有一个可计算函
§5.3 映射可归约性 例5.14可计算函数可以是机器的描述之间的变换。例如， 如果w=<M>是图灵机的编码，可以有一个可计算函 数f，以w为输入，且返回一个图灵机的描述<M > 。 M是一个与M识别相同语言的机器。函数f通过在M 的描述中加入一些状态来完成这个任务。如果 M不 是图灵机的合法编码，f就返回

43 §5.3 映射可归约性 语言A是映射可归约到语言B的，如果存在可计算函 定义 定义 数 f： **使得对每个w， 5.15 5.6
§5.3 映射可归约性 语言A是映射可归约到语言B的，如果存在可计算函 数 f： **使得对每个w， w∈A等价于f(w) ∈B 记作A≤mB。称函数f为A到B的归约。 定义 5.15 定义 5.6 A到B的映射规约提供了将A的成员测试问题转化为B的成员测试问题的方法。为了检查是否有w属于A，可使这个规约f，将w映射到f(w)，然后检查是否f(w)属于B。如果一个问题映射可规约到第二个问题，且第二个问题先前已被解决，那就能得到原来问题的解 A B f

44 §5.3 映射可归约性 证明：设M是B的判定器，f是从A到B的归约。A的判定器N 的描述如下： N=“对于输入w： 1) 计算f(w)。
§5.3 映射可归约性 定理 5.16 定义 5.6 如果A≤mB且B是可判定的，则A也是可判定的。 证明：设M是B的判定器，f是从A到B的归约。A的判定器N 的描述如下： N=“对于输入w： 1) 计算f(w)。 2) 在f(w)上运行M，输出M的输出。” 显然，如果w∈A，则f(w) ∈B，因为f 是从A到B的归约。因此，只要w∈A，则M 接受f(w)。故N的运行正如所求。

45 §5.3 映射可归约性 推论 定义 5.17 5.6 如果A≤mB且A是不可判定的，则B也是不可判定的。
§5.3 映射可归约性 推论 5.17 定义 5.6 如果A≤mB且A是不可判定的，则B也是不可判定的。 例 定理5.1使用从ATM出发的一个规约，证明了HALTTM是不可判定的。这个归约说明了怎么用HALTTM的判定器给出ATM的判定器。以下展示从ATM到HALTTM的映射可归约性，为此必须提供一个可计算函数f，它使用形如<M，w >的输入，返回形如<M  ，w  >的输出，使得 <M，w> ∈ ATM当且仅当<M  ，w  >∈HALTTM

46 §5.3 映射可归约性 下面的机器F计算了归约f: F=“对于输入<M，w>： 1) 构造下面图灵机M’。 M’=“对于输入x：
§5.3 映射可归约性 下面的机器F计算了归约f: F=“对于输入<M，w>： 1) 构造下面图灵机M’。 M’=“对于输入x： a.在x上运行M。 b.如果M接受，则接受。 c.如果M拒绝，则进入循环。 2) 输出<M’，w’ >。”

47 §5.3 映射可归约性 例 定理5.11中的波斯特对应问题是不可判定的，其证明中包含了两个映射归约。它首先证明了ATM≤mMPCP，然后又证明了MPCP≤m PCP。对于两种情形，都能容易地得到实际的归约函数，且能容易地证明它们是映射归约。 例 在定理5.4的证明中，隐含了一个从ETM到EQTM的映射归约。此归约f将输入<M >映射到输出<M，M1>,其中M1是拒绝所有输入的机器。

48 §5.3 映射可归约性 例 本节定义了映射可归约性的形式概念，本章的前面部分所使用的可归约性都是非形式概念。定理5.2证明ETM是不可判定的，这个证明说明了映射可归约性的形式概念与非形式概念之间的差别。ETM的不可判定性是通过将ATM归约到它来证明的。现在来看看能否将这个归约转化为映射归约。

49 §5.3 映射可归约性 证明与5.16类似，只是将M和N改为识别器。 如果A≤mB，且B是可图灵可识别的，则A也是图灵 定理 可识别的。
§5.3 映射可归约性 如果A≤mB，且B是可图灵可识别的，则A也是图灵 可识别的。 定理 5.22 证明与5.16类似，只是将M和N改为识别器。 推论 5.23 如果A≤mB，且A不是图灵可识别的，则B也不是图 灵可识别的。

50 §5.3 映射可归约性 定理 5.24 EQTM既不是图灵可识别的，也不是补图灵可识别的。
§5.3 映射可归约性 定理 5.24 EQTM既不是图灵可识别的，也不是补图灵可识别的。 首先证明EQTM不是图灵可识别的。为此，只要证明ATM可归约到EQTM的补 即可。归约函数如下： F=“对于输入<M，w >，其中M是TM，w 是串： 1) 构造下列两个机器M1和M2。 M1=“对于任何输入： a.拒绝。” M2=“对于任何输入： a.在w上运行M,如果它接受，就接受。” 2)输出<M1，M2>。”

51 §5.3 映射可归约性 这里M1什么也没接受。如果M接受w，则M2接受每一个输入， 故两个机器不等价。相反，如果M不接受w，则M2什么也不接
§5.3 映射可归约性 这里M1什么也没接受。如果M接受w，则M2接受每一个输入， 故两个机器不等价。相反，如果M不接受w，则M2什么也不接 受，故它们是等价的。这样f将ATM归约到EQTM的补，这正是我 们所希望的。 为了证明EQTM的补不是图灵可识别的，只要给出一个从ATM到 EQTM的归约。因此要证明ATM≤mEQTM。下面的TM G计算归 约函数g.

52 §5.3 映射可归约性 G=“对于输入<M，w >，其中M是TM，w 是串： 1) 构造下列两个机器M1和M2.
§5.3 映射可归约性 G=“对于输入<M，w >，其中M是TM，w 是串： 1) 构造下列两个机器M1和M2. M1=“对于任何输入： a.接受。” M2=“对于任何输入： a.在w上运行M b.如果它接受，就接受。” 2) 输出<M1，M2>。” f和g之间的唯一差别在机器M1上。在f中，机器M1总是拒绝.而在g中， 它总是接受。在f和g中。M接受w当且仅当M2接受所有串。在g中，M接受 w当且仅当M1和M2等价。这就是g是从ATM到EQTM的归约的原因。

53 作业 5.1、5.5、5.6、5.28、5.34