唐常杰翻译的计算理论导引22

《唐常杰翻译的计算理论导引22》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第9章难解性(同学讨论PPT素材)作为教学科研的基本训练的一个重要环节，学生应该能根据教材，作出有白己特色的PPT发言稿.这里提供一些素材，试图减小学生的工作难度。PPT不能仅仅是剪报。一份好的讨论班PPT应该冇同学的理解和创新.(素材节选自教材但不能代替教材)从素材作PPT—般需要用读-减一加三个过程。(a)先充分阅读理解教材，(b)从此素材中删去次要语句，(c)增加自己的心得，理解方法，解释和图形。PPT应该突出思路，突出要点，适当的比喻可以帮助理解。9」层次定理通常的直觉是给图灵机更多的吋间或空间就能扩大它所能求解的

2、问题类。例如，在时间用内，图灵机应能比在时间川内判定更多的语言。在一定条件下，这种直觉是正确的。层次定理(hierarchytheorems)证明了这种肓觉在满足某些条件下的正确性。采用术语层次定理，是因为这些定理中的每一个都证明了时间和空间复杂性类不全相同一它们形成一个层次结构，其中时空界限较大的类比时空界限较小的类包含更多的语言。空间复朵性层次定理比吋间复朵性层次定理稍简单-•些，故首先介绍它。在实际陈述定理之前，引入下面的定义。定义9・1函数于：NtN,/S)至少为CKlogn),如果函数/把1"映射为/(町的二进制

3、表示并且该函数在空间0(/(〃))内是町计算的'称为空间可构造的(spaceconstructible)。换言Z,如果存在某个TMM,在0(./(/?))空间内运行，而在输入1"时总能停机，停机时/⑷的二进制表示出现在带子上，则/是空间可构造的。为了具有时间和空间可构造性,如nlog2n和馆这一类带小数的函数被向下舍入到紧邻的较小的整数上。例9.2通常出现的复朵度至少为0(logn)的函数都是空间可构造的，包括log2n,nlog2n,n2。例如，〃2是空间可构造的，因为机器以$为输入，通过数1的数H得到川的二进制形式，采

4、用标推的方法将料白乘，输出〃2。全部空间消耗是0(耐，当然也是0(“)。I其中，1”的意思是"个1的字符串。当证明等于o（〃）的函数/s）是空间可构造的吋候，切同在&4节定义亚线性空间复杂性那样，有一条单独的只读输入带。例如，这种机器可以如下计算把1"映射为log2n的二进制表示的函数。随着只读头沿着输入带移动，它在工作带上以二进制形式计算输入屮1的数目。然后，因为n以二进制形式放在工作带上，它通过数n的二进制表示中的位数可以计算出log2“。从卜•面的讨论屮可以理解空间可构造性在空间层次定理屮的作用。若口7）和g@）是两

5、个空间界限，/（〃）渐近地比g®）大，贝IJ机器在/（町空间内所能计算的语言比在g（/i）空间内多。然而，假如/（司超过g@）的那部分数最非常小而且难以计算，那么机器可能无法有效地利用多出来的那部分空间，因为光是计算多出来的空间数罐所需消耗的空间就可能比所获得的空间还要多。在这种情况下，机器在/（町空间内所能计算的语言不会比在g®）空间内更多。规定/（町是空间可构造的就可避免这种情况，这样就可以证明机器所能计算的语言比它在任何渐近更小的界限内所能计算的语言更多，如下面的定理所示。定理9.3空间层次定理对于任何空间可构造函数

6、/：N-N,存在语言在空间（9（/（/?））内可判定，但不能在空间。（/（町）内判定。证明思路必须显示一个语言A具有两个性质，笫一，A在O（/（h））空间内可判定，第二，4不能在。（/（町）空间内判定。通过给出判定算法D來描述A。算法D将在O（/（«）））空间内运行，从而保证了笫一个性质。进而，D将保证A不同于任何在空间内可判定的语言，从而保证了第二个性质。不耍指望关于语言仏能够象迄今为止己出现在本书中的其他语言那样，有-•幅简单明了的图像。语言A则不同，它只能通过算法來描述，没有更简单的、非算法的定义。为保证A不能在o（

7、f（n））空间内判定，设计D用以实现定理4.9中证明停机问题A®不可解时所采用的对角线法。如果M是在空间内判定一个语言的机器，则D保证A与M的语言至少存在一点不同的地方。是哪个地方？就是对应于描述M自己的地方。看一看Q的运算方式。简单地讲，D把它的输入看作是TMM的描述。（如果输入不是任何TM的描述，则Q在该输入上的动作是无意义的，所以武断地让D拒绝即可。）然后Q在同一输入，即＜M＞上，在空间界限/（町内运行M。如果M在这么人空间内停机，则D接受的充分必要条件是M拒绝。如呆M不停机，则D拒绝。所以如果M在空间“7）内运行,

8、则D有足够的空间保证它的语言不同于M的语言。否则，D没有足够的空间算出M的结果,但幸运的是并没冇要求D的行为与不能在。（/（町）空间内运行的机器不同，所以D在该输入上的动作是无关紧要的。该描述抓住了证明的本质，但忽略了儿个重要的细节。如果M在。（/（町）空间内运行，则D必须保证它的语言不同于M的语言。但