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<b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为i+1, 转第2步； 5)若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为空格, 左移并将当前地址位改为空格直到到一个地址位其值<b，将当前地址位改为i+1, 转第2步；若到了地址带的最左端仍有当前地址位为b，则拒绝；
6)若N进入接受状态，则接受；否则，右移一格，将空格上写入1，转第三步。”
由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停机。
3.4 给出枚举器的形式定义。
解：枚举器E=(Q, , , ,q0,qaccept,qreject), 其中转移函数 为：
：Q× Q× ×{L,R}× *
(q,a)=(r,b,s1,c)
表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写为b并按s1作相应左或右移，打印带上写下字符串c，其中若c等于 ，则不打印。 另外E的起始格局只能是q0v，这里v表示一个空格。
3.5 检查图灵机的形式定义，回答下列问题并解释你的推测： a．图灵机能在它的带子上写下空白符吗
b．带字母表 和输入字母表 能相同吗？
c．图灵机的读写头能在连续的两步中处于同一个位置吗？
d．图灵机能只包含一个状态吗？
皂基
解：
a．能。因为空白符属于带字母表 ；
b．不能。因为空白符不属于输入字母表 ；
c．能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的左端点移出，所以下一个格局读写头仍在左端点。
d．不能。因为qaccept qreject，至少应有两个状态。
3.6 解：因为M不一定是判定器，可能会在运行某个si时不停机，则L(M)中按字典序大于si的字符串不可能被枚举出来。
3.7 解：因为图灵机的一个本质要求是一步之内，只能做有限的工作，而第1)步中取所有可能的值，这有无限多种情况。
3.8构造具有3条带的图灵机。
对于问题a.
1)w 先读入第一条带，然后读到0就把0写入第2条带，读到1就把1写入第3条带，直到读到空格为止。
2)然后把3个读写头都返回到最左边。
脱套伤
3)开始读第2条带和第3条带，每次都是读一个字符，如果同时遇上空格符，则接收，否则拒绝。
对于问题b:
1)图灵机和a的第1步相同。
2)和a的第2步相同。
3)每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就接收，否则拒绝。
对于问题c:
1)和a的第1步相同。
2)和a的第2步相同。
3)每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就拒绝，否则接受。
3.9由题知,1-pda代表一个栈的下推自动机,2-pda代表两个栈的下推自动机。如果能用2-pda
模拟一个图灵机,而我们已经知道图灵机比下推自动机强大，那么就有2-pda比1-pda更强大。设有TM S。下面构造2-pda P，且记其两个栈分别为A，B：
P＝“对于输入w,
1) 将w读入栈A，再全部从栈A中依次弹出并读入栈B。
2) 模拟S在w上运行。记录S的当前状态，并且栈B的栈顶字符为S的读写头所指方格的字符：
a)若S执行一个右移 (q,a)=(r,b,R)，则将栈B的栈顶字符a替换为b，弹出b，推入栈A，记录S的当前状态r。
b)若S执行一个左移 (q,a)=(r,b,L)，首先将栈B的栈顶字符a替换为b；若栈A不空，则将栈A弹出一个字符推入栈B；若栈A为空(对应于S处于工作带最左端)，则不作栈操作。记录S的当前状态r。
3) 若S进入接受状态，则进入接受状态。”
由上知.我们用2-pda模拟了图灵机,所以2-pda比1-pda强大.
下面用一个四带TM S来模拟一个3-pda P，要求P进入接受状态之前排空栈，并且或者推入或者弹出：
记P的三个栈为A,B,C。S的四个带，第一带用来模拟P的输入带，第二,三,四带分别模拟栈A,B,C：
S＝“对于输入字符串w，
1)初始化，第一带放入w，第二，三，四带为空。
2)模拟P分别在四个带上按如下方式动作：
a．若P在输入带上读一个非空字符，则读第一带字符并右移一格；
若P在输入带上读一个 ，则在第一带上不读字符，且读写头保持不动。
b．栈A,B,C中若有弹出，则在相应带上当前格改写为空格，并左移一格；若有推入a，则在相应带上右移一格，并写入a。
3) 若P进入接受状态，则接受。”
3.10证明双无限带图灵机识别图灵可识别语言。
证明思路：利用双无限单带图灵机模拟普通单带图灵机时，只需要设计一个左端点。我们的证明是让它在第一格左边标记“$”作为左端点。 证明：
首先用单带双无限带图灵机模拟普通单带图灵机：
设有普通图灵机M1＝( Q未来100年大预言1, , 1张鸣岐, 1, q0, qaccept, qreject )。 下面构造与之等价的单带双无限带图灵机M2＝( Q2, , 2, 2, qs, qaccept, qreject )，其中
Q2=Q1 {qs,qt}, qs为新的起始状态； 2＝ 1 {$}.
对任意q Q2, a 2,
再用普通单带图灵机模拟单带双无限带图灵机：
设有单带双无限图灵机M1＝(Q, , , ,q0,qaccept,qreject)，下面构造普通单带图灵机M2：
M2=“输入串w，
1)将带上字符串改写为$w, 将读写头放在w的第一个字符上，
2)按照M1的转移函数运行，
3)每当读写头移到了$上，就将$右边的所有字符右移一格，并在$右边的方格里写上空格符，再将读写头放在这个方格上，转第二步，
多普达535
4)若进入接受状态，则接受；若进入拒绝状态则拒绝。”
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议