形式语言课件：第5章 不可判定性

第5章不可判定性5.1Church-Turing论题5.2通用Turing机5.3停机问题5.4与Turing机有关的不可判定问题5.5与文法有关的不可解问题5.6不可解的铺砖问题5.7递归语言的性质第5章不可判定性5.1Church-Turing论题Church-Turing论题的描述

采用在所有输入上停机的Turing机作为与“算法”的直觉化概念相对应的精确的形式化概念。----可判定性机器是算法，半判定机器不是算法。不能被变换成在所有输入上停机的Turing机的任何东西都不能被认为是算法，而所有这样的机器都被正确的称为算法。5.2通用Turing机通用Turing机概念用Turing机的形式化这种编程语言写的一段程序，它可以用来解释执行用同样语言写的另一段程序，这种用Turing机的形式化编程语言编写的具有解释执行功能的程序叫做通用Turing机。---类似于自编译系统Turing机的一般方法

Turing机的描述可用来作为其他Turing机的输入。即要定义一个语言，它的字符串都是Turing机的合法表示。问题：无论我们为这种表示选择多么大的字母表，总是存在有更多状态和更多带符号的Turing机。解决方法：把状态和带符号编码成固定字母表上的字符串。具体方法：约定：表示Turing机状态的字符串形如{q}{0，1}*，即字母q后面跟着二进制字符串。同理，带符号总是表示为{a}{0，1}*里的字符串。设M={K，∑，δ，s，H}是Turing机，设i和j是满足2i≥|K|和2j≥|∑|+2的最小整数。于是，K里的每一个状态都表示成q后面跟着长度为i的二进制字符串，∑里的每个符号类似地表示成字母a后面跟着j位的二进制字符串。

对特殊符号

⊔，►，←，→的表示，分别被固定成4个在字典顺序下最小的符号：⊔总是表示成a0j，►表示成a0j-11，←表示成a0j-210，→表示成a0j-211。初始状态总是表示成在字典序下的第一种状态，即q0i。注意：在符号a和q后面跟着的字符串里，用前缀的0来保证总长度达到所要求的长度。

若把整台Turing机M的表示记作“M”，则：“M”包括状态转移表δ，即它是形如（q，a，p，b）的字符串的序列，其中q和p表示状态，a和b标识符号。约定：从δ(s,⊔)开始，以字典序下的升序排列四元组。停机状态集H将被直接确定，因为停机状态不出现在”M”的任何四元组的第一个分量上。若M判定语言，因此H={y,n}，则约定y是这两种停机状态中在字典序下较小的。通过这种方法，任意的Turing机都可被表示出来。并且可以用同样的方法表示Turing机的字母表里的字符串(即输入串)。例5.2.1考虑M=（K，∑，δ，s，{h}），其中K={s，q，h}，∑={⊔

，►，a}，并且δ如表5-1所示。

状态符号δsas⊔s

►qaq⊔

q►（q,⊔

）（h,⊔

）（s,→）（s,a）（s,→）（q,→）表5-1状态/符号表示sqh⊔►←→aq00q01q11a000a001a010a011a100表5-2K={s，q，h}，∑={⊔，►，a}所以满足2i≥3和2j≥3+2的最小整数为i=2和j=3因此，符号串►aa⊔a的表示是“►aa⊔a”=a001a100a100a000a100Turing机M的表示“M”是下列字符串：（状态转移描述）“M”=(q00,a100,q01,a000),(q00,a000,q11,a000),(q00,a001,q00,a011),(q01,a100,q00,a011),(q01,a000,q00,a011),(q01,a001,q01,a011)通用Turing机U，它用其他机器的编码作为程序来指导它的操作。

U收到两个自变量，分别是机器M的描述“M”和输入字符串w的描述“w”。希望U具有的性质：U在输入“M”“w”上停机当且仅当M在输入w上停机。U（“M”“w”）=M（w）用第4章开发的Turing机的函数记号表示为：通用Turing机实际上描述是密切相关的3带机器U’（单带机U将模拟U’）：第一条带包含M当前带内容的编码W’；第二条带包含M自身的编码M’；第三条带包含在被模拟的计算中M当前的状态的编码。U’扫描第二条带直到发现第一个分量与写在第三条带上的状态编码相匹配，第二分量与在第一条带里扫描的符号编码相匹配的四元组；----利用前两个分量找到相应的四元组若找到这样的四元组，则U’把第三条带上的状态改成四元组的第三个分量，并且在第一条带里完成四元组的第四个分量所提示的操作；若在第二条带里找不到规定的状态与符号的组合，则意味着第三条带上的状态是停机状态。U’也在适当的状态里停机。U’模拟M的过程：5.3停机问题halts(P,X)------P是一个程序，X输入halts(P,X)是这样一个程序：它收到用同样语言写的程序P和这个程序的输入X作为输入。它总是正确地判定在输入X上程序P是否停机（若停机它返回“是”），或者P是否死循环（若P死循环它返回“否”）。这段程序命名为halts(P,X)。

这是最有价值的程序，你可用它完成许多不寻常的事情。比如你可用它写用不祥的名字diagonal(X)命名的另一段程序(即判断一个程序X对于它自己作为输入时是否停机)。

