第五章可判定性.pptVIP

第五章 可判定性 四个语言类 ? 2013 FZU * 停机问题 语言: ATM = {M, w| M is a TM, w is a string, M accepts w} ATM 可被图灵机识别: U = “On input M, w, where M is a TM and w is a string: Simulate M on w; If M ever enters its accept state, accept; if M ever enters its reject state, reject.” 注意1: U 可视为通用图灵机 注意2: U 不是判定器. ? 2013 FZU * 对角线方法 停机问题：使用 Georg Cantor (1873)的对角线方法。 Cantor’s 方法用来区分无限集合的大小. 无限集合的大小由其集合中的元素个数决定. 如何比较两个无限集合的大小? 考虑两个集合A and B 与f: A?B 单射 满射: 双射，一一对应，一一映射. 集合 A 与B大小相同当且仅当存在双射 f: A?B ? 2013 FZU * 自然数集与偶数集 n f (n) 1 2 3 … 2 4 6 … Figure 1: size of (N) = size of (?) ? 2013 FZU * 可数集 ? 2013 FZU * ? 2013 FZU * 有理数集与自然数集的双射 Let Q be the set of positive rational numbers, Q = { | m, n ?N} 1 2 3 4 5 … 1 2 3 4 5 … 1/1 3/1 2/1 2/2 3/2 3/3 3/4 3/5 … 2/3 2/4 2/5 … 1/2 1/3 1/4 1/5 … 4/2 4/3 4/1 5/1 5/2 5/3 5/4 5/5 … … 4/4 4/5 A correspondence between N and Q 不可数集 若一个无限集合不存在与自然数集N的双射, 则其为不可数集. 例子: 实数集 R. 证明： Cantor 的对角线方法. ? 2013 FZU * R:不可数集 分析: 需要证明R与N之间无双射存在。 反证法： 假定存在双射， 然后构造出一个无法映射的元素x ?R 构造如下： x = 0.d1d2d3d4…: ?i ? N, choose di a digit different from the i-th digit of f(i) 那么: ?i ? N, x ? f(i). ? 2013 FZU * 应用 存在一些语言不可判定，甚至图灵机不可识别. 原因: 语言集合为不可数集 图灵机集合可数 一个图灵机识别一个语言 必然存在语言不能被图灵机识别. ? 2013 FZU * 应用 图灵机集合可数： 对任意字母表? ，字符串集合?* 可数. 根据字符串的长度，字符串集合?*可双射到自然数集. 每个图灵机可编码为一个字符串 忽略非图灵机的字符串。 ? 2013 FZU