大门|大门-CS-2004 |问题89

L1是∑上的递归可枚举语言。算法A有效地将其单词枚举为w1，w2，w3，…。将∑并集{#}上的另一种语言L2定义为{wi#wj:wi，wj∈ L1，i

S1 :  L1 is recursive implies L2 is recursive
S2 : L2 is recursive implies L1 is recursive 

以下哪项陈述是正确的？ （A） S1和S2都是真的 （B） S1为真，但S2不一定为真 （C） S2为真，但S1不一定为真 （D） 两者都不一定是真的 答复: （A） 说明： S1是真的。

如果L1是递归的，L2也必须是递归的。因为要检查单词w=wi#wj是否属于L2，我们可以将wi和wj赋予L1的决策者，如果两者都被接受，那么w属于L1，反之亦然。

S2是真的。

有了L2的决策器，我们可以对L1做出如下决策。设w1为算法A为L1枚举的第一个字符串。现在，为了检查单词w是否属于L1，制作一个字符串w′=w1#w，并将其交给L2的决策者，如果接受，则w属于L1，而不是L1。

因此，答案必须是（A）。 这个问题的小测验