可归约-精选课件(公开).ppt

朴秀峰 xfpiao@126.com 前言 本章讨论另外几个不可解的问题 。在讨论过程 中，将介绍一个基本方法，可用来证明问题是计算上不可解的，这个方法称为可归约性。 归约旨在将一个问题转化为加一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。 例如，在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。 从波士顿到巴黎旅行，可归约到两个城市的飞机票，进而归约到找工作问题。 数学上的例子更多。 前言 前言 可归约性总是涉及两个问题，称之为 A 和 B。如果 A 可归约到 B，就可用 B 的解来解 A。 可归约性说的不是怎样去解 A 或 B，而是在知道 B 的解时怎么去解 A。 归约的目的在于：将一个问题转化为另一个问题；且用第二个问题的解来解第一个问题。 归约的应用（A 可归约到 B ） 如果 B 是可判定的，则 A 也是可判定的。 如果 A 是不可判定的，则 B 也是不可判定的。 主要内容 5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题（自学） 5.3 映射可归约性 5.3.1 可计算函数 5.3.2 映射可归约性的形式定义 语言理论中的不可判定问题 ATM={ M, w | M 是一个 TM，且接受 w } ATM 是不可判定的，即确定一个图灵机是否接受一个给定的输入问题是不可判定的。 下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定输入是否停机（通过接受或拒绝）问题。 若将 ATM 归约到 HALTTM，就可以利用 ATM 的不可判定性证明HALTTM的不可判定性。 HALTTM 的形式化描述 HALTTM = { M,w | M是一个TM, 且对输入 w 停机} HALTTM 是不可判定的 语言理论中的不可判定问题 语言理论中的不可判定问题 语言理论中的不可判定问题 语言理论中的不可判定问题 再假设 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 拒绝，则接受。” 如果 R 是 ETM 的判定器，则 S 就是 ATM 的判定器。 而 ATM 的判定器是不存在的，故 ETM 必定是不可判定的。 语言理论中的不可判定问题 另一个与图灵机有关的计算问题也很有意思，该问题是： 给定一个图灵机和一个可由某个更简单的计算模型识别的 语言，测定此图灵机是否识别此语言。 例如：令REGULARTM是测定一个给定的图灵机是否有一个与之等价的有穷自动机问题，则这个问题与测定一个给定的图灵机是否识别一个正则语言的问题相同。 REGULARTM = { M | M 是一个 TM，且 L(M) 是一个正则语言} REGULARTM 是不可判定的。（定理5.3） 检查关于语言的任何一个性质是否可由图灵机识别都是不可判定的。（莱斯定理） 语言理论中的不可判定问题 利用历史计算归约 利用历史计算归约的例子 线性界限自动机 线性界限自动机的可判定问题 线性界限自动机的可判定问题 主要内容 5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 (自学) 5.3 映射可归约性 5.3.1 可计算函数 5.3.2 映射可归约性的形式定义 主要内容 5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 5.3.1 可计算函数 5.3.2 映射可归约性的形式定义 映射可归约性 可计算函数 可计算函数 例5.14 可计算函数可以是机器的描述之间的变换。 例如，如果 w = M 是图灵机的编码，可以有一个可计算函 数 f，以 w 为输入，且返回一个图灵机的描述 M ? 。 M?是一个与 M 识别相同语言的机器，但 M? 从不试图将它的读写头移出它的带的左端点。函数 f 通过在 M 的描述中加入一些状态来完成这个任务。如果 M不是图灵机的合法编码，f 就返回? 映射可归约性的形式化定义 映射可归约性 例5.8 定理5.1使用从 ATM 出发的一个，证明了 HALTTM是不可判定。 这个归约说明了怎么用 HALTTM 的判定器给出 ATM 的判定器。 以下展示从 ATM 到 HALTTM 的映射可归约性。 必须提供一个可计算函数 f，它使用形如 M, w 的输入， 返回形如 M ? ,w ? 的输出，使得 M, w ∈ATM