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

1、语言与计算理论导引 递归可枚举语言和递归语言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），

2、即å*上的任意字符串x都能导致T停机，且如果xÎL，输出1，否则输出0。如果存在一个图林机接受语言L，则L被称为递归可枚举语言；如果存在一个图林机识别语言L，则L被称为递归语言。显然，每个递归语言都是递归可枚举语言。如果存在一个识别语言L的图林机T，那么很容易构造接受L的图林机T，只要将输出0的停机动作修改成进入崩溃的动作就可以了。但是，反过来的命题就比较复杂了。如果T是接受L的图林机，那么可能存在不属于L的字符串导致T崩溃，而没有输出结果。本章后面，我们将讨论无法消除这种可能的语言。现在，我们只需要记住上面的部分结论。这个结论还有如下更通用的形式。定理10.1 如果L被一

3、个非确定型图林机T接受，并且T上的每一个可能的移动都导致停机或崩溃，则L是递归语言。证明：我们构造一个三带图林机T，它是定理9.2证明中构造的图林机T2的变形。在9.2定理的证明中，T2模拟图林机T的每一个可能的有限的移动序列，如果找到一个导致T停机的序列，T2则停机，否则进入无限循环。我们现在需要的图林机必须在两个方面有所不同：首先，如果T发现了T的一个停机序列，则T在停机之前应该在第一个磁带上输出D1；其次的修改更重要，如果T上没有停机序列，则T必须在适当的时机确定这一点，并且在第一个磁带上输出D0，然后停机。下面着重说明第二个修改。在定理9.2的证明中，T2利用第二个磁带上的数字串来跟踪

4、移动序列，其中的第i个数字指示了第i步的选择。显然，如果没有发现停机序列，但是发现一个整数n，每个长度为n的数字串所表示的移动序列都导致崩溃，则可以判定输入字符串不会被接受。因为如果被接受，则存在一个停机序列，如果停机序列长度小于n，则应该在发现n之前就找到，矛盾；如果停机序列长度大于n，与长度为n的序列都带来崩溃矛盾。因此问题转换成如何发现n。T每次模拟完一个T的导致崩溃的移动序列，将第二个磁带上表示这个移动序列的数字串复制到第一个磁带的空白部分，因此T在第一个磁带上保存了所有导致崩溃的序列的历史，每当T完成某个长度，比如n，的所有序列的模拟（如果T转移的最大可能数是k，则最后一个长度为n的

5、数字串为n个k-1数字组成，比如k=2，则由n个1组成），T搜索第一个磁带看是否所有长度为n的序列都在第一个磁带上，如果是，则找到整数n，擦掉第一个磁带的内容，输出D0；否则继续下一个长度的搜索。下面给出一些判定语言是否是递归可枚举和递归语言的条件。其中一些结果基于构造能够同时模拟其他两个图林机的图林机的方法。定理10.2 如果L1和L2是字母表å上的递归可枚举语言，则L1ÈL2和L1ÇL2也是递归可枚举语言。证明：设接受L1和L2的图林机分别是T1=(Q1, å, G1, q1, d1)和T2=(Q2, å, G2, q1, d2)，现在分别

6、构造接受L1ÈL2和L1ÇL2的图林机。构造思路与定理3.4的证明很相似，我们引入了2元组状态Q1´Q2，分别跟踪T1和T2的状态转移。我们在前面也讲到，由于PDA的栈的限制，这个方法不能用于PDA的类似的构造。由于图林机的磁带具有极大的灵活性，我们可以使用2带图林机分别模拟T1和T2的磁带。下面以接受L1ÈL2的图林机为例说明。T=(Q, å, G, q, d)是一个2带图林机，Q= Q1´Q2，转移函数如下，d(p1,p2), (a1,a2)=(q1,q2), (b1,b2), (D1,D2)其中，(qi, bi, Di)= di

