培训课件非计算理论

计算理论和DNA计算孟大志2004.9第一部分：计算理论电子计算机的计算理论可以分为以下三个部分：1、自动机理论——什么是计算？这是一个没有定义的熟悉概念，因此可以用计算模型来描述“计算”。自动机理论和形式语言是对电子计算机的数学模型的定义和性质的研究。2、可计算性理论——什么是可计算的？以上定义的计算来讨论什么是电子计算机可以计算的。例如确定一个命题的真伪是计算机不能解决的。3、计算复杂性理论——什么是难计算的？在可计算的问题中，难计算的概念是什么？哪些问题是难计算的？美国柯朗研究所的七个21世纪悬赏问题的第一个问题： NP=P？DNA计算将对以上三个基本问题提出新的理解！有穷自动机例：M1有有穷状态：起始状态q1，非接受状态。接受状态q2，结束于q2时称“接受”，否则称“不接受”状态q3，非接受状态。状态及其转换字符图：q3q2q1M1接受以1结尾的任意0、1串，以及100、0100、110000、，以及最后一个1后有偶数个0的0、1串，此外全拒绝。01100,1定义2.1

有穷自动机是一个5元组(Q,∑,δ,q0,F),其中1）Q是一个有穷集合，叫做状态集。2）∑是一个有穷集合，叫做字母表。3）δ：Qx∑－>Q是转移函数。4）q0∈Q是起始状态。5）FQ是接受状态集（终结状态系）。可以把M1形式地写成M1＝(Q,∑,δ

,q1,F)，其中

1)Q＝{q1,q2,q3} 2)∑＝{0,1}。 3)δ由表2－1给出。 4)q1是起始状态。 5)F={q2}。表2－101q1

q1

q2q2

q3

q2q3

q2

q2设A是机器M接受的全部字符串集，称A是机器M的语言，记作L(M)=A。又称M识别A或M接受A。在上面的例子中，令 A＝{ω|ω

至少含有一个1并且在最后的1后面有偶数个0}那么，L(M1)=A,或者等价地说，M1识别A。例2.5图2-9给出机器M5，它的输入字母表有4个符号， ∑＝{<RESET>,0,1,2}。我们把<RESET>作为一个符号。

M5以模3的方式记录它在输入串中读到的数字之和。每次读到符号<RESET>，它将计数重新置0。如果和模3等于0，换句活说，和是3的倍数，则M5接受。q0000,<RESET>2,<RESET>1,<RESET>212q21q1设M＝(Q,∑,δ,q1,F)是一台有穷自动机，ω=ω1ω2……ωi是字母表∑上的一个字符串。如果存在Q中的状态序列 r0,r1,……,rn,满足下述条件：r0=q0δ(ri,ωi-1)=ri-1i=0,1,……,n-13)rn

∈F则M接受ω。如果A={ω|M接受ω}，则称M识别语言A。定义2.7如果一个语言被一台有穷自动机识别，则称它是正则语言。取例2.5中的机器M5，令ω是字符串 10<RESET>22<RESET>102由于当M5对ω计算时进入的状态序列为

q0,q1,q1,q0,q2,q1,q0,q0,q1,q0它满足上述3个条件，根据计算的形式定义，M5接受ω。M5的语言是：L(M5)={ω|除<RESET>将计数重新置0之外，ω中所以符号之和模3等于0}因为M5识别这个语言，所以它是正则语言。 例2.8例如，假设字母表是{0,1},所考虑的语言由所有含有奇数个1的字符串组成。qoddqevenqoddqeven图2-10两个状态qeven和qodd图2-11说明如何重新安置可能性的转移qevenqodd图2-12增加起始状态和接受状态00001111正则运算在计算理论中，对象是语言，工具包括为处理语言专门设计的运算。定义语言的3种运算，称作正则运算，并且使用这些运算来研究正则语言的性质。定义2.10设A和B是两个语言，定义正则运算并、连接和星号如下：并：连接：星号： 因此空串总是A*的元素。定理2.12正则语言类在并运算下封闭。定理2.13正则语言类在连结运算下封闭。非确定性是确定性的推广，因此每一台确定型有穷自动机自动地是一台非确定型有穷自动机。如图2-14所示，非确定型有穷自动机可能有一些另外的特征。图2-14非确定型有穷自动机N1q2q3q1

q40,10,1110,εq1q3q2q1q3q1q2q3q4q4q4

q4q1q2q3q1q3

q4开始————0

——1————0

——1

——1

——0图2-16N1关于输入010110的计算称P(Q)是Q的幂集，把∑ 记作 。定义2.17非确定型有穷自动机是一个5元组(Q,∑，，q0,F),其中1)Q是有穷的状态集；2)∑是有穷的字母表；3) 是转移函数。4) 是起始状态。5) 是接受状态集。例2.18回想一下NFAN1：q2q3q1

q40,10,1110,εN1的描述形式是(Q,∑,δ，q1,F)，其中1)Q＝{q1,q2,q3,q4},2)∑={0,1},3)δ

由表2－2给出,4)q1是起始状态，5)F={q4}.表2－2NFAN1的δ

01

εq1{q1}{q1,q2}q2{q3}{q3}

q3{q4}

q4{q4}{q4}NFA计算的形式定义也和DFA计算的类似。设N=(Q,∑，，q0,F)是一台NFA，是字母表∑上的一个字符串。如果能把写成=y1y2…ym这里每一个yi是的一个成员，并且存在Q中的状态序列r0,r1,……,rm满足下述3个条件：1)r0=q02)ri+1(ri,yi+1),i=0,1,……,m-13)rmF则称N接受如果两台机器识别相同的语言，则称它们是等价的。定理2.19每一台非确定型有穷自动机都有一台等价的确定型有穷自动机。定理2.19是显然的，用例2.18说明，此时的DFA用红字字表示。 N: Q:q1,q2,q3,q4; F:q4; q0=q1; M: Q’=r0,r1,……,r7; F’=r5,……,r7;q1q2q1q3q3

