2024年3月29日发(作者：百男)
3.3 修改定理3.10以得到推论3.12的证明，即证明一个语言是可判定的当且
仅当有非确定的TM判定它。
证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。
现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器
M。模拟过程使用深度搜索。
设N的不确定性分支的最大个数为b。
M有三个带：一个输入带，一个工作带，一个地址带。M按深度优先方
式搜索N的不确定计算分支树。
M= “输入w，
1) 初始化，第一带上为w, 第二带为空，第三带为1;
2) 将第一带的内容复制到第二带上，
3) 按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N
运行一步；
4) 若当前地址位为i 态，则将当前地址位改为i+1, 转第2步； 5) 若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状 态，则将当前地址位改为空格, 左移并将当前地址位改为空格直 到找到一个地址位其值 到了地址带的最左端仍有当前地址位为b，则拒绝； 6) 若N进入接受状态，则接受；否则，右移一格，将空格上写入1， 转第三步。” 由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停 机。 3.4 给出枚举器的形式定义。 解：枚举器E=(Q,,,,q 0 ,q accept ,q reject ), 其中转移函数为： ：Q×Q××{L,R}× * (q,a)=(r,b,s 1 ,c) 表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写 为b并按s 1 作相应左或右移，打印带上写下字符串c，其中若c等于，则 不打印。 另外E的起始格局只能是q 0 v，这里v表示一个空格。 3.5 检查图灵机的形式定义，回答下列问题并解释你的推测： a．图灵机能在它的带子上写下空白符吗 b．带字母表和输入字母表能相同吗？ c．图灵机的读写头能在连续的两步中处于同一个位置吗？ d．图灵机能只包含一个状态吗？ 解： a．能。因为空白符属于带字母表； b．不能。因为空白符不属于输入字母表； c．能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的 左端点移出，所以下一个格局读写头仍在左端点。 d．不能。因为q accept q reject ，至少应有两个状态。 3.6 解：因为M不一定是判定器，可能会在运行某个s i 时不停机，则L(M)中 按字典序大于s i 的字符串不可能被枚举出来。 3.7 解：因为图灵机的一个本质要求是一步之内，只能做有限的工作，而第 1)步中取所有可能的值，这有无限多种情况。 3.8构造具有3条带的图灵机。 对于问题a. 1) w 先读入第一条带，然后读到0就把0写入第2条带，读到1就把1 写入第3条带，直到读到空格为止。 2) 然后把3个读写头都返回到最左边。
2024年3月29日发(作者：百男)
3.3 修改定理3.10以得到推论3.12的证明，即证明一个语言是可判定的当且
仅当有非确定的TM判定它。
证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。
现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器
M。模拟过程使用深度搜索。
设N的不确定性分支的最大个数为b。
M有三个带：一个输入带，一个工作带，一个地址带。M按深度优先方
式搜索N的不确定计算分支树。
M= “输入w，
1) 初始化，第一带上为w, 第二带为空，第三带为1;
2) 将第一带的内容复制到第二带上，
3) 按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N
运行一步；
4) 若当前地址位为i 态，则将当前地址位改为i+1, 转第2步； 5) 若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状 态，则将当前地址位改为空格, 左移并将当前地址位改为空格直 到找到一个地址位其值 到了地址带的最左端仍有当前地址位为b，则拒绝； 6) 若N进入接受状态，则接受；否则，右移一格，将空格上写入1， 转第三步。” 由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停 机。 3.4 给出枚举器的形式定义。 解：枚举器E=(Q,,,,q 0 ,q accept ,q reject ), 其中转移函数为： ：Q×Q××{L,R}× * (q,a)=(r,b,s 1 ,c) 表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写 为b并按s 1 作相应左或右移，打印带上写下字符串c，其中若c等于，则 不打印。 另外E的起始格局只能是q 0 v，这里v表示一个空格。 3.5 检查图灵机的形式定义，回答下列问题并解释你的推测： a．图灵机能在它的带子上写下空白符吗 b．带字母表和输入字母表能相同吗？ c．图灵机的读写头能在连续的两步中处于同一个位置吗？ d．图灵机能只包含一个状态吗？ 解： a．能。因为空白符属于带字母表； b．不能。因为空白符不属于输入字母表； c．能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的 左端点移出，所以下一个格局读写头仍在左端点。 d．不能。因为q accept q reject ，至少应有两个状态。 3.6 解：因为M不一定是判定器，可能会在运行某个s i 时不停机，则L(M)中 按字典序大于s i 的字符串不可能被枚举出来。 3.7 解：因为图灵机的一个本质要求是一步之内，只能做有限的工作，而第 1)步中取所有可能的值，这有无限多种情况。 3.8构造具有3条带的图灵机。 对于问题a. 1) w 先读入第一条带，然后读到0就把0写入第2条带，读到1就把1 写入第3条带，直到读到空格为止。 2) 然后把3个读写头都返回到最左边。