算法设计与分析-钟

1、CH5 不可判定性 丘奇-图灵论题“Nothing will be considered an algorithm if it cannot be rendered as a Turing machine that is guaranteed to halt on all inputs, and all such machines will be rightfully called algorithms.”在所有输入上都停机的TM作为 “算法”的直觉化概念。根据丘奇-图灵论题，不能用TM完成的计算任务，是不可能的, 没有希望的。5.1 丘奇-图灵论题2丘奇-图灵论题是论题，不是定理，因为它不是

2、数学结果：它只断言某个非形式化概念（算法）对应于某个数学对象(TM）。因为不是数学命题，所以丘奇-图灵论题不能被证明。不过在理论上有可能在未来某一天丘奇-图灵论题被证伪，假设有人提出另一种计算模型，公认它是有说服力的和合理的，并且证明它能完成用TM不能完成的计算。没有人认为这是可能的。5.1 丘奇-图灵论题3在第一章里论证过，若利用字符串去表示语言则不能表示出所有语言在任何字母表上只有可数个字符串，却有不可数个语言有穷自动机、下推自动机、上下文无关文法和TM都是可用来规定语言的有穷对象的例子 ，并且它们自身可用字符串来描述。相应地在任何字母表上只有可数多个递归和递归可枚举语言。所以，虽然我们尽

3、量扩充计算机的能力，但是从根本上说，在所有可能的语言里只有无穷小的部分可用计算机去半判定或判定。5.1 丘奇-图灵论题4在前几章里发现过非正则语言；在本章我们同样要发现非递归语言。不过有两点主要区别这些新的否定性结果不仅仅是暂时的挫折：根据丘奇-图灵论题，不能用TM完成的计算任务，是不可能的, 没有希望的。其次用来证明语言是非递归的方法不得不有别于为发掘上下文无关文法和有穷自动机的弱点而用过的“泵”定理5.1 丘奇-图灵论题5已经学到的TM是固化的：只用来判断某个特定语言或者计算某个特定函数是否存在一个TM，可以模拟任意特定的TM？Universal TM （通用TM）类似编程语言，可形式化描

4、述任意TM，并解释执行该描述5.2 通用TM65.2 通用TM通用TM U不仅接受字符串输入，还接受其它TM描述作为输入5.2 通用TM如何输入TM M挑战M可能的状态数和字母表无限多U作为固定的机器，必须有确定的字母表解决方案把M中的状态和字母编码到固定字母表上的字符串表示状态的字符串：q0,1*表示带符号的字符串： a0,1*采用固定长度编码5.2 通用TM字符编码 将任意字符编码为以a开头后接j个bits的字串4个特殊字符被编码为长度为j的最小的4个编码字符串被表示为字符的连接9265.2 通用TM状态编码 i是满足2i = |K| 的最小整数将任意状态编码为以q开头后接i个bits的字

5、串开始状态被编码为q0i105.2 通用TMM的编码状态转移函数用字串表示状态转移函数被记为向量：（q, a, p, b） 代表(q,a)= (p,b)M被编码为状态转移向量的序列 通过这种方法，任意TM都可被表示115.2 通用TM12 i2和j32i3 2j 32的最小整数。135.2 通用TM14通用Turing机U的描述U收到两个自变量，分别是机器M的描述 “M”和输入字符串w的描述 “w” U具有下列性质 ：U在输入“M” “w”上停机当且仅当M在输入w上停机 。即 U(“M”“w”)= “M(w)”5.2 通用TMU的设计构造一个3带的TM UM当前带内容的编码M自身的编码M当前状

6、态的编码5.2 通用TMU的设计U启动时，带1上为”M”w”，带2、3为空U将”M”移动到带2，并把”w”平移到带1左端，带3写上初始状态sU模拟M的每步计算：在带2上找到与当前状态（带3）和输入字符（带1）匹配的转移分量（p, a, q, b） ，相应更新当前状态（带3）和完成操作（带1）重复第3步直到停机（带3含状态h）多带TM U 可等价转换为TM U假设你设计了下述程序：halts (P, X)接受的输入：一个程序P和其输入X总是正确地判定若P对X停机， 它返回“是”若P对X死循环，它返回 “否”5.3 停机问题17这是最有价值的程序，它发现使得其他程序在某些输入上死循环的所有微妙的编

7、程错误在其基础上设计一段程序diagonal (X) ： a: if halts (X, X) then goto a else halt如果你的halts程序断定程序X用它自身X作为输入时X停机，那么diagonal (X)死循环；否则它停机。5.3 停机问题185.3 停机问题diagonal (diagonal)是否停机?它停机当且仅当对halts (diagonal, diagonal)的调用返回 “否”换句话说，它停机当且仅当它不停机自相矛盾，结论是：程序halts(P, X)不存在即：没有程序，没有算法可解决停机问题：辨别任意的程序是停机还是死循环。19H= “M” “w”：Tur

8、ing机M在输入w上停机H是递归可枚举的 ：构造通用TM U来半判定输入；在输入“M” “w”上，恰好当输入属于H时U才停机可证明H非递归首先，假设H是递归的，令w=M，则H1=“M”: Turing机M在输入字符串 “M”上停机也是递归的。非递归语言20非递归语言215.3 停机问题22Chomsky语言分层Regular LFAContext Free LPDARecursive LTM-decidableRecursive Enumerable LTM-semi5.3 停机问题5.4 与TM有关的不可判定问题定理5.3.1 H非递归：即没有对任意给定的TM M和输入字符串w判定M是否接受

9、w的算法无算法则问题不可判断或者不可解半判定 不可判断仅递归语言可判定245.4 与TM有关的不可判定问题定义5.4.1 设L1，L2是两个语言。从L1到L2的归约是递归函数:*使得xL1当且仅当(x)L2 。问题A可归约为问题B，指问题B的答案可用于解决问题A解决A的难度不会难于解决B定理5.4.1 若L1非递归，并且存在从L1到L2的归约，则L2也非递归。255.4 与TM有关的不可判定问题定理5.4.2 与TM有关的下列问题是不可判定的：给定TM M和输入字串w，M是否在输入w上停机？给定TM M，M是否在空带上停机？给定TM M，有没有M在上面停机的字符串？给定TM M，M是否在每一个

10、输入字串上都停机？给定TM M1和M2，它们是否在同样的字符串上停机？给定TM M，M半判定的语言是否正则？是否上下文无关？是否递归？固定机器M0，给定w， M0是否在w上停机265.4 与TM有关的不可判定问题定理5.4.2 与TM有关的下列问题是不可判定的：给定TM M和输入字串w，M是否在输入w上停机？定理5.3.1 H非递归给定TM M，M是否在空带上停机L= “M”: M在e上停机H非递归，构造H到L的归约，即可证明L非递归给定M和w，构造归约函数TM Mw：当Mw在空格带上启动时， Mw把w写在带上，然后开始模拟M”M”w” H iff ” Mw” L其它证明自学275.7 递归语言的性质285.7 递归语言的性质定理5.7.4 Rice定理假设是所有递归可枚举语言组成的类的非空真子集，那么下列问题是不可判定的：给定TM M，是否L(