q4

q4

q4r0r1r2r3r4r5r6r7001021110定理2.19说明每一台NFA都能够被转换成一台等价的DFA。于是，非确定型有穷自动机给出另一种刻画正则语言的方式。我们把这一事实陈述为定理2.19的一个推论。推论2.20一个语言是正则的，当且仅当有一台非确定型有穷自动机识别它。定理2.22正则语言类在并运算下封闭。定理2.23正则语言类在连结运算下封闭。定理2.24正则语言类在星号运算下封闭。定理2.22-2.24的证明思路是简单的。两个N1,N2构造一个N与之对应。1)并：每个N1,N2的起始状态分成两支，一个进入下一个态，一个进入

ε从而进入另一个向上起始态。2)连结：N的起始态在N1的起始态，而到N1的终态时进入N2的起始态。3)星号运算与2类似，任进入自己的任一起始态。在正则表达式中，先做星号运算，然后做连结运算，最后做并运算，除非用括号改变这种惯常的顺序。正则表达式的形式定义：定义2.26称R是一个正则表达式，如果R是 1)a,这里a是字母表∑中的一个元素； 2)ε

3)Φ

4) ，这里R1和R2是正则表达式； 5) ，这里R1和R2是正则表达式； 6)(R1*),这里R1是正则表达式。设R是任意的正则表达式，有下述恒等式。它们能很好地检查你是否理解正则表达式的定义。把空语言加到任一语言上不改变这个语言。把空串加在任一字符串上不改变这个字符串。但是，交换前面两个恒等式中的和可能导致恒等式不成立。 可能不等于R. 连结是二元运算，缺一个元不能映到任何串，于是结果没有串。例如，如果R＝0，那么L(R)={0}，而

可能不等于R.例如，如果R＝0，那么L(R)={0}，而定理2.28一个语言是正则的，当且仅当可以用正则表达式描述它。定理2.37(泵引理)设A是一个正则语言，则存在一个数p(泵长度)使得， 如果s是A中任一长度不小于p的字符串，那么s可以被分成三段， s=xyz,满足下述条件： 1)对每一个i≥0,xyiz∈A 2)|y|>0 3)|xy|p第三章上下文无关语言上下文无关文法首先被用来研究人类语言。在名词、动词、介词以及它们的短语之间的关系中存在自然的递归。上下文无关文法的一个重要应用领域是程序设计语言的规范说明和编译。与上下文无关文法有关的一类语言叫做上下文无关语言。上下文无关文法上下文无关文法例G1： A－> 0A1 A－> B B－> #字符串由变元和另一种叫做终结符的符号组成。变元经常用大写字母表示。终结符类似于输入符号，经常用小写字母、数字和特殊符号表示。一个变元被指定为起始变元，通常它出现在第一条规则的左边。能够用文法描述语言，用下述方式生成语言中的每一个字符串。1)写下起始变元。它是第一条规则左边的变元，除非另有指定。取一个写下的变元，并找到以该变元开始的规则。把这个变元替换成 这条规则右边的字符串。3)重复步骤2，直到没有变元为止。上下文无关文法(称作G2)的另一个例子，描述了一个英语片断： <句子>－><名词短语><动词短语><名词短语>－><复合名词>|<复合名词><介词短语><动词短语>－><复合名词>|<复合名词><介词短语> <介词短语>－><介词><复合名词> <复合名词>－><冠词><名词><复合动词>－><动词>|<动词><名词短语> <冠词>－>a_|the_ <名词>－>boy_|girl_|flower_ <动词>－>touches_|likes_|sees_ <介词>－>with_下面是第一个字符串的派生：<句子>＝><名词短语><动词短语> ＝><复合名词><动词短语> ＝><冠词><名词><动词短语> ＝>a_<名词><动词短语> ＝>a_boy_<动词短语> ＝>a_boy_<复合动词> ＝>a_boy_<动词> ＝>a_boy_sees_定义3.1上下文无关文法是一个4元组(V,∑,R,S)，这里 1)V是一个有穷集合，称作变元集。 2)∑是一个与V不相交的有穷集合，称作终结符集。 3)R是一个有穷的规则集，每一条规则是一个变元和一个 由变元和终结符组成的字符串。 4)SV是起始变元。设u,v和w是变元和终结符的字符串，A－>w是文法的一条规则，称uAv生成uwv,记作uAv＝>uwv。如果u=v，或者存在序列u1,u2,……,uk,使得 u=>u1=>u2=>……=>uk=>v其中k0,则记作uv。该文法的语言是在文法G2中，V={<句子>,<名词短语>,<动词短语>, <介词短语>,<复合名词>,<复合动词>, <冠词>,<名词>,<动词>,<介词>}∑＝{a,b,c,……,z,_}，符号_表示空白，它放在每一个字a,boy等后面，因而所以的字不会连在一起。乔姆斯基范式定义3.5一个上下文无关文法为乔姆斯基范式，如果它的每一个规则具有 如下形式：

A->BC A->a

这里，a是任意的终结符，A,B和C是任意的变元，但B和C不能是 起始变元。此外，允许规则S－>ε，其中S是起始变元。定理3.6任一上下文无关语言都可以用乔姆斯基范式的上下文 无关文法产生。下推自动机定义3.8下推自动机是一个6元组（Q，∑，Γ，δ，q0

，F），这里Q，∑，Γ和F都是有穷集合，并且

1）Q是状态表

2）∑是输入字母表

3）Γ是栈字母表

4）δ：Q×∑ε×Γε→р(Q×Γε)是转移函数 5）q0єQ是初始状态

6）FQ是接受状态一台下推自动机M=（Q，∑，Γ，δ，q0

，F）的计算如下。它接受输入ω，如果能够把ω写成ω=ω1

ω2…ωm，这里每一个ωi∈∑ε，并且存在状态序列r0，r1，…，rm∈Q和字符串序列s0，s1，…

，sm∈Γ*满足下述3个条件。字符串s0，s1，…

