What is an example of a language over the alphabet {1}* which is recognizable but not decidable?
I have troubles finding an example of this. After a long search, I am still curious for the answer though.
A hint would be very welcome.
问问题
6741 次
3 回答
3
由于任何有限字母表上的字符串都是可数的，因此每种语言都可以映射到自然数的子集。因此，您只需采用不可判定的递归可枚举语言并将其映射到 {1}* 的子集。
例如，在停止问题的经典版本中，我们将每个图灵机枚举为二进制字符串；您现在可以对所有图灵机进行排序并定义f : TM -> N从图灵机到整数的映射，其中f(TM) = n如果 TM 是nth所有 TM 的有序列表中的图灵机。
现在，编码为一元数的图灵机的停机问题是可解决的，但不可判定。
于 2012-12-02T19:39:30.043 回答
1
想象一台机器给定两台字母为 {1}* 的机器，如果第一台机器可以生成第二台机器可以生成的所有字符串，则接受它。
如果它接受，我们的机器就会停止。但是对于不是该语言的字符串（第一个给定的机器不能生成第二个可以生成的所有字符串），我们的机器可能会停止并拒绝，或者可能永远不会停止。这意味着我们的图灵机是可识别的，但它是不可判定的。
有关可识别和不可判定语言的更多信息，请参阅数学百科全书（特别是第 56 页）。
于 2012-12-02T19:37:45.413 回答
0
{1}* 中唯一不可判定的子集是空集。
我们可以根据 TM 在 {1}* 上定义语言： L = { < M > | M 是一个 TM 并且 L(M) = 空 }
所以我们可以证明 L 是不可判定的，因为接收 L 作为输入的 TM U 需要测试 {1}* 上的所有元素，然后在 M 拒绝所有元素的情况下决定接受，所以它永远不会停止并且这意味着 L 不可判定，意味着空语言不可判定
于 2019-11-13T01:16:32.357 回答