7、(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接受语言L1ÈL2。语言L1ÇL2以相似的方式处理，不同的是，T1和T2中只要有一个崩溃，则T就崩溃，而只有当T1和T2都停机，T才停机。并集和

8、交集还保持语言的递归性，即两个递归语言的并集和交集仍然是递归语言，而且递归语言还保持补集的递归性。定理10.3 如果L是一个递归语言，则补集L也是递归语言。证明：如果T是识别L的图林机，则只要交换停机时的输出结果，得到的图林机就能识别L。这个简单的构造证明不适用于递归可枚举语言；练习9.10没有明确说明递归可枚举语言的补集不一定是递归可枚举的，但是下面的定理预示了这个结果。定理10.4 如果L是一个递归可枚举语言，它的补集也是递归可枚举语言，那么L是递归语言。证明：设T1和T2分别是接受L和L的图林机，我们构造一个2带图林机接受L，首先利用定理10.2构造接受并集的图林机的方法，然后适当修改。

9、我们已经知道，对于任意一个字符串，T1和T2中有且只有一个停机，修改T如下：当T1或T2停机时，T也停机，并且擦掉第一个磁带内容，如果是T1停机，输出1，否则输出0。10.2 枚举一个语言枚举一个集合的含义是逐个列出集合中的元素。因此如果称一个集合是可枚举的，意味着存在一个枚举这个集合的算法。事实上，根据这个思路，我们可以提出递归可枚举语言和递归语言相应的特征。首先，我们精确地描述图林机是如何枚举一个语言的。显然，使用多带图林机更方便，其中一个磁带用于输出枚举结果。定义10.2 T是一个k带图林机，k>=2，语言LÍå*，如果T满足下面的条件，则称T枚举L：1. 第一

10、个磁带的磁带头绝对不会左移；2. 在任何时候，第一个磁带的内容形式是，x1#x2#.#xn#y，其中n>=0，每个xiÎL，且各不相同，y是L的另一个元素的前缀；3. 对于每个xÎL，x最终作为其中的某个xi出现在第一个磁带上。根据上面的定义，如果L是一个有限语言，图林机枚举完所有L中的字符串后，或者停机，或者继续移动，不会在第一个磁带上打印任何内容；如果L是一个无限语言，图林机枚举L的过程不会停止。上面的定义显然是一种合理的形式化“枚举集合元素”这个概念的方法。定义10.1说明能够被图林机接受的语言是递归可枚举语言，而这个名称隐含了递归可枚举语言是能够被图林机枚举的

11、语言，证明的思路是简单的，但是详细证明有些繁琐。一方面，如果存在图林机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Í&

12、#229;*是递归可枚举当且仅当L能够被图林机枚举。证明：假设T是枚举L的图林机，构造接受L的图林机T1如下。T1的磁带比T多一个，第一个磁带是增加的那个磁带，作为输入磁带，然后T1模拟T，每当符号#输出在第二个磁带上，T1暂停，检查新输出的字符串是否与第一个磁带上的输入字符串相同，如果相同，T1停机，如果不同，继续上面的“枚举-比较”过程。显然，T1接受且只接受属于L的字符串。更具体而言，T1开始完全模仿T的动作，忽略第一个磁带，直到输出符号#，则只考虑第一个磁带和第二个磁带，忽略其他磁带，如果不匹配，则回到初始格局。反过来，如果T接受L，我们构造一个3带图林机T1枚举L。第一个磁带是输出磁

13、带，第二个磁带用于生成å*上的每个字符串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上的两步移

14、动，并生成a，模拟T在a上的一步移动；第三趟扫描，T1模拟在L上的三步移动，模拟在a上的两步移动，生成b，模拟在b上的一步移动。第i趟扫描完成后，第二个磁带的内容的形式如下，其中字符串后面的1的数目表示T1处理该字符串所用的步数。x是规范顺序中的第i个字符串。在下一趟扫描中，T1给第二个磁带上的每个字符串增加一个1，即增加一次移动，然后复制到第三个磁带，模拟T处理这个输入字符串的规定数目的前面过程，然后擦掉第三个磁带。如果T停机，T1将这个字符串复制到第一个磁带，并添加符号#，第二个磁带上的内容都模拟完后，添加规范顺序中的下一个字符串（次处是x的下一个字符串）到第二个磁带，并添加一个1，复制到

15、第三个磁带，然后类似上面的处理。我们没有明确写出T1完成这些动作需要的簿记装置，但是它们能够很直观地实现，显然每个被T接受的字符串最终会出现在T1的第一个磁带上，且只有这样的字符串出现在上面。定理10.5证明的第二部分，应该注意，尽管å*上的字符串按照规范顺序出现在第二个磁带上，但是L中的字符串不是按照规范顺序列举在第一个磁带上。如果给予T更强的假设，我们能够很容易构造出按照规范顺序列举接受字符串的图林机。这个更强的假设是，如果T不仅接受L，而且识别L。反过来可以说，如果存在图林机按照规范顺序列举枚举L，则L是递归语言。定理10.6 L是递归语言当且仅当存在一个图林机按照规范顺序枚举

16、L。证明：留作练习10.7。练习中还讨论了根据图林机可计算函数得到的一些递归可枚举语言的一些性质。10.3 非递归可枚举语言我们前面讨论的比较简单的计算模型，FA和PDA，能够接受特定类型的语言，发现了一些它们无法接受的语言。对于图林机，我们也要研究是否存在不能接受的语言，但是由于不存在图林机的泵引理，因此图林机的这个问题要难得多。Church-Turing论题预示了这一点，如果一个想象得到的算法能够被图林机实现，那么它不太可能必须遵循一些相似于FA和PDA泵引理的规律性约束，因为图林机接受语言的能力太灵活了。我们很快将能够展示一个不是递归可枚举的语言。当然，并不是一定先有一个构造性证明说明这

17、种语言一定存在，然后才能讨论这种语言。但是先构造一个这种语言具有下面的好处：首先，证明的梗概很容易从直觉出发得到理解；其次，它表明不仅存在非递归可枚举语言，而且更严格地讲，大多数语言都是非递归可枚举的；第三，它引入了一种特别的方法，“对角线参数法”（diagonal argument），我们在后面章节还会用到这个方法，它是一个很有効的寻找一组特殊参数的方法。方法的思路很简单，如果存在的语言比图林机的个数多得多，那么就一定存在与图林机无关的语言。显然，存在无限多的语言和图林机，因此，为了得到一个精确的论证，我们需要定义一个精确比较两个无限集合大小的方法。说两个有限集合大小相等不困难，如果比较方法

18、得当，它还可以推广到更广泛的情况。为什么说集合a,b,c和x,y,z具有相同的规模？当然，一个原因是它们的元素都是3个，但是这种方法无法推广到无限集合，因此我们需要的方法是直接比较，而不是具体统计集合元素的个数。一个好的比较上面两个集合的方法是定义一个双射函数，函数定义域是一个集合，值域是另一个集合，这个方法很容易推广到任意的集合上。上面的思想陈述如下：如果存在一个从集合A到集合B的双射，则称A和B的大小相同。集合的大小相同是一个等价关系（参见练习10.26a），因此具备自反、对称和传递等性质。尽管我们避免象谈论数量那样谈论集合的大小，但是我们希望能够像比较数量那样比较集合的大小。比如说集合p

19、,q,r,s,t比a,b,c大，这是因为两个集合间存在一个一一映射，因此一个集合的大小与另一个集合的子集的大小相等，而集合本身大于或等于它的子集。显然，这个方法也可以推广到无限集合。实际上，不仅存在某些无限集大于另一些无限集，而且无限集有着许多不同的规模（参见练习10.18和10.26）。本节，我们只需要区分两类无限集，一类是与自然数集N大小相同的无限集，另一类是比自然数集大的无限集。（本文的自然数集包括0）定义10.3 如果存在一个从自然数集到集合S的双射，那么集合S称为可数无限集。如果S是可数无限集或有限集，那么S称为可数集，或可数的。一个不可数的集合，称为不可数无限集，或不可数集。说函数

20、f: N®S是一个双射函数意味着满足下面三个条件：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中的任意一个元素，都可以利用这个函数在列表中发现该元素；第二种，我们说“列举”，并没有说明

21、一个明确的算法来“列举”，仅仅说明了存在一个双射函数，也没有说明发现或计算这个函数的算法。注意，任意两个可数无限集的大小相同，如果事实上无限集的规模有很多种，那么所有的不可数集不可能是同一个规模，而且任何一个不可数集的规模大于任何一个可数集。这个结论不是很明显，可以从下面的事实推论得到。引理10.1 每个无限集都有一个可数无限子集。证明：我们证明如果S是一个无限集，那么存在一个从自然数集N到S的子集的双射f。下面，我们逐个整数定义f的映射。因为S是无限集，则至少存在一个元素，选择这个元素，并定义为f(0)。假设这个过程进行到了第n步，从S中选择了n个不同的元素，分别定义为f(0), f(1),

22、 ., 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的所有元素，还

23、含有一些其他元素。即存在一个从N到S的真子集的双射，如果它们是有限集，显然S大于N，但对于无限集，不能得出同样的结论，看起来似乎不符合直接，但它在数学意义上是正确的（参见练习10.13）。对于无限集，可能既存在从一个集合到另一个集合的真子集的双射，也存在到另一个集合自身的双射。下面的结论将给出一大类可数无限集，它的含义是可数个可数集的并集仍然是可数集。定理10.7 设S0, S1, .是可数集，那么它们的并集S=也是可数集。证明：我们假设所有的集合Si中没有空集（如果需要，可以重新命名），我们描述一种列举这个并集中所有元素的方法。每一行列举一个集合Si，第一行是集合S1，第i行是集合Si，得到

24、一个二维数组如下。其中，由于Si可以是有限集或无限集，因此每行的长度可能不同，现在考虑图10-1所示的一个列举路线。显然，这个路线能够包含进并集S的每个元素至少一次，如果元素s出现在多个Si中，则路径将多次包含这个元素。我们定义函数f如下：f(i)=则f是一个双射函数，如果S是有限的，是从1.m到S的双射函数，否则是从N到S的双射函数。由于有限个可数集的并集是S的子集，因此有限个可数集的并集也是可数集。例子10.1 S=N´N是所有自然数二元对组成的集合，S是可数集。分析：容易根据定理10.7得到S是一个可数集，因为而每个集合m´N都是可数集，因为存在双射函数fm: N&#

25、174;m´N, fm(n)=(m,n)。但是我们可以更直接地构造从N到N´N的双射函数f，采用类似定理10.7和图10-1的方法。我们先给出它的逆函数f-1，即从N´N到N的函数，也是图10-1用到的枚举方法。我们再次考察图中的路径，设j>=0，当路径循回到第j次，它命中的二元对(m,n)满足m+n=j，共有j+1个这样的二元对。特别地，如果当前二元对是(m,n)，m+n=j，则路径上包含所有(p,q)，p+q<j-1，和m个p+q=j。因此命中(m,n)之前共有如下数目的二元对被命中（参见练习2.7），1+2+.+(m+n-1)+(m+n)+m=(

26、m+n)(m+n+1)/2+m即f-1(m, n)=(m+n)(m+n+1)/2+m由此可以求得函数f，它被称为配对函数（pairing function），用在许多有关计数的讨论中。上面的结论容易推广到任意的可数集上，即对任意的可数集S，S´S仍然是可数集。例子10.2 对任意的有限集å，包含å上任意字符串的集合å*是可数集。分析：å*=，其中，ån是所有长度为n的字符串组成的集合，它是有限集，因此也是可数集，根据定理10.7，显然å*是可数集。例子10.3 设T是所有图林机组成的集合，RE是所有递归可枚举语言组成的集合，

27、为了讨论方便，不是一般性，我们假设所有图林机的状态都来自集合Q，所有的磁带符号来自集合S，特别地，所有递归可枚举语言的字母表都是S的子集。我们可以利用定理10.7显示集合T是可数的（参见练习10.17），此处，我们9.7节定义的编码函数来说明。编码函数e: T®0,1*是一个一一映射函数，也是从T到0,1*的某个子集的双射。既然0,1*是可数的，因此它的子集也是可数的，则T也是可数的。现在说明RE也是可数的。根据定义，一个递归可枚举语言能够被某个图林机接受，对每个递归可枚举语言L，设t(L)是接受它的图林机。因此，得到一个从RE到T的函数t，由于每个图林机只能接受一种语言，因此t是一

28、一映射的，既然T是可数的，利用类似上面的讨论知道RE也是可数的。例子10.3提供了我们需要的结果的一半，现在我们已经证明了递归可枚举语言组成的集合是可数的，如果能够说明所有语言组成的集合是不可数的（或共有不可数的语言），那么就说明了存在非递归可枚举语言。有关不可数集合的最著名的证明方法是经典的对角参数法，它由19世纪德国数学家Georg Cantor提出，它证明了实数集是不可数的。参见练习10.20，或参考任何一本关于集合理论的书籍。下面的结论也来自Cantor，可以用类似的方法证明。定理10.8 S是任意一个可数无限集，则S的幂集2S是不可数无限集。特别地，对每个非空有限字母表å，

29、å上的所有语言组成的集合是不可数的。证明：我们可以分别构造从N到S和从2N到2S的双射，因此只要证明了2N是不可数的，就证明了2S是不可数的。使用反证法。假设2N是可数集无限集，则可以列举N的所有子集如下，2N=A0, A1, .现在定义N的一个子集A=iÎN | iÏAi，既然N的每个子集都在上面的列举中，则存在自然数I，使得A=AI。考察命题IÎAI。如果命题为真，则得到IÏAI，矛盾。如果命题为假，即IÏAI，则符合AI成员的要求，得到IÎAI，矛盾。即如果假设2N是可数的，则存在一个集合AÍN和自然数I，呈

30、现出下面的矛盾，1. 如果IÎA，则IÏA；2. 如果IÏA，则IÎA。因此，假设不成立，2N是不可数集。å上所有语言组成的集合是2å*，而å*是可数无限集，因此å上所有语言组成的集合不可数。推论10.1 字母表0,1上非递归可枚举语言的集合是不可数的，特别地，至少存在一个非递归可枚举语言。证明：根据例子10.3，所有的递归可枚举语言组成的集合S1是可数的，根据定理10.8，0,1上所有语言组成的集合不可数S，根据练习10.15，不可数集合与可数集合的差集是不可数的。定理10.8的证明比较难于理解，主要的难点是集合

31、A的定义，构造出A的定义后，很容易想到考察命题IÎAI。那么构造A的思路怎么产生的呢？A的定义方法来自称为对角参数法的证明方法。我们使用了一个几何术语表示这个思路。考察如下一个无限的两维数组，行下标记号为i，列下标记号为j，其中第(i,j)项条目是命题iÏAj的真值表。（参见304页）图中给对角线上的条目加了下划线，集合A由这些对角线上条目iÏAi的值为真的i组成，我们在下一节和后面章节还会使用这个方法。你也许不清楚定理10.8在整个计算理论中的意义。它的结论表明存在不能被图林机接受的语言，即没有足够多的图林机处理所有的语言，预示了通用图林机的计算能力还不够强大。

32、图林机可以被编码成符号串，而符号串的个数是可数的，因此无论我们如何描述一个语言，或描述一个接受它的机器，或其他什么方法，只要这个描述方式是可以编码的，就一定存在不能描述的语言。即一定存在非常复杂、非常大的语言，它们无法被精确描述。但是我们不必将这个定理看成一个负面结果，毕竟，到目前为止，凡是我们感兴趣的语言、凡是能够被以某种方式精确描述的语言都能够被图林机接受。但是到下一节，我们会看到上面结论不一定成立。10.4 非递归可枚举语言的实例知道了存在不可数的非递归可枚举语言并不意味着有了发现这种语言的方法。根据Church-Turing论题，一个不能被图林机接受的语言也不能被任何可以想象到的算法过

33、程所识别。因此需要一个“狡诈”的方法来构造这个语言，“狡诈”是描述前一节“对角线参数法”的合适的词，本节我们还要使用这个方法。在前一节，我们使用了一个矩阵，它的行代表整数i，它的列代表集合Aj，并用集合的包含运算定义(i,j)条目。此处的论证更有创造性，考虑图林机集合是一个可数集，因此存在一个所有图林机的列举T0, T1, .，考虑每个图林机的编码e(Ti)Î0,1*，e是9.7节定义的编码函数。重复前面的对角线参数法，用e(Ti)代替i，用Tj代替Aj，用“e(Ti)不被Tj接受”代替“iÏAj”。然后同样选择对角线为真的元素组成集合，导出矛盾。下面的定义与前面稍有区别，

34、部分因为没有明确应用图林机集合的可数性，更主要因为它将用于后面章节去考察一些更大的语言。定义10.4 NSA（not self-accepting，非自接受集）是0,1*的一个子集，定义如下，NSA=NSA1ÈNSA2其中，NSA1=wÎ0,1* | w是某个图林机T的编码，且T不接受wNSA2=wÎ0,1* | w不是任何图林机的编码令SA（self-accepting）是NSA的补集，SA=wÎ0,1* | w是某个图林机T的编码，且T接受w。定理10.9 语言NSA不是递归可枚举集。证明：类似前面的对角线参数法，此处也用反证法。假设NSA是递归可枚

35、举集，则存在一个图林机T0接受语言NSA，即L(T0)=NSA。即T0接受字符串x当且仅当wÎNSA。现在令w0=e(T0)，考虑命题“T0接受w0”，如果命题真，则w0ÎNSA，又根据NSA的定义，T0不接受w0，矛盾。如果命题为假，则w0ÏNSA，则w0ÎSA，根据SA定义，T0接受w0，矛盾。因此，我们的假设不成立，即NSA不是递归可枚举集。同样，很多人想知道定理10.9在计算理论中的意义。尽管我们知道存在很多非递归可枚举的语言，但NSA是一个人工设计的语言，我们不知道这种人工设计的“奇怪”语言恰好是其中一个非递归可枚举语言有什么意义。但事实上，定

36、理10.9带来许多重要的结论，我们将用它解决一些特定的问题，包括很多听起来不是“人工制造”的问题，证明这些问题的无解性。现在，我们用它设计另一个例子，这个例子澄清了递归可枚举与递归之间的关系。定理10.10 SA是递归可枚举集而不是递归集。即尽管存在图林机Tsa接受SA，但至少存在一个不属于SA的输入字符串使得Tsa无限循环。证明：定理的第二部分可以从定理10.3和定理10.9很容易地得到。如果SA是递归集，那么它的补集NSA也是一个递归集，因而与定理10.9矛盾。因此，证明的关键是构造接受SA的图林机Tsa。Tsa首先确定输入的字符串w是否是某个图林机T的编码e(T)（编码具有特殊的格式），

37、如果不是，Tsa崩溃。如果是，即w=e(T)，则Tsa模拟T处理w的过程，当T停机，则停机。9.7节我们构造的通用图林机Tu已经具备了模拟其他图林机动作的能力，它的输入是e(T)e(w)=we(w)，这意味着Tsa可以构造成T1Tu的形式，问题转换成T1的构造，它完成的功能是如果输入字符串w不是e(T)的形式，则崩溃，否则在磁带上留下we(w)，然后停机。一个字符串w是某个图林机T的编码e(T)，它必须以字符串0k1开头，随后是图林机移动的编码，因此满足下面的正则表达式，0+1(0+1)5)+另外，由于是确定型图林机，因此每个状态-符号组合只能有一个转移动作，即如果5元组的前两部分相同，那么后