，sm是M在计算的接收分支中的栈内容序列。

1）r0=q0且s0=ε，该条表示M从起始状态和空栈开始。

2）对于i=0，…，m-1，（ri+1，b）∈δ（ri,ωi+1,a），其中si=at,si+1=bt,a,b∈Γε和t∈Γ*。该条说明M在每一步都完全按照当时的状态，栈顶符号和下一个输入符号动作。

3）rm∈F，该条说明在输入结束时出现一个接受状态。例3.9下面是先前叙述过的那台识别语言{0n1n|n≥0}的PDA的形式定义。令M1=（Q，∑，Γ，δ，q1

，F），其中 Q={q1，q2，q3，q4} ∑={0，1}

Γ={0，$}

F={q1，q4}

δ由表3-1给出，表中空白项表示Φ。输入01ε栈0$ε0$ε0$εq1|(q2,0)||(q2,0)|q2|(q2,0)||(q3,0)|q3|(q3,0)||(q4,0)|q4q1q2q3q40，ε→01，0→ε1，0→εε，ε→$ε，$→ε图3-6识别{0n1n|n≥0}的PDAM1的状态图3.2.3与上下文无关文法的等价性 定理3.12

一个语言是上下文无关的，则存在一台下推自动机识 别它。 引理3.15如果一个语言被一台下推自动机识别，则它是上下文 无关的。

推论3.18每一个正则语言是上下文无关的。3.3非上下文无关语言定理3.19（关于上下文无关语言的泵引理）如果A是上下文无关语言，则存在数p（泵长度），使得A中任何一个长度不小于p的字符串s能够划分成5段，s=uvxyz，满足下述条件：

1）对于每一个i，uvixyiz∈A， 2）|vy|>0， 3）|vxy|≤p。 当s被划分为uvxyz时，条件2称v或y不是空串。否则定理自动成立，但毫无意义。条件3称v、x和y三段在一起的长度不超过p。这个技术性条件在证明某些语言不是上下文无关语言时是有用的。第二部分可计算性理论第四章丘奇—图灵论题图灵机这个模型是由图灵（AlanTuring）在1936年第一次提出的，故称作图灵机。图灵机与有穷自动机相似，但图灵机有一个无限的存储。下面是由穷自动机与图灵机之间的区别：1）图灵机在带子上既能写也能读。2）读写头既能向左移也能向右移。3）带子是无限长的。4）进入拒绝和接受状态将立即停机。图灵机的形式定义定义4.1一个图灵机是一个7元组（Q，∑，Γ，δ，q0，qaccept，qreject），其中：Q，∑，Γ都是有穷集合，并且

1）Q是状态集

2）∑是输入字母表，不包括特殊空白符号“_”。

3）Γ是带字母表，其中：_∈Γ，∑Γ。 4）δ：Q×Γ→Q×Γ×{L，R}是转移函数。

5）q0∈Q是起始状态。

6）qaccept∈Q是接受状态

7）qreject∈Q是拒绝状态，且qaccept≠qreject。图灵机M=（Q，∑，Γ，δ，q0，qaccept，qreject）的计算方式如下：开始时，M以最左边的n个方格接受输入ω=ω1ω2…ωn

∈∑*，带的其余部分是空白（即填以空白符）。读写头从最左边的带方格开始运行。注意，∑不含空白符，故出现在带上的第一个空白符表示输入的结束。M开始运行后，计算根据转移函数所描述的规则进行。如果M试图将读写头从带的左端点再向左移出，即使转移函数指示的是L，读写头也停在原地不动。计算一直持续到它进入接受或拒绝状态，此时停机。如果二者都不发生，则M永远运行下去。图灵计算时，当前状态、当前带内容和读写头当前位置会发生改变，这三项构成的整体叫做图灵机的格局。uqv表示如下格局：当前状态是 q，当前带内容是uv，读写头的当前位置是v的第一个符号，带上v的最后符号以后的符号都是空白符。现在对图灵机计算方式进行形式化。如果图灵机能合法的从格局C1一步进入C2，则称格局C1产生格局C2，这个概念的形式定义如下：设a,b和c是Γ中的复合，u和v是Γ*中字符串，qi和qj是状态，则uaqibv和uqjacv是两个格局。如果转移函数满足δ(qi,b)=(qj,c,L),则说

uaqibv产生uqjacv这说明了图灵机左移的情形，下面是右移的情形。如果δ(qi,b)=(qj,c,R),则说 uaqibv产生uacqjv当读写头处于格局的两个端点之一时，会发生特殊变化。对于左端点，如果转移时向左移动，则格局qibv产生格局qjcv(因为不准机器从带的左端点移出)；如果转移时向右一定，这个格局产生cqjv。对于右端点，格局uaqi等价于uaqi_，因为已假设：在带子上格局没有描述的部分都是空格。这样，就能像以前一样处理了，因为此时读写头已不再处于右端点。M在输入ω上的起始格局是格局q0ω,表示机器处于起始状态q0，并且读写头处于带子的最左端位置。在接受格局里，状态是qaccept；在拒绝格局里，状态是qreject。接受和拒绝状态都是停机状态，它们都不再产生新的格局。图灵机M接受输入ω，如果存在格局的序列C1,C2,……,Ck使得： 1)C1是M在输入ω上的起始格局， 2)每一个Ci产生Ci+1， 3)Ck是接受格局。M接受的字符串的全体称为M的语言，记为L(M).定义4.2如果有图灵机识别一个语言，则称该语言是图灵机可识别的。定义4.3称一个语言是图灵可判定的，或简单地讲，是可判定的， 如果有图灵机判断它。对所有输入都停机的图灵机，它们永不循环。称这种机器为判定器。图灵可判定语言都是图灵可识别的，但某些图灵可识别语言不是可判定的。图灵机的例子：例4.4

