按字典序枚举图灵可识别语言

Question

所以图灵可识别的语言也是可枚举的。

但是枚举器是否有可能 "print" 一种按字典顺序排列的图灵可识别语言？

Answer 1

没有。假设这是可能的。那么语言可以决定如下：

1. 开始按顺序枚举所有接受的字符串。
2. 如果您列出的字符串的字典顺序大于您要查找的字符串，请停止拒绝。
3. 如果列出要查找的字符串，请停止接受。

对于任何输入字符串，这最终都会终止，因为对于任何给定的输入字符串，只有有限多个枚举字符串以较小的字典顺序存在。如果找不到您的目标字符串，它将始终停止拒绝，如果找到，它将始终停止接受。它不必担心丢失您的字符串，因为它知道您的字符串应该在哪里，这要归功于按顺序列出的字符串。

既然我们知道有不可判定的可枚举语言，那肯定是我们不能按顺序枚举可枚举语言。