38、三部分也应该相同；第三，5元组的第5部分必须是0, 00或000，表示正确的移动方向。最后，没有5元组允许第一部分为0，因为图林机不允许从停机状态上移动。任何一个满足上面条件的字符串是某个图林机的编码，尽管这个图林机可能完全没有有意义的动作（比如立即崩溃）。除了第二个条件，其他条件都很容易测试。为了测试第二个条件，T1执行一个循环，在第i趟循环，T1在第i个5元组之后搜索与第i个元组的前两部分相同的5元组。这个过程完全相同于图9-19中作为通用图林机一部分的“search”部件，此处不再详述。如果上面4个w是e(T)形式的条件中有一个没有满足，则T1崩溃，如果都满足了，则T1在磁带上恢复w，并

39、在其后添加字符串e(w)。由于w已经是0和1的编码的形式，因此生成e(w)的方法很直观。它开始于11，如果0和1分别对应字母表S中的符号ai和aj，那么w中的每个0编号为0i+1，每个1编号为0j+1，每个那样字符串后面添加一个1，比如，00101编码成110i+110i+110j+110i+110j+11T1将we(w)留在磁带上以后，并把磁带头移动到0号格子，然后停机。-END-10.1 递归可枚举和递归相对有限自动机和下推自动机对应的语言是正规语言和上下文无关语言，Turing机对应的语言有多个，如递归可枚举和递归语言（这两个语言的命名不好理解）。许多知识点，或称为定义和定理，难度在于证