现在描述TMM2，它识别的语言是所有由0组成、长度为2的方幂的字符串，即它判定语言A={02n|n≥0} M2＝”对于深入字符串ω”： 1)从左往右扫描整个带子，隔一个消去一个0。 2)如果在第一步之后，带子上只剩下唯一的一个0，则接受。 3)如果在第一步之后，带子上包含不止一个0，并且0的 个数是奇数，则拒绝。 4)让读写头返回带子的最左端。 5)转到第一步。下面给出M2=(Q，∑，Γ，δ，q1，qaccept，qreject)的形式描述：Q={q2,

q2,q3,q4,q5,qaccept，qreject}∑={0}

Γ={0,x,_}将δ描述成状态图如下。开始、接受和拒绝状态分别是q1，qaccept和qrejectq1q2q3q4qacceptqrejectq2o→Lx→Lx→Rx→Ro→x,R_→R_→Rx→Ro→_,R_→Rx→Ro→Ro→x,R_→R_→L在输入0000上运行的例子（格局）：q10000 _q5x0x_ _xq5xx__q2000 q5_x0x_ _q5xxx__xq300 _q2x0x_ q5_xxx__x0q40 _xq20x_ _q2xxx__x0xq3_ _xxq3x_ _xq2xx__x0q5x_ _xxxq3_ _xxq2x__xq50x_ _xxq5x_ _xxxq5_ _xxx_qaccept图灵机的变形其它形式的图灵机还有很多，例如有多个带子的或非确定性的。它们被称为图灵机模型的变形。原来的模型与它所以合理的变形有着同样的能力——识别同样的语言类。这种变化中的不变性称为稳健性。为了证明两个模型是等价的，只要证明它们能相互模拟即可。多带图灵机开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许同时进行读、写和移动读写头，其形式为：

δ：Q×Γk－>Q×Γk×{L,R}k此处k是带子的个数。表达式

δ(qi,a1,……,ak)=(qj,b1,……,bk,L,R,……,L)指的是：若机器处于qi状态读写头1到k所读的符号分别是a1,……,ak，则转移到状态qj，写下符号b1到bk，且按此式所指示的那样移动每个读写头。定理4.8每个多带图灵机都有一个与之等价的单带图灵机。推论4.9一个语言是图灵可识别的，当且仅当有多带图灵机识别它。非确定型图灵机在计算的任何时刻，机器可以在多种可能性中选择一种继续进行。它的转移函数具有如下形式：

δ：Q×Γ－>P3(

Q×Γ×{L,R,S}其计算是一棵树，不同分枝对应着机器不同的可能性。定理4.10每个非确定型图灵机都有一个与之等价的确定型图灵机。推论4.11一个语言是图灵可识别的，当且仅当有非确定型图灵机识别它。推论4.11一个语言是可判定的，当且仅当有非确定型图灵机判定它。枚举器使用术语递归可枚举语言来代替图灵机可识别语言。这个术语起源于称为枚举器的机器，它是图灵机的一种变形。枚举器是代言打印机的图灵机，图灵机将打印机当作输出设备，从而可以打印串。枚举器以空白输入带开始运行，如果不停机，它可能会打印出串的一个无限序列。枚举器E所枚举的语言是最终打印出的串的集合。而且，E可能以任意顺序生成这个语言中的串，可能还有重复。定理4.13一个语言是图灵可识别的，当且仅当有枚举器枚举它。算法的定义：希尔伯特问题：希尔伯特第10问题是要设计一个算法来测试多项式是否有整数根。他没有用算法这个术语，而用这样一句短语：“通过有限多次运算就可以决定的过程”。丘奇－图灵论题

算法的直觉概念 等于 图灵机算法

丘奇－图灵论题丘奇－图灵论题提出的算法定义是解决希尔伯特第10问题所必须的。证明了检查多项式是否有整数根的算法是不存在的。设 D＝{p|p是有整数根的x的多项式}本质上，希尔伯特第10问题是问：集合D是不是可判定的？答案是否定的。描述图灵机的术语：描述程度有三种： 第一种是形式描述，即详尽地写出图灵机的状态、转移函数等等，这是最低、最详细程度的描述； 第二种的描述程度要高一些，叫做实现描述，这种方法使用日常语言来描述图灵机的运行，如怎么移动读写头，怎么在带上存储数据等，这种程度的描述没有给出状态和转移函数的细节； 第三种是高水平描述，它也是使用日常语言来描述算法，但忽略了实现的模型。第五章 可判定性研究算法求解问题的能力。我们将证明：有些问题算法上能够求解，而另一些则不能。我们的目的 是研究算法可解性的局限。可判定语言： 例如，提出一个算法来检测一个串是否是一个上下文无关语言中的元素。这个问题与程序设计语言中的程序识别及编译有关。与正则语言相关的可判定性问题DFA接受问题，检测一个特定的自动机是否接受一个事先给定的串，此问题可表示为语言ADFA,它包含了所以DFA及其接受的串的编码，令

ADFA={<B,ω>|B是DFA,ω是串，B接受ω}问题“DFAB是否接受输入ω”与问题“<B,ω

>是否是ADFA的元素”是相同的。类似地，其它一些计算问题也可以表示成检查语言的成员隶属关系，证明这个语言是可判定的与证明这个计算问题是可判定是同一回事。下面定理将证明是可判定的，因而也就证明了问题“一个给定的有穷自动机是否接受一个给定的串”是可判定的。定理5.1

ADFA是一个可判定语言。可以对非确定型有穷自动机证明类似的定理。设

ANFA={<B,ω>|B是NFA,ω是串，B接受ω}定理5.2

ANFA是一个可判定语言。可以类似地检查一个正则表达式是否派生一个给定的串。设

AREX={<R,ω>|R是正则表达式,ω是串，R派生ω}定理5.3

AREX是一个可判定语言。有穷自动机语言的空性质测试。在以前的定理中，常常必须检查一个有穷自动机是否接受一个特殊的串。在下面的证明中，要检查一个有穷自动机是否根本不接受任何串。令

EDFA={<A>|A是一个DFA,且L(A)=Φ}定理5.4

EDFA是一个可判定语言。证明：DFA接受一个传当且仅当：从起始状态出发，沿着此DFA的箭头方向，能够到达一个接受状态。为检查这个条件，设计一个使用标记算法的TMM,此算法已在例4.14中使用过。T=“对于输入<A>，其中A是一个DFA: 1)标记起始状态。 2)重复下列步骤，直到所有状态都被标记。 3)对于一个状态，如果有一个到达它的转移是从某个已经 标记过的状态出发的，则将其标记。 4)如果没有接受状态被标记，则接受，否则拒绝。”检查两个DFA是否识别同一个语言是可判定的。设

