子语言不是图灵可识别的，或者可以吗？

Question

设 A 和 B 是 A ⊆ B 的语言，并且 B 是图灵可识别的。A 不能被图灵识别吗？如果有的话，有什么例子吗？

Answer 1

这是使许多学生感到困惑的事情。这里的重点是，作为另一种语言的子集并不意味着它们的计算困难。您始终可以考虑琐碎的语言$ emptyset $和$ sigma^*$，并且它们之间的任何其他语言都在wrt set包含之间。

因此，仅知道语言包含或包含在易于计算的语言中并没有说明计算它的困难。

Answer 2

当图灵可识别的语言$ x $是 不是 可决定性的，这意味着它不是可识别的（换句话说：$ x^c $无法识别）。由于$ x^c $是$ sigma^*$的一个非常有效的子集，因此这支持了以下事实：对于语言$ a subseteq b $，其中$ b $ turing-b $是图灵可识别的，$ a $ a $可能不太可能不是。

Answer 3

您的讨论成功使我混淆了:(

“ A不能公认吗？”

我觉得A总是可以识别的. 。这是我的想法

由于b是turing可识别=>有一些tm接受语言b =>的所有单词，因此有一个tm接受（所有语言的单词a + listher n of dosect）=>有一个接受所有单词的tm语言a => a是可以识别的。

这是错误的吗？在B为TRL时，可以在任何情况下a是非trl的。 请帮助

Answer 4

在这种情况下，A 无法被图灵识别。以此为例：

语言 B 是语言 t.r (C) 和语言非 t.r(A) 的并集。你可以创建一个识别 B 的图灵机。A 不是 t.r 并且 A ⊆ B。

是对的吗？我不知道是不是..所以..=)