递归语言

Question

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

第一：两种说法有区别吗？ 第二：它应该只是一个词典顺序吗？

Answer 1

回想之所以字典顺序为递归语言的定义是必要的：

• 语言是递归的，如果它可以决定。也就是说，对于给定的单词W和给定的语言L，可以在有限的许多步骤中知道W是否是L，或不是的成员。
• 语言如果可以是可接受可递归枚举。也就是说，对于给定的单词W和给定的语言L，可以在有限多个步骤中知道W是否是L的成员，但是可能知道W 是否是成员的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. 是两个不同的语句？
   是的。
   第一条语句陈述“以某种顺序排列”，其中没有指定该顺序必须是在L的字母表上的total order。因此第一个陈述是不正确的。第一条语句定义了一个递归枚举语言。
   第二种说法是正确的，但比它需要的限制性更强。字典顺序只是一个字母表上的总顺序。其他可以使用。

2. 它应该只是一个词典命令吗？
   如上所述，只要机器以字母顺序保证任何顺序的输出，语言就是递归的。