我有这2种语言
A = {<M> | M is a TM and L(M) contains exactly n strings }
B = {<N> | N is a TM and L(N) contains more than n strings }
我相信这 2 个是不可判定的，但我不确定它们是图灵可识别的还是共同图灵可识别的。
B是图灵可识别的，因为我们可以在所有可能的输入磁带上交错执行M。如果超过n个正在运行的实例M停止接受，则停止接受。
我们知道A不能是图灵可识别的，因为如果是，语言B' = {<N> | N is a TM and L(N) contains no more than n strings }将是图灵可识别的(我们可以交错执行识别器 1、2、...、n 和 halt-accept，如果其中任何一个)。这意味着B和B'都是可判定的，因为B'必须是共同图灵可识别的。
如果A是可识别的，我们可以识别接受许多不同于n字符串的机器。特别是，让我们n = 1.我们可以在 TM 上为语言包含n字符串以外的机器运行识别器，以接受每个可能的字符串w的L(M) {w}。在每个阶段，我们运行所有现有机器的一个步骤，然后构建一台新机器，然后重复，从而交错执行并确保所有 TM 最终运行任意多个步骤。
假设|L(M)| = 1，这些TM中的一个将停止接受(删除L(M)中唯一字符串的那个)，其余的将停止拒绝或永远运行。因此，|L(M)| != 1的识别器可用于构造|L(M)| = 1的识别器。这通过减去所有可能的k输入字符串集来推广到|L(M)| != k和|L(M)| = k。
因此，如果 A 是共图灵可识别的，那么它也将是图灵可识别的，因此是可判定的。我们已经知道这是错误的，所以我们必须得出结论，A不是共图灵可识别的;也不是图灵可识别的。