4、丘奇-图灵论题练习

2024-07-28 作者:

第4章、丘奇-图灵论题习题解答 - 练习

4.1、此练习和TM M2有关，例4.4给出了它的描述和状态图，它判定语言A{02|n0}。在下列每个输入串上，给出M2所进入的格局序列：

a. 0

b. 00

c.

000

nd. 000000

答：

a.

q10

、 q2

、 q20

、 qaccept

、 x q3

、 q5x

、q5

x

、 q2 x

b. q100

x q2

c.

q1000

、 x qaccept

、 q200

、 x q30 、 x0q4

、 x0qreject

、 x0q4000

、 x0xq50x

、 q2x0x0x

、 x0xq300

、 x0q5x0x

、 xq20x0x

d. q1000000

x0x0q40

xq50x0x

xxq3x0x

、 q200000

x0x0xq3

、 xq30000

、 x0x0q5x

、q5

x0x0x

、 q5x0x0x

xxxq30x

、 xxx0q4x 、 xxx0xq4

xxx0x qreject

1

4.2、此练习和TM M1有关，例4.5给出了它的描述和状态图，它判定语言B={w#w|w{0,1}*}。在下列每个输入串上，给出M1所进入的格局序列：

a. 11

b. 1#1

c.

1##1

d. 10#11

e.

10#10

答：

a.

q111

、 q31

b. q11#1

、 q3#1

q7

#1 、 q9#1

#q14x 、 #xq14

c.

q11##1 、 q3##1

d. q110#11 、 q30#11

0#1q71 、 0#q711

0q9#11、 0#q1111

xq8#x1、 x#q10x1

e.

q110#10 、 q30#10

0#1q70 、 0#q710

1q3 、 1qreject

#q51 、 #1q5

、 # q71

、 q7#1

#q111 、 q12# x 、q12

# x 、q13

# x

#x qaccept

#q5#1 、 #qreject #1

0q3#11 、 0#q511 、 0#1q51

、 0#11q5

0q7#11 、 q70#11 、q7

0#11 、 q90#11

0q12#x1

、 q120#x1

、q12

0#x1 、 q130#x1

x#xq101 、 x#xqreject1

0q3#10 、 0#q510 、 0#1q50

、 0#10q5

0q7#10

、 q70#10 、q7

0#10 、 q90#10

2

、、、、、、、、、、、0q9#10、 0#q1110

xq8#x0、 x#q10x0

、 0q12#x0 、 q120#x0 、q12

0#x0 、 q130#x0

、 q12x#xx

、 x#xxq14

、 x#xq100 、 x#q12xx 、 xq12#xx

、 x#q14xx 、 x#xq14x

q12

x#xx、 q13x#xx 、 xq13#xx

x#xx qaccept

4.3 修改定理4.10以得到推论4.12的证明，即证明一个语言是可判定的当且仅当有非确定型TM判定它。（可以假设关于树的下列定理成立：如果一个树中的每个结点只有有限多个子结点，且此树的每一个分枝只有有限多个结点，则此树本身只有有限个结点）。

证明：

定理4.10为：每个非确定型图灵机都有一个与之等价的确定型图灵机。

修改定理4.10为：每个非确定性判定器都有与之等价的确定型判定器。

现在设N是一个非确定性判定器，N 对所有输入，所有分枝都停机。构造一个与之等价的确定型判定器D。D有三个带：一个输入带，一个模拟带，一个地址带。D按“宽度优先”策略搜索N的不确定计算分枝树。

M= “输入w，

1) 开始时，输入带包含输入w, 模拟带和地址带都是空的。

2) 把输入带的内容复制到模拟带上。

3) 在模拟带上模拟N在输入w上的非确定性计算树的某个分枝。

a) 在N的每一步动作之前，查询地址带上的下一个数字，以决定在N的转移函

数所允许的选择中作何选择。

b) 如果地址带上下一个数字是空白，则放弃这个分枝，转到第四步。

c) 如果这个非确定性的选择是无效的，则放弃这个分枝，转到第四步。

d) 如果遇到拒绝格局，则放弃这个分枝，转到第四步。

e) 如果遇到接受格局，则接受这个输入。

4) 按照字典顺序取下一个地址串。根据假设非确定性计算树只有有限的结点，所以地

址串有一个上界Amax。

a) 如果下一个地址串已经超过Amax，则说明已经搜索了所有分枝，那么拒绝这

个输入。

b) 否则用下一个地址串来替代原有的串。转到第二步，以模拟N的计算的下一

个分枝。”

如果有一个非确定性判定器判定语言，根据上述证明，必有与之等价的确定型判定器判

3

