6.045J/18.400J:Automata,Computability and Complexity Prof.Nancy Lynch 测试2(3.302005) 请在每一页的上面写上自己的名字 问题1：判断正误(20分)：判断正确的话，给全分。如果你对你的结论作论证的话，即使 你的判断不正确，也可能获得部分的分数。 1、设S是一个图灵机判定器的集合，并且S包含所有能够判定无穷的可判定语言的判定器， 那么存在一个图灵机能够枚举S中的元素。 2、设S是一个图灵机判定器的集合，并且S至少包含一个能够判定所有可判定语言的判定器， 那么存在一个图灵机能够枚举S中的元素。 3、设S是一个图灵机判定器的无穷集合，并且S中的每一个机器都是“最小”的（这里最小 的意思是说不存在一个比改图灵机更小的判定相同语言的机器)，那么存在一个图灵机能够 枚举S中的元素。 4、由RiCe定理可得出{M是一个图灵机，L(M)是集合0*1*的子集}是不可判定的。 5、如果L1是一个可判定的语言，而L2是一个图灵机可识别的语言，那么L1-L2一定是图灵 机可识别的。 6、如果L1是一个可判定的语言，而L2是一个图灵机可识别的语言，那么L1L2一定是图灵 机可识别的。 7、三维图灵机是在普通的图灵机作如下的修改而得到的机器：它的带子的存储是一个三维的 带子，每个带子单元有一个立方体组成。每一步中，读写头可以向北、南、东、西、上、 下移动。三维图灵机所识别的语言就是图灵机可识别的语言集合。 8、三个栈的栈机器所识别的语言恰好就是图灵机可识别的语言。（即两者相等） 问题2：（25分)图灵机M的形式描述如下图所示：这里Q={q0,q,q2,q3,Qreject,Qaccept},∑={0,1} T={0,1,Ⅱ}。假设图中没有标示的转化都会转化到qeet状态。 0>L 0-R 1→R 1L 0+尽 L凵L 1-UL q0 01 0n 03 L☐R -R q accept 1、(5分)写出M在输入01上的详细计算过程。请用课上所讲的格式 2、(5分)M识别什么样的语言（请给出精确的定义）
6.045J/18.400J: Automata, Computability and Complexity Prof. Nancy Lynch 测试 2 (3.30 2005) 请在每一页的上面写上自己的名字. 问题 1：判断正误（20 分）：判断正确的话，给全分。如果你对你的结论作论证的话，即使 你的判断不正确，也可能获得部分的分数。 1、 设 S 是一个图灵机判定器的集合，并且 S 包含所有能够判定无穷的可判定语言的判定器， 那么存在一个图灵机能够枚举 S 中的元素。 2、 设 S 是一个图灵机判定器的集合，并且 S 至少包含一个能够判定所有可判定语言的判定器， 那么存在一个图灵机能够枚举 S 中的元素。 3、 设 S 是一个图灵机判定器的无穷集合，并且 S 中的每一个机器都是“最小”的（这里最小 的意思是说不存在一个比改图灵机更小的判定相同语言的机器），那么存在一个图灵机能够 枚举 S 中的元素。 4、 由 Rice 定理可得出{| M 是一个图灵机，L(M)是集合 0*1*的子集}是不可判定的。 5、 如果 L1 是一个可判定的语言，而 L2 是一个图灵机可识别的语言，那么 L1-L2 一定是图灵 机可识别的。 6、 如果 L1 是一个可判定的语言，而 L2 是一个图灵机可识别的语言，那么 L1L2 一定是图灵 机可识别的。 7、 三维图灵机是在普通的图灵机作如下的修改而得到的机器：它的带子的存储是一个三维的 带子，每个带子单元有一个立方体组成。每一步中，读写头可以向北、南、东、西、上、 下移动。三维图灵机所识别的语言就是图灵机可识别的语言集合。 8、 三个栈的栈机器所识别的语言恰好就是图灵机可识别的语言。（即两者相等） 问题 2：（25 分）图灵机M的形式描述如下图所示：这里Q={q0,q1,q2,q3,qreject,qaccept}，∑={0,1}， Γ={0,1 ,ц}。假设图中没有标示的转化都会转化到qreject状态。 1、（5 分）写出 M 在输入 01 上的详细计算过程。请用课上所讲的格式 2、（5 分）M 识别什么样的语言(请给出精确的定义)
3、(10分)针对本特殊的机器M以及输入01，给出修正的PCP所对应的小片集合，并指明那 个是初始片。题目己经给出了最终的结果，你只需要完成前面的初始小片以及移动所需要的片。 初始化片： 右移的片： 左移的片： 字母表片： (8)()(出)()(u) 1 qaccept qaccept Qaccept 0 “清空”片： Qaccept Qaccept Qaccept Qaccept qaccept I U 4、(5分)把1中的计算过程写两遍，一个写在另一个的上面。并标记在本匹配中的MPCP小片 的边界。你可以跳过那些和计算终止有关的部分，只要标记那些与一个接受状态有关的小片。 问题3：(15分)假设我们有一个图灵机M,对于任何的输入字符串x,M或者在其带子上输 出一个字符串，或者就永远的循环下去。简单的描述怎样创建一个图灵机枚举器E来枚举M在 所有的输入上产生的输出。 问题4：(20分)设EVENODD={M是那些接受所有长度为偶数字符串的机器，并且只 接受长度为偶数的字符串}。 1、(2分)Rice定理对EVENODD适用吗？为什么？如果适用，那么我们可以得出什么样的结论。 2、(9分)EVENODD是图灵机可识别的吗？证明你的结论。 3、(9分)EVENODD的补是图灵可识别的吗？证明你的结论。 问题5：(15分)设L是下列图灵机描述的语言{M是一个字母表为{0,1的图灵机，并 且M接受所有只含有0的字符串（它可能接受其他的字符串）} 请使用递归定理证明L是不可判定的。下面是一个不完整的证明，请将其填写完整。 假设为了得出下列矛盾 定义D为 同时定义图灵机R: R:在输入w上作如下的事情： 包含 这是能够做到的，因为有 在输入 上运行D 如果D接受，则有 如果D拒绝，则有 如果R接受所有只含0的字符串，那么 ,而这个结论可以推出： ,很明显这是不可能的：另一方面，假如R不能接受所有 只含有0的字符串，那么 ，这个可以推出下列结论 这也是不可能的。 这样我们就有了一个矛盾，因此L是不可判定的。 问题6：（10分)我们假设有一个称为k-队列机器的新机器。它和k-计数器以及k栈机器的
3、（10 分）针对本特殊的机器 M 以及输入 01，给出修正的 PCP 所对应的小片集合，并指明那 个是初始片。题目已经给出了最终的结果，你只需要完成前面的初始小片以及移动所需要的片。 初始化片： 右移的片： 左移的片： 字母表片： “清空”片： 4、（5分）把1中的计算过程写两遍，一个写在另一个的上面。并标记在本匹配中的MPCP小片 的边界。你可以跳过那些和计算终止有关的部分，只要标记那些与一个接受状态有关的小片。 问题 3：（15 分）假设我们有一个图灵机 M，对于任何的输入字符串 x，M 或者在其带子上输 出一个字符串，或者就永远的循环下去。简单的描述怎样创建一个图灵机枚举器 E 来枚举 M 在 所有的输入上产生的输出。 问题 4：（20 分）设 EVENODD={|M 是那些接受所有长度为偶数字符串的机器，并且只 接受长度为偶数的字符串}。 1、 (2分)Rice定理对EVENODD适用吗？为什么？如果适用，那么我们可以得出什么样的结论。 2、 (9 分) EVENODD 是图灵机可识别的吗？证明你的结论。 3、 (9 分) EVENODD 的补是图灵可识别的吗？证明你的结论。 问题 5：（15 分）设 L 是下列图灵机描述的语言{| M 是一个字母表为{0,1}的图灵机，并 且 M 接受所有只含有 0 的字符串(它可能接受其他的字符串)} 请使用递归定理证明 L 是不可判定的。下面是一个不完整的证明，请将其填写完整。 假设为了得出下列矛盾_____________________________________________ 定义 D 为_________________________________________________________ 同时定义图灵机 R： R：在输入 w 上作如下的事情： 包含______________________________________________ 这是能够做到的，因为有________________________________ 在输入____________________上运行 D 如果 D 接受，则有________________ 如果 D 拒绝，则有________________ 如果 R 接受所有只含 0 的字符串，那么____________________________，而这个结论可以推出： __________________________________,很明显这是不可能的；另一方面，假如 R 不能接受所有 只含有 0 的字符串，那么______________________________________，这个可以推出下列结论 __________________________________，这也是不可能的。 这样我们就有了一个矛盾，因此 L 是不可判定的。 问题 6：（10 分）我们假设有一个称为 k-队列机器的新机器。它和 k-计数器以及 k 栈机器的
结构基本上相同，只是它用的存储是k个队列。初始的时候每个队列都是空的。 它支持如下的操作（假设「是队列符号的字母表） 1、进队列：把Γ中的一个符号加入到队列q的最后。 2、出队列：如果q不为空，则把q队列的最前面的元素移出队列，否则，不做任何操作。 3、空判断：布尔操作，如果队列空则返回1，否则0。 简要的说明论证一下为什么2队列机器的接受问题是一个不可判定的问题
结构基本上相同，只是它用的存储是 k 个队列。初始的时候每个队列都是空的。 它支持如下的操作（假设Γ是队列符号的字母表） 1、 进队列：把Γ中的一个符号加入到队列 q 的最后。 2、 出队列：如果 q 不为空，则把 q 队列的最前面的元素移出队列，否则，不做任何操作。 3、 空判断：布尔操作，如果队列空则返回 1，否则 0。 简要的说明论证一下为什么 2 队列机器的接受问题是一个不可判定的问题