检查2种语言是否是图灵可识别的或co-Turing可识别的
Check whether 2 languages are Turing recognizable or co-Turing recognizable
我有这两种语言
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个是不可判定的，但我不确定它们是图灵可识别的还是co-Turing可识别的。
B 是图灵可识别的，因为我们可以在所有可能的输入磁带上交错执行 M。如果 M 的 运行ning 个实例中有超过 n 个停止接受，则停止接受。
我们知道 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 以外的字符串，构造为接受 L(M) \ {w} 每个可能的字符串 w。在每个阶段，我们 运行 所有现有机器的一个步骤，然后构建一个新机器，并重复，从而交错执行并确保所有 TM 最终到达 运行 任意多个步骤。
假设 |L(M)| = 1，这些 TM 中恰好有一个将停止接受（删除 L(M) 中唯一字符串的那个），其余的将停止拒绝或 运行永远。因此，|L(M)| != 1 的识别器可用于构造 |L(M)| = 1 的识别器。这通过减去所有可能的 k 输入字符串集推广到 |L(M)| != k 和 |L(M)| = k。
因此，如果 A 是共同图灵可识别的，那么它也将是图灵可识别的，因此是可判定的。我们已经知道那是错误的，所以我们必须得出结论 A 不是共同图灵可识别的；也不是图灵可识别的。
我有这两种语言
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个是不可判定的，但我不确定它们是图灵可识别的还是co-Turing可识别的。
B 是图灵可识别的，因为我们可以在所有可能的输入磁带上交错执行 M。如果 M 的 运行ning 个实例中有超过 n 个停止接受，则停止接受。
我们知道 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 以外的字符串，构造为接受 L(M) \ {w} 每个可能的字符串 w。在每个阶段，我们 运行 所有现有机器的一个步骤，然后构建一个新机器，并重复，从而交错执行并确保所有 TM 最终到达 运行 任意多个步骤。
假设 |L(M)| = 1，这些 TM 中恰好有一个将停止接受（删除 L(M) 中唯一字符串的那个），其余的将停止拒绝或 运行永远。因此，|L(M)| != 1 的识别器可用于构造 |L(M)| = 1 的识别器。这通过减去所有可能的 k 输入字符串集推广到 |L(M)| != k 和 |L(M)| = k。
因此，如果 A 是共同图灵可识别的，那么它也将是图灵可识别的，因此是可判定的。我们已经知道那是错误的，所以我们必须得出结论 A 不是共同图灵可识别的；也不是图灵可识别的。