EQDFA={<A,B>|A和B都是DFA,且L(A)=L(B)}定理5.5

EQDFA是一个可判定语言。与上下文无关语言相关的可判定问题下面描述两个算法，一个检查一个CFG是否派生一个特定的串，另一个检查一个CFG的语言是否为空。设

ACFG={<G,ω>|G是CFG，ω

是串，G派生ω}定理5.6

ACFG是一个可判定语言。现在讨论CFG语言的空性检查问题。如对待DFA那样，可以证明：检查一个CFG是否派生任何串是可判定的。设

ECFG={<G>|G是一个CFG，且L(G)＝Φ}定理5.7

ECFG是一个可判定语言。图灵可识别的可判定的

上下文无关定理5.8每个上下文无关语言是可判定的。四个主要语言类：正则的、上下文无关的、可判定的和图灵可识别的， 定理5.8在它们直接的关系图中画出了做后一条连线。 图5－2是这个关系图的示意图。正则图5－2语言类间的关系停机问题检查一个图灵机是否接受一个给定的串问题。类似于ADFA和ACFG，记之为ATM。但ADFA和ACFG是可判定的，ATM却不是。令

ATM＝{<M,ω>|M是一个TM，且接受ω}定理5.9

ATM是不可判定的。在证明之前，先来证明ATM是图灵可识别的。这样，定理5.9表面识别器确实比判定器更强大。要求TM在所以输入上都停机限制了它能够识别的语言种类。下面的图灵机U识别ATM.U=“对于输入<M,ω>,其中M是一个TM，ω是一个串： 1)在输入ω上模拟M； 2)如果M进入接受状态，则接受；如果M进入拒绝状态，则拒绝。”注意，如果M在ω上循环，则机器U在输入<M,ω>上循环，这就是U不判定ATM的原因。假如M知道自己在ω上不停机，它能拒绝ω，但事实上，它不知道。所以ATM有时被称为停机问题。对角化方法定义5.10设A和B是两个集合，f是从A到B的函数。如果f从不将两个不同 元素映射到同一个地方，即：只要a≠b，就有f(a)≠f(b),则称

f是一对一的。定义5.12称一个激活是可数的，如果它是有限的，或者它与N有相同 的规模。 定理5.14

R是不可数的。推论5.15存在语言不是图灵可识别的。停机问题是不可判定的

ATM＝{<M,ω>|M是一个TM，且M接受ω}证明：假设ATM是可判定的，下面将由之导出矛盾。设H是ATM的判定器。令M是一个TM，ω是一个串。在输入<M,ω>上，如果M接受ω，

则H就停机且接受ω；如果M不接受ω，则H也会停机，但拒绝ω。换句话说，H是一个TM使得： 接受 如果M接受ω

H(<M,ω>)=

拒绝 如果M不接受ω

现在来构造一个新的图灵机D，它以H作为子程序。当M被输入它自己的描述<M>是，TMD就调用H，以了解M将做什么。一旦得到这个信息，D就反着做，即：如果M接受，它就拒绝；如果M

不接受，它就接受。下面是D的描述。

D＝”对于输入<M>，其中M是一个TM： 1)在输入<M,<M>>上运行H。 2)输出H输出的相反结论，即，如果H接受，就拒绝； 如果H拒绝，就接受。”不要被“在一个机器上运行它自己的描述”这个想法所困扰，这类似于以一个程序本身作为输入来运行这个程序，这在实际中确实时有发生。例如，编译器时翻译其它程序的程序。Pascal语言的编译器也许其自身就是以Pascal写的，所以“在一个程序本身上运行这个程序”是有意义的。总而言之， 接受 如果M不接受<M>

D(<M>)= 拒绝 如果M接受<M>当以D的描述<D>作为输入来运行D自身时，结果会怎样呢？我们得到： 接受 如果D不接受<M>

D(<D>)=

拒绝 如果D接受<M>不论D做什么，它都被迫相反地做，这显然是一个矛盾。所以，TMD和TMH都不存在。回顾一些上述证明步骤。先假设TMH判定ATM；然后用H来构造一个TMD，它接受输入<M>，当且仅当M不接受输入<M>；最后在D自身上运行D。这些机器发生下列动作：

H接受<M,ω>，当且仅当M接受ω。

D拒绝<M>,当且仅当M接受<M>。 D拒绝<D>,当且仅当D接受<D>。最后一行是矛盾的。一个图灵不可识别语言定理5.16一个语言是可判定的，当且仅当它既是图灵可识别的，也是 补图灵可识别的。(换句话说,一个语言可判定的,当且仅当它和它的补都是图灵可识别的.)推论5.17ATM不是图灵可识别的。第六章可归约性

归约就是将一个问题转化为另一个问题的方法，使得可以用第二个问题的解来解第一个问题。语言理论中的不可判定问题设 HALATM={<M,ω>|M是一个TM,且对输入ω停机}定理6.1

HALATM是不可判定的。设 ETM={<M>|M是一个TM,且L(M)=Φ}定理6.2

ETM是不可判定的。设 REGULARTM={<M>|M是一个TM,且L(M)是一个正则语言}定理6.2

REGULARTM是不可判定的。设 EQTM={<M1,M2>|M1和M2都是TM,且L(M1)＝L(M2)}定理6.2

