递归可枚举语言和递归语言.doc

语言与计算理论导引 递归可枚举语言和递归语言10 递归可枚举语言和递归语言10.1 递归可枚举和递归在本章和后面一章，我们集中讨论图林机识别的语言的外部特征，并且详细研究图林机接受的语言的性质。我们首先形式化说明9.4节提到的图林机接受语言和识别语言的区别。前面讲到，对于图林机T，记号L(T)表示由导致T停机的字符串组成的语言。定义10.1 L*是一个语言，图林机T的输入字母表是，如果L=L(T)，则称T接受L（accept）。xL: *0,1是L的特征函数，如果T计算xL，则称T识别L或判定L（recognize, decide），即*上的任意字符串x都能导致T停机，且如果xL，输出1，否则输出0。如果存在一个图林机接受语言L，则L被称为递归可枚举语言；如果存在一个图林机识别语言L，则L被称为递归语言。显然，每个递归语言都是递归可枚举语言。如果存在一个识别语言L的图林机T，那么很容易构造接受L的图林机T，只要将输出0的停机动作修改成进入崩溃的动作就可以了。但是，反过来的命题就比较复杂了。如果T是接受L的图林机，那么可能存在不属于L的字符串导致T崩溃，而没有输出结果。本章后面，我们将讨论无法消除这种可能的语言。现在，我们只需要记住上面的部分结论。这个结论还有如下更通用的形式。定理10.1 如果L被一个非确定型图林机T接受，并且T上的每一个可能的移动都导致停机或崩溃，则L是递归语言。证明：我们构造一个三带图林机T，它是定理9.2证明中构造的图林机T2的变形。在9.2定理的证明中，T2模拟图林机T的每一个可能的有限的移动序列，如果找到一个导致T停机的序列，T2则停机，否则进入无限循环。我们现在需要的图林机必须在两个方面有所不同：首先，如果T发现了T的一个停机序列，则T在停机之前应该在第一个磁带上输出D1；其次的修改更重要，如果T上没有停机序列，则T必须在适当的时机确定这一点，并且在第一个磁带上输出D0，然后停机。下面着重说明第二个修改。在定理9.2的证明中，T2利用第二个磁带上的数字串来跟踪移动序列，其中的第i个数字指示了第i步的选择。显然，如果没有发现停机序列，但是发现一个整数n，每个长度为n的数字串所表示的移动序列都导致崩溃，则可以判定输入字符串不会被接受。因为如果被接受，则存在一个停机序列，如果停机序列长度小于n，则应该在发现n之前就找到，矛盾；如果停机序列长度大于n，与长度为n的序列都带来崩溃矛盾。因此问题转换成如何发现n。T每次模拟完一个T的导致崩溃的移动序列，将第二个磁带上表示这个移动序列的数字串复制到第一个磁带的空白部分，因此T在第一个磁带上保存了所有导致崩溃的序列的历史，每当T完成某个长度，比如n，的所有序列的模拟（如果T转移的最大可能数是k，则最后一个长度为n的数字串为n个k-1数字组成，比如k=2，则由n个1组成），T搜索第一个磁带看是否所有长度为n的序列都在第一个磁带上，如果是，则找到整数n，擦掉第一个磁带的内容，输出D0；否则继续下一个长度的搜索。下面给出一些判定语言是否是递归可枚举和递归语言的条件。其中一些结果基于构造能够同时模拟其他两个图林机的图林机的方法。定理10.2 如果L1和L2是字母表上的递归可枚举语言，则L1L2和L1L2也是递归可枚举语言。证明：设接受L1和L2的图林机分别是T1=(Q1, , G1, q1, d1)和T2=(Q2, , G2, q1, d2)，现在分别构造接受L1L2和L1L2的图林机。构造思路与定理3.4的证明很相似，我们引入了2元组状态Q1Q2，分别跟踪T1和T2的状态转移。我们在前面也讲到，由于PDA的栈的限制，这个方法不能用于PDA的类似的构造。由于图林机的磁带具有极大的灵活性，我们可以使用2带图林机分别模拟T1和T2的磁带。下面以接受L1L2的图林机为例说明。T=(Q, , G, q, d)是一个2带图林机，Q= Q1Q2，转移函数如下，d(p1,p2), (a1,a2)=(q1,q2), (b1,b2), (D1,D2)其中，(qi, bi, Di)= di(pi, ai), i=1,2。T首先将输入字符串从第一个磁带复制到第二个磁带，并且在两个磁带的左端都插入符号#。T满足下面的条件：1. T1和T2都不停止，则T不停止；2. T1和T2至少有一个停机，则T停机；3. 如果T1和T2同时崩溃，则T崩溃；如果其中一个崩溃，则T放弃这个模拟（忽略相应磁带），继续模拟另一个，如果它停止在停机或崩溃，则T以相同方式停止。上面的构造使得T停机时当且仅当T1和T2中至少有一个停机，因此能够推断T接受语言L1L2。语言L1L2以相似的方式处理，不同的是，T1和T2中只要有一个崩溃，则T就崩溃，而只有当T1和T2都停机，T才停机。并集和交集还保持语言的递归性，即两个递归语言的并集和交集仍然是递归语言，而且递归语言还保持补集的递归性。定理10.3 如果L是一个递归语言，则补集L也是递归语言。证明：如果T是识别L的图林机，则只要交换停机时的输出结果，得到的图林机就能识别L。这个简单的构造证明不适用于递归可枚举语言；练习9.10没有明确说明递归可枚举语言的补集不一定是递归可枚举的，但是下面的定理预示了这个结果。定理10.4 如果L是一个递归可枚举语言，它的补集也是递归可枚举语言，那么L是递归语言。证明：设T1和T2分别是接受L和L的图林机，我们构造一个2带图林机接受L，首先利用定理10.2构造接受并集的图林机的方法，然后适当修改。我们已经知道，对于任意一个字符串，T1和T2中有且只有一个停机，修改T如下：当T1或T2停机时，T也停机，并且擦掉第一个磁带内容，如果是T1停机，输出1，否则输出0。10.2 枚举一个语言枚举一个集合的含义是逐个列出集合中的元素。因此如果称一个集合是可枚举的，意味着存在一个枚举这个集合的算法。事实上，根据这个思路，我们可以提出递归可枚举语言和递归语言相应的特征。首先，我们精确地描述图林机是如何枚举一个语言的。显然，使用多带图林机更方便，其中一个磁带用于输出枚举结果。定义10.2 T是一个k带图林机，k=2，语言L*，如果T满足下面的条件，则称T枚举L：1. 第一个磁带的磁带头绝对不会左移；2. 在任何时候，第一个磁带的内容形式是，x1#x2#.#xn#y，其中n=0，每个xiL，且各不相同，y是L的另一个元素的前缀；3. 对于每个xL，x最终作为其中的某个xi出现在第一个磁带上。根据上面的定义，如果L是一个有限语言，图林机枚举完所有L中的字符串后，或者停机，或者继续移动，不会在第一个磁带上打印任何内容；如果L是一个无限语言，图林机枚举L的过程不会停止。上面的定义显然是一种合理的形式化“枚举集合元素”这个概念的方法。定义10.1说明能够被图林机接受的语言是递归可枚举语言，而这个名称隐含了递归可枚举语言是能够被图林机枚举的语言，证明的思路是简单的，但是详细证明有些繁琐。一方面，如果存在图林机T枚举语言L，那么给定一个字符串x，我们能够等待观察x是否在出现在T的输出结果中，来判断x属于L。如果x属于L，上面策略能够保证T接受x，如果不属于L，则保证不接受。另一方面，如果T是接受L的图林机，为了枚举L，我们先定义字符串的顺序，比如9.6节引入的规范顺序（canonical order），即短字符串先于长的，长度相同的按照字母表顺序。然后，我们根据这个顺序考虑*上的所有字符串，逐个判定字符串x是否属于L，比较复杂的问题是，x可能导致T无限循环，下面的证明着重解决这个问题。定理10.5 语言L*是递归可枚举当且仅当L能够被图林机枚举。证明：假设T是枚举L的图林机，构造接受L的图林机T1如下。T1的磁带比T多一个，第一个磁带是增加的那个磁带，作为输入磁带，然后T1模拟T，每当符号#输出在第二个磁带上，T1暂停，检查新输出的字符串是否与第一个磁带上的输入字符串相同，如果相同，T1停机，如果不同，继续上面的“枚举-比较”过程。显然，T1接受且只接受属于L的字符串。更具体而言，T1开始完全模仿T的动作，忽略第一个磁带，直到输出符号#，则只考虑第一个磁带和第二个磁带，忽略其他磁带，如果不匹配，则回到初始格局。反过来，如果T接受L，我们构造一个3带图林机T1枚举L。第一个磁带是输出磁带，第二个磁带用于生成*上的每个字符串x，第三个磁带用于模拟T处理x的动作。为了避免前面提到的难点，T1模拟T的越来越长的有限移动序列，而不是试图完成单个字符串的所有移动。因此，第二个磁带不仅保存目前为止的所有生成的所有字符串，而且保存T处理每个字符串的移动次数。我们采用*上的规范顺序，比如=a,b，则字符串的生成顺序是，L, a, b, aa, ab, ba, bb, aaa, aab, ., bbb, aaaa, aaab, .T1做如下的多趟扫描。第一趟扫描，T1生成字符串L，并且模拟T在这个输入字符串L上的一步移动；第二趟扫描，T1模拟在L上的两步移动，并生成a，模拟T在a上的一步移动；第三趟扫描，T1模拟在L上的三步移动，模拟在a上的两步移动，生成b，模拟在b上的一步移动。第i趟扫描完成后，第二个磁带的内容的形式如下，其中字符串后面的1的数目表示T1处理该字符串所用的步数。x是规范顺序中的第i个字符串。在下一趟扫描中，T1给第二个磁带上的每个字符串增加一个1，即增加一次移动，然后复制到第三个磁带，模拟T处理这个输入字符串的规定数目的前面过程，然后擦掉第三个磁带。如果T停机，T1将这个字符串复制到第一个磁带，并添加符号#，第二个磁带上的内容都模拟完后，添加规范顺序中的下一个字符串（次处是x的下一个字符串）到第二个磁带，并添加一个1，复制到第三个磁带，然后类似上面的处理。我们没有明确写出T1完成这些动作需要的簿记装置，但是它们能够很直观地实现，显然每个被T接受的字符串最终会出现在T1的第一个磁带上，且只有这样的字符串出现在上面。定理10.5证明的第二部分，应该注意，尽管*上的字符串按照规范顺序出现在第二个磁带上，但是L中的字符串不是按照规范顺序列举在第一个磁带上。如果给予T更强的假设，我们能够很容易构造出按照规范顺序列举接受字符串的图林机。这个更强的假设是，如果T不仅接受L，而且识别L。反过来可以说，如果存在图林机按照规范顺序列举枚举L，则L是递归语言。定理10.6 L是递归语言当且仅当存在一个图林机按照规范顺序枚举L。证明：留作练习10.7。练习中还讨论了根据图林机可计算函数得到的一些递归可枚举语言的一些性质。10.3 非递归可枚举语言我们前面讨论的比较简单的计算模型，FA和PDA，能够接受特定类型的语言，发现了一些它们无法接受的语言。对于图林机，我们也要研究是否存在不能接受的语言，但是由于不存在图林机的泵引理，因此图林机的这个问题要难得多。Church-Turing论题预示了这一点，如果一个想象得到的算法能够被图林机实现，那么它不太可能必须遵循一些相似于FA和PDA泵引理的规律性约束，因为图林机接受语言的能力太灵活了。我们很快将能够展示一个不是递归可枚举的语言。当然，并不是一定先有一个构造性证明说明这种语言一定存在，然后才能讨论这种语言。但是先构造一个这种语言具有下面的好处：首先，证明的梗概很容易从直觉出发得到理解；其次，它表明不仅存在非递归可枚举语言，而且更严格地讲，大多数语言都是非递归可枚举的；第三，它引入了一种特别的方法，“对角线参数法”（diagonal argument），我们在后面章节还会用到这个方法，它是一个很有効的寻找一组特殊参数的方法。方法的思路很简单，如果存在的语言比图林机的个数多得多，那么就一定存在与图林机无关的语言。显然，存在无限多的语言和图林机，因此，为了得到一个精确的论证，我们需要定义一个精确比较两个无限集合大小的方法。说两个有限集合大小相等不困难，如果比较方法得当，它还可以推广到更广泛的情况。为什么说集合a,b,c和x,y,z具有相同的规模？当然，一个原因是它们的元素都是3个，但是这种方法无法推广到无限集合，因此我们需要的方法是直接比较，而不是具体统计集合元素的个数。一个好的比较上面两个集合的方法是定义一个双射函数，函数定义域是一个集合，值域是另一个集合，这个方法很容易推广到任意的集合上。上面的思想陈述如下：如果存在一个从集合A到集合B的双射，则称A和B的大小相同。集合的大小相同是一个等价关系（参见练习10.26a），因此具备自反、对称和传递等性质。尽管我们避免象谈论数量那样谈论集合的大小，但是我们希望能够像比较数量那样比较集合的大小。比如说集合p,q,r,s,t比a,b,c大，这是因为两个集合间存在一个一一映射，因此一个集合的大小与另一个集合的子集的大小相等，而集合本身大于或等于它的子集。显然，这个方法也可以推广到无限集合。实际上，不仅存在某些无限集大于另一些无限集，而且无限集有着许多不同的规模（参见练习10.18和10.26）。本节，我们只需要区分两类无限集，一类是与自然数集N大小相同的无限集，另一类是比自然数集大的无限集。（本文的自然数集包括0）定义10.3 如果存在一个从自然数集到集合S的双射，那么集合S称为可数无限集。如果S是可数无限集或有限集，那么S称为可数集，或可数的。一个不可数的集合，称为不可数无限集，或不可数集。说函数f: NS是一个双射函数意味着满足下面三个条件：1. 对每个自然数n，都有f(n)S；2. 对任意两个不同的自然数m和n，f(m)f(n)；3. S中的每个元素s，都存在一个自然数n，使得s=f(n)。因此如果说S是可数无限集，意味着S中的元素能够以f(0), f(1), .的方式列举，每个元素只在列表中出现一次，如果S是有限集，则这个列表的长度有限。存在两种错误理解术语“列举”的情况。第一种，显然不存在实际的、物理意义上的、完全的列举元素，仅仅证明了存在一个函数，对S中的任意一个元素，都可以利用这个函数在列表中发现该元素；第二种，我们说“列举”，并没有说明一个明确的算法来“列举”，仅仅说明了存在一个双射函数，也没有说明发现或计算这个函数的算法。注意，任意两个可数无限集的大小相同，如果事实上无限集的规模有很多种，那么所有的不可数集不可能是同一个规模，而且任何一个不可数集的规模大于任何一个可数集。这个结论不是很明显，可以从下面的事实推论得到。引理10.1 每个无限集都有一个可数无限子集。证明：我们证明如果S是一个无限集，那么存在一个从自然数集N到S的子集的双射f。下面，我们逐个整数定义f的映射。因为S是无限集，则至少存在一个元素，选择这个元素，并定义为f(0)。假设这个过程进行到了第n步，从S中选择了n个不同的元素，分别定义为f(0), f(1), ., f(n)。由于S是无限的，能够从中选择一个不同于上面n个元素的元素，称为f(n+1)，因此根据数学归纳法原理，我们能够在整个n=0的自然数集上定义f(n)，而且它是一个一一映射。另一个关于可数集的有用的事实是：可数集的任意子集都是可数集。这个结论很明显，参见练习10.12。最直接的可数无限集是自然数集本身，容易发现许多其他可数无限集，比如集合S=0, 1/2, 1, 3/2, 2, 5/2, .是一个可数无限集，因为S=0, 1/2, 2/2, 3/2, 4/2, 5/2, .它与自然数集存在明显的双射关系。当然，初步观察，S似乎应该比自然数集N大，因为S包含了N的所有元素，还含有一些其他元素。即存在一个从N到S的真子集的双射，如果它们是有限集，显然S大于N，但对于无限集，不能得出同样的结论，看起来似乎不符合直接，但它在数学意义上是正确的（参见练习10.13）。对于无限集，可能既存在从一个集合到另一个集合的真子集的双射，也存在到另一个集合自身的双射。下面的结论将给出一大类可数无限集，它的含义是可数个可数集的并集仍然是可数集。定理10.7 设S0, S1, .是可数集，那么它们的并集S=也是可数集。证明：我们假设所有的集合Si中没有空集（如果需要，可以重新命名），我们描述一种列举这个并集中所有元素的方法。每一行列举一个集合Si，第一行是集合S1，第i行是集合Si，得到一个二维数组如下。其中，由于Si可以是有限集或无限集，因此每行的长度可能不同，现在考虑图10-1所示的一个列举路线。显然，这个路线能够包含进并集S的每个元素至少一次，如果元素s出现在多个Si中，则路径将多次包含这个元素。我们定义函数f如下：f(i)=则f是一个双射函数，如果S是有限的，是从1.m到S的双射函数，否则是从N到S的双射函数。由于有限个可数集的并集是S的子集，因此有限个可数集的并集也是可数集。例子10.1 S=NN是所有自然数二元对组成的集合，S是可数集。分析：容易根据定理10.7得到S是一个可数集，因为而每个集合mN都是可数集，因为存在双射函数fm: NmN, fm(n)=(m,n)。但是我们可以更直接地构造从N到NN的双射函数f，采用类似定理10.7和图10-1的方法。我们先给出它的逆函数f-1，即从NN到N的函数，也是图10-1用到的枚举方法。我们再次考察图中的路径，设j=0，当路径循回到第j次，它命中的二元对(m,n)满足m+n=j，共有j+1个这样的二元对。特别地，如果当前二元对是(m,n)，m+n=j，则路径上包含所有(p,q)，p+q=2），如果T满足下面的条件，则称T枚举语言L：第一个磁带的带头没有左移任何时刻，第一个磁带的内容都形如：x1#x2#.#xn#yxiL，各不相同，y是一个不同于xi的L中的元素的前缀。L中的每个元素，最终都会以某个xi的形式出现在第一个磁带上。定理10.5 语言L是递归可枚举的当且仅当它能够被某个TM枚举。证明：？定理10.6 L是递归语言当且仅当存在一个TM T按照canonical序枚举它。canonical序：长度短的优先，如果长度相等，则按字母顺序排列。10.3 不是所有的语言都是递归可枚举的定义10.3 如果存在一个从集合S到自然数集N的双射，则称S是可数无限集；如果S是有限集或可数无限集，则称S是可数的；如果S不是可数的，则称S是不可数无限集。引理10.1 每个无限集都有一个可数无限的子集。定理10.7 可数集的并集仍然是可数集。证明：？例子10.2 对于任何一个有限字母表，*（上的所有字符串组成的集合）是可数集。证明：*=n=0-n例子10.3 所有TM组成的集合T，以及所有递归可枚举语言组成的集合RE，都是可数的。证明：根据前面对TM的编码方法，可以构造一个双射函数，e: T0, 1*，而集合0, 1*是可数的，同样可以构造从RE到T的双射函数。如果我们能够证明所有语言构成的集合是不可数的，而递归可枚举语言的集合却是可数的，则表明存在不是递归可枚举的语言。定理10.8 任给一个可数无限集S，则S的幂集是不可数无限集。特别地，任给一个非空字母表，则上所有语言组成的集合是不可数的。证明：只要证明自然数集N的幂集2-N是不可数的。反证法。假设2-N是可数的，则存在一个从N到2-N的一一映射，则可以表示成2-N=A0, A1, .，现在定义一个N的子集，A=iN | iAi，由于A是N的一个子集，则存在一个自然数I，使得A=AI，现在判定自然数I是否属于A。如果IA，则IAI，根据A的定义，则IA，矛盾。如果IA，则IAI，根据A的定义，则IA，矛盾。因此，无论我们如何假设I，都会导致矛盾，因此初始假设2-N是可数的不成立，即2-N是不可数集。上所有语言组成的集合L是*的幂集，*可数无限集，因此L是不可数集。因此存在不是递归可枚举的语言，即不能被TM接受的语言。如果所有语言组成的集合相当于实数集，则TM能够处理的