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

Question

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

我找到一个这方面的例子很麻烦.经过长时间的搜索,我仍然对这个答案感到好奇.

提示非常受欢迎.

Answer 1

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

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

有关可识别和不可判定语言的更多信息，请参阅数学百科全书（具体第 56 页）。