超过{1}的语言是可识别但不可确定的？

Question

字母表{1}*上的可识别但不可判定的语言的示例是什么？

我很难找到这样的例子。经过长时间的寻找，我仍然对答案很好奇。

一个提示将非常受欢迎。

Answer 1

由于任何有限字母表上的字符串域都是可数的，因此每种语言都可以映射到自然数的子集。因此，您只需将一种不可判定的递归可枚举语言映射到{1}*的子集。

例如，在停机问题的经典版本中，我们将每个图灵机枚举成一个二进制字符串；您现在可以对所有图灵机进行排序，并定义一个从图灵机到f : TM -> N 的映射，其中f(TM) = n if TM是所有TM的有序列表中的nth图灵机。

现在，编码为一元数字的图灵机的停机问题是r.e。但不能断定。

Answer 2

假设有一台机器，给定两台字母表为{1}*的机器，如果第一台机器可以生成第二台机器可以生成的所有字符串，则接受第一台机器可以生成的所有字符串。

如果接受，我们的机器就会停止。但是对于不是该语言的字符串(第一个给定的机器不能生成第二个机器可以生成的所有字符串)，我们的机器可能会暂停并拒绝，或者可能永远不会停止。这意味着我们的图灵机是可识别的，但它是不可判定的。

有关可识别和不可判定语言的更多信息，请参阅Encyclopedia of Mathematics (具体地说，第56页)。

Answer 3

{1}*中唯一不可判定的子集是空集。

我们可以根据TM定义{1}*上的语言:l={|M是TM且L(M) =空}

因此，我们可以证明L是不可判定的，因为接收L作为输入的TM U需要测试{1}*上的所有元素，然后在M拒绝所有元素的情况下决定接受，因此它永远不会停止，这意味着L是不可判定的，意味着空语言是不可判定的