丘奇图灵论题练习.doc

第4章、丘奇-图灵论题习题解答 - 练习 4.1、此练习和TM M2有关，例4.4给出了它的描述和状态图，它判定语言。在下列每个输入串上，给出M2所进入的格局序列： 0 00 000 000000 答： q10 、 q2 、 qaccept q100 、 q20 、 x q3 、 q5x 、q5 x 、 q2 x x q2 、 x qaccept q1000 、 q200 、 x q30 、 x0q4 、 x0qreject q1000000 、 q200000 、 xq30000 、 x0q4000 、 x0xq300 x0x0q40 x0x0xq3 、 x0x0q5x 、 x0xq50x 、 x0q5x0x xq50x0x 、 q5x0x0x 、q5 x0x0x 、 q2x0x0x 、 xq20x0x xxq3x0x xxxq30x 、 xxx0q4x 、 xxx0xq4 xxx0x qreject 4.2、此练习和TM M1有关，例4.5给出了它的描述和状态图，它判定语言B={w#w|w({0,1}*}。在下列每个输入串上，给出M1所进入的格局序列： 11 1#1 1##1 10#11 10#10 答： q111 、 q31 、 1q3 、 1qreject q11#1 、 q3#1 、 #q51 、 #1q5 、 # q71 、 q7#1 q7 #1 、 q9#1 、 #q111 、 q12# x 、q12 # x 、q13 # x #q14x 、 #xq14 、 #x qaccept q11##1 、 q3##1 、 #q5#1 、 #qreject #1 q110#11 、 q30#11 、 0q3#11 、 0#q511 、 0#1q51 、 0#11q5 0#1q71 、 0#q711 、 0q7#11 、 q70#11 、q7 0#11 、 q90#11 0q9#11、 0#q1111 、 0q12#x1 、 q120#x1 、q12 0#x1 、 q130#x1 xq8#x1、 x#q10x1 、 x#xq101 、 x#xqreject1 q110#10 、 q30#10 、 0q3#10 、 0#q510 、 0#1q50 、 0#10q5 0#1q70 、 0#q710 、 0q7#10 、 q70#10 、q7 0#10 、 q90#10 0q9#10、 0#q1110 、 0q12#x0 、 q120#x0 、q12 0#x0 、 q130#x0 xq8#x0、 x#q10x0 、 x#xq100 、 x#q12xx 、 xq12#xx 、 q12x#xx q12 x#xx、 q13x#xx 、 xq13#xx 、 x#q14xx 、 x#xq14x 、 x#xxq14 x#xx qaccept 4.3 修改定理4.10以得到推论4.12的证明，即证明一个语言是可判定的当且仅当有非确定型TM判定它。（可以假设关于树的下列定理成立：如果一个树中的每个结点只有有限多个子结点，且此树的每一个分枝只有有限多个结点，则此树本身只有有限个结点）。 证明： 定理4.10为：每个非确定型图灵机都有一个与之等价的确定型图灵机。 修改定理4.10为：每个非确定性判定器都有与之等价的确定型判定器。 现在设N是一个非确定性判定器，N 对所有输入，所有分枝都停机。构造一个与之等价的确定型判定器D。D有三个带：一个输入带，一个模拟带，一个地址带。D按“宽度优先”策略有哪些信誉好的足球投注网站N的不确定计算分枝树。 M= “输入w， 开始时，输入带包含输入w, 模拟带和地址带都是空的。 把输入带的内容复制到模拟带上。 在模拟带上模拟N在输入w上的非确定性计算树的某个分枝。 在N的每一步动作之前，查询地址带上的下一个数字，以决定在N的转移函数所允许的选择中作何选择。 如果地址带上下一个数字是空白，则放弃这个分枝，转到第四步。 如果这个非确定性的选择是无效的，则放弃这个分枝，转到第四步。 如果遇到拒绝格局，则放弃这个分枝，转到第四步。 如果遇到接受格局，则接受这个输入。 按照字典顺序取下一个地址串。根据假设非确定性计算树只有有限的结点，所以地址串有一个上界Amax。 如果下一个地址串已经超过Amax，则说明已经有哪些信誉好的足球投注网站了所有分枝，那么拒绝这个输入。 否则用下一个地址串来替代原有的串。转到第二步，以模拟N的计算的下一个分枝。” 如果有一个非确定性判定器判定语言，根据上述证明，必有与之等价的确定型判定器判定该语言，则该语言是可判定的。 如