遞歸語言

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. 它應該只是一個詞典命令嗎？
   如上所述，只要機器以字母順序保證任何順序的輸出，語言就是遞歸的。