EQTM是不可判定的。利用计算历史的归约计算历史方法是证明ATM可归约到某些语言的重要技术。在证明某个问题的不可判定性时，如果此问题涉及的是检查某样东西的存在性，则这个方法常常很有用。图灵机在输入上的计算历史就是当这个图灵机处理此输入时所经过的格局序列。它是这个机器所经历的计算的完整记录。定义6.5设M是一个图灵机，ω是一个串。M在ω上的一个接受计算历史 是一个格局序列C1,C2,……,CL,其中：C1是M在ω上的起始格局，

CL是M的一个接受格局，且CL每个都是CL-1的合法结果，即符合

M的规则。M在ω上的一个拒绝计算历史可类似定义，只是CL应 是一个拒绝格局。定义6.6线性界限自动机（LBA）是一种受到限制的图灵机，它不允许 其读写头离开包含输入的带区域。如果此机器试图将它的读写 头移出输入的两个端点，则读写头就待在原地不动。设ALBA={<M,ω>|M是一个接受串ω的LBA}引理6.7设M是有q个状态和g个带符号的LBA。对于长度为n的带子， M恰有qngn个不同的格局。证明：M的格局就像计算中间的一个快相。格局由控制状态、读写头位置和带内容组成。这里，M由q个状态。它的带长度是n，所以读写头肯处于n个位置之一，且gn多个带符号串可能出现在带上。此三个量的乘积就是带长为n的M的格局总数。证明：判定ALBA的算法如下： L=“对于输入<M,ω>，其中M是LBA,ω是串： 1)在ω上模拟Mqngn步，或者直到它停机。 2)如果M停机，则当它接受是接受，拒绝时拒绝。如果它还 没有停机，就拒绝。”如果M在ω上运行qngn步还没有停机，根据引理6.7，它必定在重复某个格局，即陷入了循环。这就是算法为什么在此情形下拒绝的原因。定理6.8

ALBA是可判定的。ELBA={<M>|M是一个LBA，且L(M)=Φ}定理6.9

ELBA是不可判定的。证明：现在构造从ATM到ELBA的归约。假设TMR判定ELBA。如下构造判定

ATM的TMS: S=“对于输入<M,ω>，其中M是TM,ω是串： 1)如在证明思路中所描述的那样从M和ω构造LBAB; 2)在输入<B>上运行R. 3)如果R拒绝，则接受；如果R接受，则拒绝。”如果R接受<B>，则L(B)=Φ。这样，M在ω上就没有技术计算历史，M也就不接受ω。因此，S就拒绝<M,ω>。类似地，如果R拒绝<B>，则B的语言不空。B能够接受的唯一串，是M在ω上的接受计算历史。这样，M必定接受ω。相应地，S也就接受<M,ω>。可计算函数图灵机计算函数的方式是：将函数的输入放在带子上，开始运行，并以停机后的带子作为函数的输出。定义6.12函数f:∑*－>∑*是一个可计算函数，如果有某个图灵机M，

使得在每个输入ω上，M停机，此时只有f(ω)出现在带子上。例6.13整数上所以通常的算数运算都是可计算函数。例如，可以制造

一个机器，它以<m,n>为输入且返回m与n的和m+n。

在这里不给出细节，而把它们当作练习。映射可约性的形式定义定义6.15语言A是映射可约到语言B的，如果存在可计算函数 f:∑*－>∑*使得对每个ω，

ω∈A<=>f(ω)∈B

记作A≥mB。称函数f为A到B的归约。定理6.16如果A≥mB且B是可判定的，则A也是可判定的。证明：设M是B的判定器，f是从A到B的归约。A的判定器N的描述如下：

N=“对于输入ω： 1)计算f(ω). 2)在f(ω)上运行M，输出M的输出。” 显然，如果ω∈A，则f(ω)

∈B,因为f是从A到B的归约。因此， 只要ω∈A，则M接受f(ω)

。故N的运行正如所求。推论6.17如果A≥mB且A是不可判定的，则B也是不可判定的。定理6.22如果A≥mB，且B是可图灵识别的，则A也是图灵可识别的。推论6.23如果A≥mB，且A不是图灵可识别的，则B也不是图灵可识别的。定理6.24

EQTM既不是图灵可识别的，也不是补图灵可识别的。信息的定义算法和信息在计算机科学中是基本概念。但丘奇－图灵论题在给出算法的广泛而实用的定义的时候，却没有关于信息的同等广泛的定义。考虑下列两个二进制数序列的信息量： A=0101 B=0111直观上，序列A包含较少的信息，因为它只是将01重复了20次。相比之下，序列B看起来包含了更多的信息。包含在一个对象中的信息量，将被定义为这个对象的最小表示或描述的大小。对象的描述是指这个对象的精确且无歧义的特征，使得单从这个特征，就能重新产生那个对象。极小长度的描述用图灵机M和它的二进制数的输入ω来描述二进制数的串x。描述的长度是表示M和ω的组合长度。定义7.20设x是二进制数的串。X的极小描述是最短的串<M,ω>，

其中：TMM在输入ω上停机时，x在带上。且如果有多个 这样的串存在，则在其中选择字典序下的第一个串。记

x的极小描述为d(x)。x的描述复杂性K(x)是

K(x)=|d(x)|定理7.21说明了怎么使用图灵机的输入来表示这样的信息：在存储而不是使用此图灵机的转换函数时，这信息要求一个真正大的描述。它与我们的直觉时一致的，即一个串包含的信息量不可能（实质性的）多于它的长度。类似地，直觉也告诉我们，串xx包含的信息不真的多于x所包含的信息。下面的定理验证了这个事实。下面检查二个串x和y的连接xy的描述复杂性与它们的单个复杂性间的关系。定理7.21可能会引导我们去相信，连接的复杂性最多是单个复杂性的和（加上一个固定的常量），但实际上组合二个描述的代价是导致了一个更大的上界，如下面定理所描述的。定理7.21Ecx[K(x)≤|x|+c]A定理7.22cx[K(xx)≤K(x)+c]AE定理7.23cx，y[K(xy)≤2K(x)+K(y)+c]AE这个定理称，一个串的描述复杂性最多比它的长度多一个固定的常量。这个常量是通用的，即不依赖于这个串。第三部分复杂性理论时间复杂性可判定从而在理论上用计算机可解，在实际中它还可能是不可解的。本书的最后这一部分介绍计算复杂性理论——一门研究求解计算问题所需要的时间、存储量，或者其它资源的理论。度量复杂性定义8.1令M是一个在所有输入上都停机的确定型图灵机。M的运行 时间，或者时间复杂度，是一个函数f:N－>N，其中f(n)是

