Рекурсивный язык

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
https://en.wikipedia.org/wiki/Kleene%E2%80%93Brouwer_order

Итак, чтобы ответить на ваши конкретные вопросы:

1. Отличаются ли эти два утверждения?
   Да.
   Первый оператор заявляет "в некоторой последовательности", которая не указывает, что последовательность должна быть полным порядком по алфавиту L. Поэтому первое утверждение неверно. Первое утверждение определяет рекурсивно перечислимый язык.
   Второе утверждение верно, но оно более ограничительно, чем должно быть. Лексикографический порядок - это всего один общий порядок над алфавитом. Другие могут быть использованы.

2. Должен ли это быть только лексикографический порядок?
   Нет.
   Как и выше, до тех пор, пока машина гарантирует вывод в любом общем порядке по алфавиту, язык является рекурсивным.