40、明它们，重点讲述基本知识、不要证明或只作说明性证明，不严格证明。定义10.1 语言L和TM T，如果L(T)=L，则称T接受L。如果T能够计算L的特征函数c_L: å*®0, 1，则称T识别（或判定）L。即如果T识别L，则任给字符串x，T都会停机。TM T会不会对任意的字符串停机，与要接受的语言无关，是T本身的固有特征，因此TM T可以分成两大类，对任意字符串都停机的TM和对部分字符串停机的TM，前者接受的语言是递归语言，后者接受的语言是递归可枚举语言，或说如果存在一个TM T接受L，则称L是递归可枚举语言（recursively enumerable）；如果存在一个TM

41、T识别L，则称L是递归语言（recursive）。显然任何一个递归语言都是递归可枚举语言，但递归可枚举语言不一定是递归语言。因为可能存在一个字符串不属于某个递归可枚举语言，在判定过程中出现无限循环，从而永远无法判定。定理10.1 如果语言L被一个非确定型TM T接受，且T的每个可能出现的移动序列要么导致停机，要么导致崩溃，则L是递归语言。证明：定理10.2 语言L1和L2是递归可枚举的，则它们的并集和交集也是递归可枚举的。证明：构造法。定理10.3 如果语言L是递归的，则它的补集也是递归的。定理10.4 如果语言L是递归可枚举的，它的补集也是递归可枚举的，则L是递归的。证明：修改定理10.2的

42、方法。10.2 枚举一个语言定义10.2 T是一个有k个磁带的TM（k>=2），如果T满足下面的条件，则称T枚举语言L：第一个磁带的带头没有左移任何时刻，第一个磁带的内容都形如：x1#x2#.#xn#yxiÎL，各不相同，y是一个不同于xi的L中的元素的前缀。L中的每个元素，最终都会以某个xi的形式出现在第一个磁带上。定理10.5 语言L是递归可枚举的当且仅当它能够被某个TM枚举。证明：？定理10.6 L是递归语言当且仅当存在一个TM T按照canonical序枚举它。canonical序：长度短的优先，如果长度相等，则按字母顺序排列。10.3 不是所有的语言都是递归可枚举的定

43、义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: T'®0, 1*，而集合0, 1*是可数的，同样可以构造从RE到T'的双射函数。如果我们能够证明所有语言构成的集合是不可数的，而递归可枚举语言的集合却是可数的，则表