M在所有长度为n的输入上运行时所经过的最大步数。若f(n)

时M的运行时间，则称M在时间f(n)内运行，M是f(n)时间 图灵机。分析为语言A={0k1k|k≥0}给出的算法。M1=“对输入串ω： 1)扫描带，如果在1的右边发现0，就拒绝。 2)如果0和1都在带上，就重复下一步。 3)扫描带，删除一个0和一个1。 4)如果所有1都被删除以后还有0，或者所有0都被删除后还有1， 就拒绝。否则，如果在带上没有留下0和1，就接受。”M1在长度为n的输入上总共耗时为O(n)+O(n2)+O(n)，或O(n2)。换句话说，它的运行时间是O(n2)。定义8.7令t:N－>N是一个函数。定义时间复杂性类TIME(t(n))为

TIME(t(n))={L|L是一个由O(t(n))时间的图灵机判定的语言}。M2=“对输入串ω：

1)扫描带，如果在1的右边发现0，就拒绝。 2)只要在带上还有0和1，就重复下面的步骤。 3) 扫描带，检查剩余的0和1的总数是偶数还是奇数。 若是奇数，就拒绝。 4) 再次扫描带，从第一个0开始，隔一个删除一个0； 然后从第一个1开始，隔一个删除一个1。 5)如果带上不再有0和1，就接受。否则，拒绝。”

M2的运行时间是O(n)+O(nlogn)=O(nlogn)实际上，单带图灵机在o(nlogn)时间内判定的语言都是正则语言。如果图灵机有第二条带，就可以在O(n)时间（也称为线性时间）内判定语言A。下面的两带TMM3在线性时间内判定A。M3=“对输入串ω： 1)扫描带，如果在1的右边发现0，就拒绝。 2)扫描带1上的0，直到第一个1时停止，同时把0复制到带2上。 3)扫描带1上的1直到输入的末尾。每次从带1上读到一个1， 就在带2上删除一个0，如果在读完1之前所有的0都被删除， 就拒绝。 4)此时，如果所有的0都被删除，就接受。如果还有0剩下， 就拒绝。”总结一些关于A的时间复杂性的结果。给出一个单带TMM1，能够在时间O(n2)内判定A；以及一个更快的单带TMM2，能够在时间O(nlogn)内判定A。并称（没有证明）不存在更快的单带TM。随后给出一个两带TMM3，能够在时间O(n)内判定A。因此A在单带TM上的时间复杂度是O(nlogn),在两带TM上是O(n)。注意A的复杂度与选择的计算模型有关。模型间的复杂性关系现在来考察计算模型的选择怎样影响语言的时间复杂度。考虑三种模型：单带图灵机。多带图灵机和非确定型图灵机。定理8.8设t(n)是一个函数，t(n)≥n。则每一个t(n)时间的多带图灵机都 和某一个O(t2(n))时间的单带图灵机等价。下面考虑对非确定型单带图灵机的类似定理。证明这种机器所判定的语言在确定型单带图灵机上也是可判定的，但需要多得多的时间。在此之前，不行定义非确定型图灵机的运行时间。回忆一下，一个非确定型图灵机，当它的所有计算分支在所有输入上的停机时，成为一个判定机。定义8.9设N是一个非确定型图灵机，并且是个判定机。N的运行时间是 函数f:N－>N,f(n)是在任何长度为n的输入上，N的所有计算分支 的最大步数。定理8.10设t(n)是一个函数，t(n)≥n。则每一个t(n)时间的非确定型 单带图灵机都与某一个2O(t(n))时间的确定型单带图灵机等价。P类定理8.8和定理8.10显示出一个重要的差别。一方面，问题的时间复杂性在确定型单带和多带图灵机上最多相差平方或多项式；另一方面，在确定型和非确定型图灵机上，问题的时间复杂性最多相差指数。多项式时间定义8.11

P是确定型单带图灵机在多项式时间内可判定的语言类。 换句话说，P=∪kTIME(nk)

在我们的理论中，P类扮演核心的角色，它的重要性在于 1)对于所有与确定型单带图灵机多项式等价的计算模型来说， P是不变的。 2)P大致对应于在计算机上实际可解的问题类。P中的问题举例PATH={<G,s,t>|G是具有从s到t的有向路径的有向图}定理8.12

PATH∈P证明：PATH的一个多项式时间算法M运行如下：

M＝“对输入<G,s,t>，G是包含节点s和t的有向图 1)在节点s上做标记。 2)重复下述步骤，直到不再有节点做标记。 3) 扫描G的所有边。如果找到一条边(a,b)，a被标记而 b没有标记，那么标记b。 4)若t被标记，则接受；否则，拒绝。”分析该算法，证明它在多项式时间内运行。显然，步骤1和4只执行一次。步骤3最多执行m次，因为除最后一次外，每一次执行都要标记G中的一个未标记的节点。所以用到的总步数最多是1+1+m，是G的规模的多项式。定理8.14每一个上下文无关语言都是P的成员。证明：下面的算法D实现了这一证明思路。令G是产生CFLL的乔姆斯基范式的CFG。假设S是起始变元。（回忆一下，空串在乔姆斯基范式文法中被特殊处理。算法在步骤1中处理ω=ε的特殊情况。）注释写在双括号中。D＝“对输入ω=ω1ω2……ωn：

