2021年：可规约性.ppt

*
前言
本章讨论另外几个不可解的问题 。在讨论过程 中，将介绍一个基本方法，可用来证明问题是计算上不可解的，这个方法称为可归约性。
归约旨在将一个问题转化为加一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。
例如，在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。
：可规约性
*
*
前言
可归约性总是涉及两个问题，称之为 A 和 B。如果 A 可归约到 B，就可用 B 的解来解 A。
可归约性说的不是怎样去解 A 或 B，而是在知道 B 的解时怎么去解 A。
归约的目的在于：将一个问题转化为另一个问题；且用第二个问题的解来解第一个问题。
归约的应用（A 可归约到 B ）
如果 B 是可判定的，则 A 也是可判定的。
如果 A 是不可判定的，则 B 也是不可判定的。
：可规约性
*
*
主要内容
语言理论中的不可判定问题
一个简单的不可判定问题（自学）
映射可归约性
可计算函数
映射可归约性的形式定义
：可规约性
*
*
语言理论中的不可判定问题
ATM={ <M, w> | M 是一个 TM，且接受 w }
ATM 是不可判定的，即确定一个图灵机是否接受一个给定的输入问题是不可判定的。
下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定输入是否停机（通过接受或拒绝）问题。
若将 ATM 归约到 HALTTM，就可以利用 ATM 的不可判定性证明HALTTM的不可判定性。
HALTTM 的形式化描述
HALTTM = { <M,w> | M是一个TM, 且对输入 w 停机}
：可规约性
*
*
HALTTM 是不可判定的
定理

HALTTM是不可判定的。
证明思路：反证法。（将 ATM 归约到 HALTTM ）
假设 TM R 判定 HALTTM，利用 R 可以构造一个判定 ATM 的 TM S。
使用 R，可以检查 M 对 w 是否停机，
如果 M 对 w 不停机，S 就拒绝，因为 <M,w > 不在 ATM 中。
如果 M 对 w 确实停机，S 就模拟它，而不会有死循环的危险。
这样，如果 TM R 存在，就能判定 ATM。
：可规约性
*
*
语言理论中的不可判定问题
定理

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 也必定是不可判定的。
：可规约性
*
*
语言理论中的不可判定问题
定理

ETM 是不可判定的。
假设 ETM 是可判定的，以此证明 ATM 是可判定的。
设 R 是判定 ETM 的一个 TM，考虑用 R 来构造判定 ATM 的 S。
当 S 收到输入<M, w>时，如何运行？
构造 S 的一个想法是：输入 <M> 上运行 R 且看它是否接受。
如果是，知道 L(M) 是空集，因此M不接受w。
如果 R 拒绝 w，则只知道 L(M) 不空，即 M 接受某个串，但是不知道是否接受这个特定的 w。
因此，不能在<M> 上运行 R。
目标：修改<M>，使得除了 w 外，M 对所有串都拒绝。
ETM = { M | M 是一个TM，且L(M)= } 空问题
：可规约性
*
*
语言理论中的不可判定问题
定理

ETM 是不可判定的。
先用标准术语来写在证明思路中描述的那个修改型机器M1.
M1 = “在输入x上：
1) 如果 x≠w，则拒绝。
2) 如果 x=w，则在 x上运行M，当M接受时，就接受。”
这个机器以 w 作为它的描述的一部分。检查 x=w 是否成立的方法很显然，
即扫描输入并用一个字符一个字符地将它与 w 进行比较，就可确定它们是否相同。
ETM = { M | M 是一个TM，且L(M)= } 空问题
：可规约性
*
*
语言理论中的不可判定问题
再假设 TM R 判定 ETM。如下构造判定 ATM 的