computation-theory - 递归语言

Question

“如果一种语言是递归的，那么存在一种方法可以按某种顺序编写语言中的字符串” 我还被告知“如果某种语言可以通过某些图灵机按字典顺序枚举，那么这种语言称为递归”

首先:这两种说法是不同的吗？ 第二:是否应该只按字典序排列？

Answer 1

回想一下为什么定义递归语言需要字典顺序的原因:

• 如果可以决定，则语言是递归的。也就是说，对于给定的单词 W 和给定的语言 L，可以通过有限多个步骤知道 W 是否是 L 的成员，或不是。
• 如果一种语言可以被接受，那么它就是递归可枚举的。也就是说，对于给定的单词 W 和给定的语言 L，可以通过有限多步知道 W 是否是 L 的成员，但是不可能知道 W < em>不是 L 的成员。

因此，如果机器只是以任意顺序枚举 L 中的单词，您可以检查您的单词 W 是否在该列表中。如果是，你就停下来。如果不是，你必须永远等待，看看你的词是否最终被机器输出。该语言是递归可枚举的。

不过，如果您知道顺序，您可以评估机器现在是否应该输出 W。如果机器输出了一个单词 X，并且根据你知道机器正在使用的顺序，W 在 X 之前，你知道机器永远不会输出 W，所以你知道 W 不是 L 的成员。

词典顺序是满足属性的众多单词总排序之一，您可以判断单词 W 应该 何时输出，因此如果到那时您还没有看到它，您可以停止。

其他订单:
https://en.wikipedia.org/wiki/Lexicographical_order#Colexicographic_order
https://en.wikipedia.org/wiki/Kleene%E2%80%93Brouwer_order

所以回答你的具体问题:

1. 这两个说法有区别吗？
   是的。
   第一条语句声明“按某种顺序”，它没有指定序列必须是 total order。在 L 的字母表上。因此第一种说法是错误的。第一条语句定义了递归可枚举语言。
   第二个陈述是正确的，但比它需要的更严格。词典顺序只是一个字母表的总顺序。其他的也可以。

2. 是否应该只按字典序排列？
   没有。
   如上，只要机器保证按字母表上的任何全序输出，该语言就是递归的。