1)若ω=ε且S－>ε是一条规则，则接受。[处理ω=ε的情况] 2)Fori=1ton，[考察每一长为1的子串] 3) 对每一变元A， 4) 检查A－>b是否是一条规则，其中b=ωi。 5) 若是，把A放入table(i,j)。 6)Forl=2ton,[l是子串的长度] 7) Fori=1ton-l+1,[i是子串的起始位置] 8) 令j=i+l-1,[j是子串的结束位置] 9) Fork=itoj-1,[k是分裂位置] 10) 对每一条规则A－>BC， 11) 若table(i,k)包含B且table(k+1,j)包含C， 则把A放入table(i,j)。 12)若S在table(1,n)中，则接受；否则，拒绝。”

现在分析D。每一步很容易在多项式时间内运行。步骤4和5最大运行nv次，其中v是G中的变元数，是与n无关的固定常数；因此这两步运行O(n)次。步骤6最大运行n次。步骤6每运行一次，步骤7最多运行n次。步骤7每运行一次，步骤8和9最多运行n次。步骤9每运行一次，步骤10运行r次，这里r是G的规则数，是另一个固定常数。所有步骤11，即该算法的内层循环，运行O(n3)次。总计D执行O(n3)步。NP类定义8.15语言A的验证机是一个算法V，这里

A={ω|对某个字符串c，V接受<ω,c>}

因为只根据ω的长度来度量验证机的时间，所以多项式

时间验证机在ω的长度的多项式时间内运行。若语言A有一个 多项式时间验证机，则称它为多项式可验证的。定义8.16

NP是具有多项式时间验证机的语言类。术语NP即非确定型多项式时间，是使用非确定型多项式时间图灵机的另一个特征。在非确定型多项式时间内判定HAMPATH问题的非确定型图灵机(NTM)。N1＝“对输入<G,s,t>，这里G是包含节点s和t的有向图： 1)写一列m个数p1,p2,……,pm,m是G的节点数。列中每一个数 都是从l到m中非确定地挑选。 2)在列中检查重复性，若发现有重复，则拒绝。 3)检查S=P1和t=pm,是否都成立。若有一个不成立，则拒绝。 4)对于1到m－1中的每一个i，检查(pi,pi+1)是否是G的一条边。 若有一个不是，则拒绝。否则，所有检查都通过了，接受。”定理8.17一个语言在NP中，机当且仅当它能被某个非确定型多项式 时间图灵机判定。证明：对于该定理从左向右的方向，设A∈NP，要证明A被多项式时间

NTMN判定。有NP的定义，存在A的多项式时间验证机V。假设V是一个在时间nk内运行的TM，构造N如下：

N＝“对长为n的输入ω。 1)非确定地选择长为nk的字符串c 2)在输入<ω,c>上运行V。 3)若V接受，则接受；否则拒绝。” 为了证明该定理的另一个方向，假设A被多项式时间HTMN判定，构造多项式时间验证机V如下：

V=“对输入<ω,c>，这里ω,c是字符串： 1)在输入ω上模拟N，把c的每一个符号看作是对每一步 所做的非确定型选择的描述(正如在定理4.10的证明中 那样。) 2)若N的该计算分支接受，则接受；否则，拒绝。”类似与确定型时间复杂性类TIME(t(n))，定义非确定型时间复杂性类NTIME(t(n))。定义8.18

NTIME(t(n))＝{L|L是一个被O(t(n))时间的非确定型图灵机 判定的语言}推论8.19

NP=UkNTIME(nk)NP中的问题举例无向图中的一个团是一个子图。其中每两个节点都有边相连。K团就是包含k个节点的团。团问题就是判定一个图是否包含指定大小的团。令

CLIQUE={<G,k>|G是包含k团的无向图}定理8.20CLIQUE属于NP。证明：下面是CLIQUE的验证机V。 V＝“对输入<<G,k>,c>； 1)检查c是否是G中k个节点的集合。 2)检查G是否包含连接c中节点的所有边。 3)若两项检查都通过，则接受；否则，拒绝。”另一种证明：如果读者喜欢从非确定型多项式时间图灵机的角度来理解

NP类，那么可以通过给出判定CLIQUE的图灵机来证明本定理。 注意这两种证明的相似性。

N=“对输入<G,k>,这里G是一个图： 1)非确定性地选择G中k个节点的子集c。 2)检查G是否包含连接c中节点的所有边。 3)若是，则接受；否则，拒绝。”

P与NP问题

NP是在非确定型图灵机上多项式时间内可解的语言类，或者等价地说，是成员资格可以在多项式时间内验证的语言类。P是成员资格可以在多项式时间内判定的语言类。把这些内容总结如下，其中，把多项式时间可解的粗略地称为“快速地”可解的。

P＝成员资格可以快速地判定的语言类

NP＝成员资格可以快速地验证的语言类求解NP语言的已知的最后方法确定性地使用指数时间。换言之，可以证明

NPEXPTIME=∪kTIME(2nk)但是，不知道NP是否包含在某个更小的确定性时间复杂性类中里。∩NP完全性在P与NP问题上的一个重大进展是在70年年代初由斯蒂芬库克和列奥尼德列文完成。他们发现NP中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间算法，那么所有NP问题都是多项式时间可解的。这些问题称为NP完全的。NP完全性现象对于理论与时间都具有重要意义。给出的第一个NP完全问题称为可满足性问题。取值为TRUE和FALSE的变量称为布尔变量。通常用1表示TRUE，用0表示FALSE。布尔运算AND，OR，NOT分别表示为∧，∨，﹁。定理8.22库克—列文定理

SAT∈P 当且仅当P=NP布尔公式是包含布尔变量和运算的表达式。例如，

Ф=(x∧y)∨(x∧z)是一个布尔公式。如果对变量的某个0，1赋值使得一个公式的值等于1，则该布尔公式是可满足的。可满足性问题就是判定一个布尔公式是否是可满足的。令

SAT={<Φ>|Φ是可满足的布尔公式}多项式时