4、丘奇-图灵论题练习

《4、丘奇-图灵论题练习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章、丘奇-图灵论题习题解答-练习4.1、此练习和TMM2有关，例4.4给出了它的描述和状态图，它判定语言。在下列每个输入串上，给出M2所进入的格局序列：a.0b.00c.000d.000000答：a.q10、q2、qacceptb.q100、q20、xq3、q5x、q5x、q2xxq2、xqacceptc.q1000、q200、xq30、x0q4、x0qrejectd.q1000000、q200000、xq30000、x0q4000、x0xq300x0x0q40x0x0xq3、x0x0q5x、x0xq50x、x0q5x0xxq50x0x、q5x0x0x、q5x0x0x

2、、q2x0x0x、xq20x0xxxq3x0xxxxq30x、xxx0q4x、xxx0xq4xxx0xqreject64.2、此练习和TMM1有关，例4.5给出了它的描述和状态图，它判定语言B={w#w

3、wÎ{0,1}*}。在下列每个输入串上，给出M1所进入的格局序列：a.11b.1#1c.1##1d.10#11e.10#10答：a.q111、q31、1q3、1qrejectb.q11#1、q3#1、#q51、#1q5、#q71、q7#1q7#1、q9#1、#q111、q12#x、q12#x、q13#x#q14x、#xq14、#xqacceptc.q11##1、q3##1

4、、#q5#1、#qreject#1d.q110#11、q30#11、0q3#11、0#q511、0#1q51、0#11q50#1q71、0#q711、0q7#11、q70#11、q70#11、q90#110q9#11、0#q1111、0q12#x1、q120#x1、q120#x1、q130#x1xq8#x1、x#q10x1、x#xq101、x#xqreject1e.q110#10、q30#10、0q3#10、0#q510、0#1q50、0#10q50#1q70、0#q710、0q7#10、q70#10、q70#10、q90#1060q9#10、0#q1110、0q12#x

5、0、q120#x0、q120#x0、q130#x0xq8#x0、x#q10x0、x#xq100、x#q12xx、xq12#xx、q12x#xxq12x#xx、q13x#xx、xq13#xx、x#q14xx、x#xq14x、x#xxq14x#xxqaccept4.3修改定理4.10以得到推论4.12的证明，即证明一个语言是可判定的当且仅当有非确定型TM判定它。（可以假设关于树的下列定理成立：如果一个树中的每个结点只有有限多个子结点，且此树的每一个分枝只有有限多个结点，则此树本身只有有限个结点）。证明：定理4.10为：每个非确定型图灵机都有一个与之等价的确定型图灵机。修改定理

6、4.10为：每个非确定性判定器都有与之等价的确定型判定器。现在设N是一个非确定性判定器，N对所有输入，所有分枝都停机。构造一个与之等价的确定型判定器D。D有三个带：一个输入带，一个模拟带，一个地址带。D按“宽度优先”策略搜索N的不确定计算分枝树。M=“输入w，1)开始时，输入带包含输入w,模拟带和地址带都是空的。2)把输入带的内容复制到模拟带上。3)在模拟带上模拟N在输入w上的非确定性计算树的某个分枝。a)在N的每一步动作之前，查询地址带上的下一个数字，以决定在N的转移函数所允许的选择中作何选择。b)如果地址带上下一个数字是空白，则放弃这个分枝，转到第四步。c)如果这个非

7、确定性的选择是无效的，则放弃这个分枝，转到第四步。d)如果遇到拒绝格局，则放弃这个分枝，转到第四步。e)如果遇到接受格局，则接受这个输入。4)按照字典顺序取下一个地址串。根据假设非确定性计算树只有有限的结点，所以地址串有一个上界Amax。a)如果下一个地址串已经超过Amax，则说明已经搜索了所有分枝，那么拒绝这个输入。b)否则用下一个地址串来替代原有的串。转到第二步，以模拟N的计算的下一个分枝。”6如果有一个非确定性判定器判定语言，根据上述证明，必有与之等价的确定型判定器判定该语言，则该语言是可判定的。如果一个语言是可判定的，则有一个确定性判定器判定该语言。确定性判定器自

8、然是非确定型判定器，所以必有非确定型判定器判定它。4.4给出枚举器的形式定义。可将其看作一种双带图灵机，用它的第二个带子作为打印机。包括它所枚举的语言的定义。解：枚举器E=(Q，S，G，d，q0，qaccept，qreject),其中转移函数d为：d：Q×G→Q×G×{L,R}×G×{R}d(q，a)=(r，b，s1，c，R)表示若E处于状态q，且在工作带上读到a，则状态转移到r，当前格改写为b并按s1所指示的方向移动读写头，打印带上写下c并向右移动读写头。另外E的起始格局只能是q0ò。L(E)={w

9、w是枚举器E打印出的串}