turing-machines - 集合在大小范围方面的可识别性

Question

试图自学计算理论，偶然发现了这个问题：

假设我们有两个集合：

1. {T | T 是图灵机，L(T) 至少包含 1001 个字符串}
2. {T | T 是图灵机，L(T) 最多包含 1001 个字符串}

其中一个是可识别的，另一个则不是。

哪个是哪个，为什么？

直觉上，我认为具有“至少 1001 个字符串”的那个是无法识别的，因为它没有字符串数量的上限，所以这个数字可能是无限的，但同样一些无限的语言应该是可识别的。

我对这个问题很困惑。表明一组可识别而另一组不可识别的正确直觉和正式方法是什么？

标签： turing-machineslanguage-theorydecidable

Answer 1

为了建立关于如何判断一种语言是否可识别、可判定等的直觉，我建议查看我为可计算性理论课程整理的这些笔记。

我发现最有用的关键直觉是证明事物的想法——如果你有一个语言中的字符串，是否有一些你可以做的演示可以向持怀疑态度但诚实的观察者证明你是对的？因此，例如，在第一种语言的情况下，您可以告诉观察者“注意这个 - 我将在这组 1001 个字符串上运行这个 TM，我知道它会接受它们中的每一个最多 k 步。” 然后观察者可以观察 k 步并看到它接受了所有字符串，此时他们会确定你是对的，并且 TM 的编码确实是在该语言中。

另一方面，您能想出一个演示来证明 TM最多接受一定数量的字符串吗？我不能，那是因为没有通用的方法可以做到这一点。因此，第二种语言是不可识别的。但证明这是另一个步骤 - 您需要将一些已知的非 RE 语言简化为它，或者使用某种自我引用技巧来证明它不可识别。还有第三种方法——你可以证明它的补码是可识别但不可判定的，这将确保语言本身不可识别。最后一个选项在这里可能是最简单的——你能证明补码可以使用上面的参数来识别，然后证明语言不可判定吗？