diagonal(X)定义如下：

diagonal(X)a:ifhalts(X,X)thengotoaelsehalt

如果你的halts程序断定当程序X用它自身X作为输入时X停机，那么diagonal(X)死循环；否则它停机。

矛盾：diagonal(diagonal)是否停机？它停机当且仅当对halts(diagonal,diagonal)的调用返回“否”；即它停机当且仅当它不停机。结论：假设是假的，程序halts(P,X)其实并不存在。没有程序，没有算法可解决假设halts解决的问题：判别任意的程序是停机还是死循环。非递归的语言定义及其证明设H={“M””w”：Turing机M在输入w上停机}注意：H是递归可枚举的，它是通用Turing机半判定的语言。确实，在输入“M”“w”上，恰好当输入属于H时U才停机。若H是递归的，则每个递归可枚举语言都是递归的。即：所有递归可枚举语言也是Turing机可判定的(不是半判定)，当且仅当H是递归的。------通过对角化可知假设导致逻辑矛盾。定理5.3.1语言H不是递归的;所以，递归语言类是递归可枚举语言类的真子集。

注：递归语言是可判定的，而H是不可判定的。定理5.3.2

递归可枚举语言类在补运算下不封闭。

注：反证法。假设在补运算下封闭（即补语言也是递归可枚举语言），则H就是可判定的。茅盾！5.4与Turing机有关的不可判定问题不可判定：没有对任意给定的Turing机M和输入字符串ω判定M是否接受ω的算法。没有算法的问题称为不可判定的或者不可解的。最有名的和最基本的不可判定问题是辨别给定的Turing机在给定的输入上是否停机的问题，我们刚刚证明它的不可判定性。这个问题通常称为Turing机的停机问题。定义5.4.1设L1,L2

∑*是两个语言。从L1到L2的规约是递归函数φ:∑*→∑*使得x∈L1当且仅当φ(x)∈L2定理5.4.1

若L1不是递归的，并且存在从L1到L2的归约，则L2也不是递归的。

证明：假设L2是递归的，比如说用Turing机M2判定，并设T是计算归约φ的Turing机。那么Turing机TM2判定L1。但是L1是不可判定的，矛盾。通过对角化证明了停机问题是不可判定的，就可由此得出一大批问题的不可判定性。这里可直接通过归约证明：定理5.4.2

与Turing机有关的下列几个问题是不可判定的。a)给定Turing机M和输入字符串ω，M是否在输入ω上停机？b)给定Turing机M，M是否在空带上停机？c)给定Turing机M，究竟有没有M在上面停机的字符串？d)给定Turing机M，M是否在每一个输入字符串上都停机？e)给定两台Turing机M1和M2，他们是否在同样的字符串上停机？f)给定Turing机M，M半判定的语言是否正则？是否上下文无关？是否递归？g)另外，存在某台固定机M0，对下列问题是否不可判定：给定ω，M0是否在ω上停机？证明：可以把停机问题归约到该问题或把前一个问题归约到后者。见书上166-167页5.5与文法有关的不可解问题不可解问题不但出现在Turing机的领域里，而且事实上出现在所有的数学领域里。例如存在多个与文法有关的不可判定问题，总结如下：定理5.5.1

下列每个问题都是不可判定的：a)对给定的文法G和字符串ω，判定是否ω∈L(G)。b)对给定的文法G，判定是否e∈L(G)。c)对两个给定的文法G1和G2，判定是否L(G1)＝L(G2)。d)对任意的文法G，判定是否L(G)＝Φe)另外，存在某个固定的文法G0，使得判定任意给定的字符串ω是否属于L(G0)，这是不可判定的。定理5.5.2

下列每个问题都是不可判定的：a)给定上下文无关文法G，是否L(G)＝∑*?b)给定两个上下无关文法G1和G2，是否L(G1)＝L(G2)？c)给定两台下推自动机M1和M2，它们是否恰好接受同样的语言？d)给定下推自动机M，是否能找出状态数量最少的等价的下推自动机。5.6不可解的铺砖问题问题描述：给定砖的有穷集，每块砖是单位正方形，而且我们有每块砖的无穷多块复制品。要求我们用这些砖的复制品来铺满平面的第一象限。仅有的限制是左下角放特殊的砖，只有特定的成对的砖才可彼此水平相邻,只有特定的成对的砖才可彼此垂直的相邻。（砖不可被旋转或翻面）给定砖的有穷集，原点砖和相邻规则，有没有判定第一象限能否被铺满的算法？这个问题可形式化如下。铺砖系统是四元组⊙=(D,d0,H,V)，其中D是砖的有穷集，d0∈D，并且H,V⊆D×D。根据⊙的铺砖是函数f:N×ND使得下列关系成立：

f(0,0)=d0(f(m,n),f(m+1,n))∈H对于所有的m,n∈N

(f(m,n),f(m,n+1))∈V对于所有的m,n∈N定理5.6.1：给定铺砖系统，判定是否存在根据这个系统的铺砖，这个问题是不可判定的。

证明：主要思想是把给定Turing机M，判定M是否在输入e上不停机的问题（停机问题的补，所以是不可判定问题）归约到铺砖问题上。-----略5.7递归语言的性质定理5.7.1:语言是递归