计算理论11年真题及答案(研究生部分答案已参考老师的答案-还有我们做的本科生部分的答案).doc

这是我们（32舍388）参考老师的课堂内容整理的11年的答案，附带解析。由于时间仓促，错误必定不少，请各位见谅并吐槽指正。G版(a) F 不一定。因为假设A是*，B是M在“M”上不停机，符合题目要求，B不是可判定的。(b) T 如果A可以归约到B，根据归约的定义，xA的时候t(x)B，反之，xA，即xA的补的时候t(x)B，即t(x)B的补。(c) F 因为DFA总有停机的时候，对于一个DFA输入“M”，这个DFA总会读完所有的字符然后给出yes或者no，因此这个语言是递归的。老师课堂上说DDFA是非正则的，这是可以用对角化定理证明DDFA和每个正则语言都不一样，证明和课本165页中间的相似。(d) T 这个非递归可枚举的语言就是课本164下面那个H1的补，M在“M”上不停机(e) T He可以用通用图灵机半判定，但是无法判定。停机问题，即图灵机M在某个输入w上是否停机，无法判定，这里让w=e即可。(f) F 根据定理5.4.1，因为H不是递归的，所以L也不递归了。因为HL补，所以H补L。如果L是递归可枚举的，那么H补也是递归可枚举，那么H就不是递归可枚举的了，这和H本身是递归可枚举的事实是相悖的，因此L不是递归可枚举的。(g) T 假设M1半判定A，M2半判定B，M3半判定AB的补。对于输入w，交给M1、M2和M3一起做。如果M1接受，那么wA，M2接受，那么wB，如果M3接受，那么w(AB)，即不是A也不是B。因为A和B是不相交的，因此M1、M2和M3的合体可以判定A或者B，因此A和B都是可判定的，递归的。(h) T 后面的是NTIME，应该是不确定性计算的所需时间。所以，我们把nk看作一体的，称为a，那么确定计算时间是指数ca，非确定计算只要a，也就是nk了。(i) T B是P，A可以多项式时间归约到B，所以A也是P，P对补封闭，所以命题正确。(j) F 假设A是这样一个问题，给定一个整数集合和整数k，求是否存在k个元素和大于C。直观看我们可以用随机抽取k个元素然后算和然后如果其中一次大于C就接受。但是我们也可以通过，例如多项式时间的冒泡排序，把集合的整数降序排序，归约到问题B，前k个元素的和是否大于C，显然B是P的。所以，只能说如果B是NP的，A可以归约到B，那么A也是NP的。(k) T 这个表述有点纠结，我们尚且给个T。因为NPC是可计算的，有算法可解的，是递归的，当然也是递归可枚举的。(l) F 我们直观点看，NPC是所有NP问题都可以多项式归约到的问题，如果命题是正确的，那么NP=NPC了，所有NP问题都可以归约到任意一个NP问题上。如果这样，数学家不用花那么多精力寻找更多的NPC问题了。所以这么看命题是错误的。其实这个题目应该是个陷进，把L和SAT的位置换一下就对了。解析：是正则的。因为这相当于要求xy中a的个数是偶数就可以了，所以可以构造DFA来接受。解析：非正则。可以用泵定理证明。解析：其实这是正则的，只有首尾字母不同并且长度是偶数就可以了。G=（V，R，S）V=a，b，S，S1，S2=a，bR=下推自动机M=（K，s，F）K=p，q=a，b=a，b，S，S1，S2=(q,a,a),(q,e)(q,b,b),(q,e)S=pF=q好像还是第一次考乔姆斯基范式。生成乔姆斯基范式有三个阶段，把右面是大于2的分解掉，把右面是e的消掉变成右面是1个的，最后把右面是1个的消掉实在是太烦了，还要求闭包，这显然是给机器做的通用做法。大家不如用人脑只能直接凑一下吧，反正不是每年常考的题目这是双带图灵机，字符右上角标记表示在第几条带操作，诸如ab这样的表示第一条带带头下是a，第二条的是b。思路是，首先把c前面的内容复制到第二条带。然后第一条带带头到最左边，两条带同时移位检查c前面的内容是否对称。如果对称了，那么检查后面。图上的小修改是因为n是0也可以，因此要先判断c后面是不是a，如果是空格那么也是可以的。如果输入字串的c后面是a，那么把所有a复制到第二条带上，然后第一条带上读到b的时候开始检查a和b的数量是否相同。解析：composite numbers 就是合数。（x,y）= (1prime(x)(1prime(y)exp(x+1,y)其中prime(x)就是判断x是否是质数，exp就是求指数，是非负减法。Rem是求余的函数，equals是判断是否相等的函数，都是原始递归的，所以prime原始递归的其中multi是乘法函数，所以exp也是原始递归的。原始递归函数的合成也是原始递归的，所以原函数是原始递归的。（a） 设这个语言是L，L是递归可枚举但非递归的，我们可以用通用图灵机M半判定L。为了找到M1和M2都可以停机的字符串，我们逐轮逐轮来寻找。第一轮，生成w0，然后通用图灵机UTM模拟M1和M2在w0上计算一步。如果都没有停机，下一轮。第二轮，生成w1，然后通用图灵机UTM模拟M1和M2在w0和w1上计算两步。如果都没有停机，下一轮。第n轮，生成wn-1，模拟M1和M2在w0到wn-1上计算n步。木有停机就下一轮。Wi是按照字典序的*的字符串。因此，如果真的有M1和M2同时停机的字符串w的话，那么UTM的模拟最终停止然后接受“M1”“M2”，否则不停机，因此L是递归可枚举的。这里只是证明了递归可枚举，还没有证明其不是递归的。证明不是递归，可以通过把一个非递归的问题归约到L上，那么L也是非递归的。设He=“M”|图灵机M在e上停机，显然这是不递归的。我们要把L归约到He上来。考虑图灵机C，C启动前木有任何输入，启动之后首先在带上面自己写上“M1”“M2”，只有自己写上个w，然后先模拟M1在w上的执行，如果停机了，那么擦掉结果，再模拟M2在w上的执行，如果M1和M2都在w上停机了，那么显然，C在e上停机，否则不停机。所以，C在空串上停机当且仅当M1和M2都在w上停机。因为He是不可判定的，所以L也是不可判定的。（很绕很恶心，觉得不对劲的同学请参看课本上5.4节定理5.4.2的（b）的、同样绕同样恶心的证明。）（b） 设这个语言是L1，显然L1是L的补，L是递归可枚举非递归，因此L1不是递归可枚举的。（a） 我们可以设计一个NTM M在多项式时间之内计算SAT。对于给定输入，M首先随机生成一串各变量的真值赋值F，然后代入到在O(N)时间内（N为输入长度）验证F是否满足每个子句至少一个文字为真且至少一个文字为负。所以SAT是NP难的。（b） 我们要把3SAT问题多项式时间归约到SAT上面。归约的原始定义，是L1归约到L2，那么如果xL1当且仅当t(x)L2。（原谅我们用t替代）因此证明的时候需要证明当和仅当。首先是转换t，对于输入的3-CNF范式，对于每个合取子句，我们这样转换假设有n个析取范式，那么我们增加n个变量zi，b取F，于是得到（上面加一波浪线，各位意淫一下）看下面的答案解析之前，各位哥哥姐姐且听我等一劝：这题目只占4分，丢卒保车更好。U版（a） F 令y=e，然后整个语言就成了a，b*，所以是正则的。（b） F 实在不会这个要举反例，我们都木有想到，各位想到了可以告诉贺剑峰（c） T 可以构造一个PDA来接受。读到a压栈，读到b弹出a或者空栈了压入b，读到c弹出b，如果最后栈空了那么不接受。（d） F 同样可以构造一个PDA来接受，读到一个x的字符压栈三个字母，读到一个z的字符出栈三个字母。（e） F PDA同样有停机问题，不一定可以停机，因此不是递归的。（f） F 确定型图灵机和非确定的都是计算能力等价的。（g） T 可以用通用图灵机半判定。通用图灵机随机生成一个输入w，然后模拟M(w)，如果接受那么yes，否则就不停机。（h） T 这句话的意思是，存在非原始递归的可计算函数，因为原始递归函数是递归函数的子集，而递归的函数才是可计算的函数，因此表述正确。（i） F 我们可以用有限的字符来对图灵机进行编码，而有限集合的幂集是可数无穷的，因此图灵机的个数也是可数无穷个。（j） T 语言是递归的当且仅当其本身和其补都是递归可枚举的，因此如果L是递归的，那么其本身和其补都是可半判定的。（k） T 课本5.3节已说明（l） F 和（k）相近，是非递归的递归可枚举（a） (aa)*(bb)* (aa)*a(bb)*b(b)根据泵定理，假设L2是正则的，存在满足泵定理的整数m。对于wL2，考虑w=amb2ncanb3m，|w|m，令w=xyz，且|xy|m，ye，那么y=ak，显然xyizL2，所以L2不是正则的。最后得到 101100，中间的格局大家自己推吧_X=0时，f(x)=1X=1时，f(x)=101其他，f(x)=4x这是显然的，函数分段操作是原始递归的，乘法运算也是原始递归的，因此f(x)是原始递归的。 可以用通用图灵机UTM半判定，对于输入“M”，UTM模拟M(“M”)的计算，如果M在“M”上停机那么UTM停机返回yes，如果M在“M”上不停机那么通用图灵机也不会停机。因此这个语言是递归可枚举的。