定该语言，则该语言是可判定的。

如果一个语言是可判定的，则有一个确定性判定器判定该语言。确定性判定器自然是非确定型判定器，所以必有非确定型判定器判定它。

4.4 给出枚举器的形式定义。可将其看作一种双带图灵机，用它的第二个带子作为打印机。包括它所枚举的语言的定义。

解：枚举器E=(Q，，，，q0，qaccept，qreject), 其中转移函数为：

：Q×→Q××{L,R}××{R}

 (q，a)=(r，b，s1，c，R)

表示若E处于状态q，且在工作带上读到a，则状态转移到r，当前格改写为b并按s1

所指示的方向移动读写头，打印带上写下c并向右移动读写头。

4．5 检查图灵机的形式定义，回答下列问题并解释你的推测：

a． 图灵机能在它的带子上写下空白符吗？

b．带字母表和输入字母表能相同吗？

c．图灵机的读写头能在连续的两步中处于同一个位置吗？

d．图灵机能只包含一个状态吗？

解：

a.

能。因为空白符属于带字母表；

另外E的起始格局只能是q0。

L(E)={w|w是枚举器E打印出的串}

b. 不能。因为空白符不属于输入字母表；

c.

能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的左端点移出，所以下一个格局读写头仍在左端点。

d. 不能。因为qacceptqreject，至少应有两个状态。

4．6 定理4.13证明了一个语言是图灵可识别的当且仅当有枚举器枚举它。为什么不能用下列更简单的算法作为证明？像以前一样，s1，s2，。。。是∑*中所有的串。

E=“忽略输入，

1) 对于i=1，2，3，… 重复下列步骤。

2) 在si上运行M。

4

3) 如果它接受，则打印出si。”

答：因为M不一定是判定器，可能会在运行某个si时不停机，则L(M)中按字典序的序数大于si的字符串不可能被枚举出来。

这个思想和定理4.10中的“宽度优先”的策略类似。

4.7 下面描述的不是一个合法的图灵机，解释为什么。

Mbad=“输入是变元x1，x2，…，xk上的一个多项式p：

1) 让x1，x2，。。。，xk取所有可能的整数值。

2) 对所有这些值求p的值。

3) 只要某个取值使得p为0，则接受，否则拒绝”

答：因为图灵机的一个本质要求是一步只能做有限的工作。参考希尔伯特问题一节中图灵机M1的定义。

4.8 下面的语言都是字母表{0，1}上的语言，以实现水平的描述给出判定这些语言的图灵机：

a. {w|w包含相同个数的0和1}

b. {w|w所包含的0的个数是1的个数的二倍}

c.

{w|w所包含的0的个数不是1的个数的二倍}

答：构造具有3条带的图灵机。第一条带子是输入带，第二条带子存放输入串所包含的0，第三条带子存放输入串所包含的1。

对于问题a.

M1=“对于输入字符串w：

1) 扫描输入，读到0就把0写入第2条带，读到1就把1写入第3条带，直到读到空

白符为止。

2) 第2、3条带的读写头回到最左端。

3) 读第2、3条带，每次读一个字符，如果同时读出空白符，则接收，否则拒绝。”

对于问题b:

M2=“对于输入字符串w：

1) 扫描输入，读到0就把0写入第2条带，读到1就把1写入第3条带，直到读到空

白符为止。

2) 第2、3条带的读写头回到最左端。

3) 每次读带3的一个字符就读带2的两个字符。

4) 如果从带3上读出的字符是1，从带2上读出的两个字符都是0，转第3步。否则，

5

拒绝。

如果从带3上读出的字符是空白，从带2上读出的第一个字符也是空白，就接收，否则拒绝。”

对于问题c:

M3=“对于输入字符串w：

1) 运行M2。

2) 如果M2拒绝，则接受；如果M2接受，则拒绝。”

4.18 设多项式c1xn+c2xn-1+…+cnx+cn+1有根x=x0，cmax是ci的最大绝对值。证明

|x0|(n1)cmax

|c1|证明：

1) 当|x0|1时，由条件cmax|c1| 知不等式显然成立。

3) 当|x0|>1时，由

c1x0nc2x0n1...cnx0cn10c1x0n(c2x0n1...cnx0cn1)(c2x0n1...cnx0cn1)c1x0x0n111c1x(c2...cnn2cn1n1)x0x0取绝对值

|c1||x0||c2...cn1x0n2cn11x0n1|11|c|

n1|x0|n2|x0|n1 |c2|...|cn||cn1| |c2|...|cn|

最后得到

|c1||x0|ncmax<(n1)cmax

|x0|(n1)cmax

|c1| 6