turing-machines - 检查 2 种语言是图灵可识别的还是共同图灵可识别的

Question

我有这两种语言

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 }

我相信这两个是不可判定的，但我不确定它们是图灵可识别的还是共同图灵可识别的。

Answer 1

BM是图灵可识别的，因为我们可以在所有可能的输入磁带上交错执行。如果超过停止接受n的正在运行的实例M，则停止接受。

我们知道这A不可能是图灵可识别的，因为如果是这样，该语言B' = {<N> | N is a TM and L(N) contains no more than n strings }将是图灵可识别的（我们可以交错执行 1、2、...、n 和停止接受的识别器，如果有的话）。这意味着两者B都是可确定的B'，因为B'必须是共同图灵可识别的。

如果A共同图灵可识别，我们可以识别接受许多不同于n. 特别是，让n = 1. 我们可以为语言包含非n字符串的机器运行识别器，TM 构造为接受L(M) \ {w}每个可能的字符串w。在每个阶段，我们运行所有现有机器的一个步骤，然后构建一台新机器并重复，从而交错执行并确保所有 TM 最终可以运行任意多个步骤。

假设|L(M)| = 1，这些 TM 中恰好有一个将停止接受（删除 中唯一字符串的那个L(M)），其余的将停止拒绝或永远运行。因此，一个识别器|L(M)| != 1可以用来构造一个识别器|L(M)| = 1。这可以概括为|L(M)| != k并|L(M)| = k减去所有可能的k输入字符串集。

因此，如果 A 是共同图灵可识别的，那么它也是图灵可识别的，因此是可判定的。我们已经知道这是错误的，所以我们必须得出结论 A 不是协同图灵可识别的；也不是图灵可识别的。