Рекурсивно перечисляемый язык - Recursively enumerable language

В математике , логике и информатике , А формальный язык называются перечислимый (также узнаваемы , частично разрешимы , полуразрешимый , Тюринг приемлемого или Тюринг узнаваемый ) , если это перечислимое подмножество в множестве всех возможных слов над алфавитом из язык, т. е. существует ли машина Тьюринга, которая перечислит все допустимые строки языка.

Рекурсивно перечисляемые языки известны как языки типа 0 в иерархии формальных языков Хомского . Все обычные , контекстно- зависимые , контекстно-зависимые и рекурсивные языки рекурсивно перечислены.

Класс всех рекурсивно перечислимых языков называется RE .

Определения

Есть три эквивалентных определения рекурсивно перечислимого языка:

1. Перечислимый языком является перечислимым подмножеством в множестве всех возможных слов над алфавитом из языка .
2. Рекурсивно перечисляемый язык - это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция ), которая будет перечислять все допустимые строки языка. Обратите внимание, что если язык бесконечен , предоставленный алгоритм перечисления может быть выбран так, чтобы он избегал повторений, поскольку мы можем проверить, является ли строка, созданная для числа n , «уже» созданной для числа, которое меньше n . Если он уже создан, используйте вместо этого вывод для ввода n + 1 (рекурсивно), но снова проверьте, является ли он «новым».
3. Рекурсивно перечисляемый язык - это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая будет останавливаться и принимать при представлении любой строки на языке в качестве входных данных, но может либо останавливаться и отклонять, либо зацикливаться навсегда при представлении строки не на языке. Сравните это с рекурсивными языками , которые требуют, чтобы машина Тьюринга останавливалась во всех случаях.

Все обычные , контекстно- зависимые , контекстно-зависимые и рекурсивные языки рекурсивно перечислены.

Теорема Поста показывает, что RE вместе с его дополнительным co-RE соответствуют первому уровню арифметической иерархии .

пример

Набор останавливающихся машин Тьюринга рекурсивно перечислим, но не рекурсивен. В самом деле, можно запустить машину Тьюринга и принять, если машина остановится, следовательно, она рекурсивно перечислима. С другой стороны, проблема неразрешима.

Некоторые другие рекурсивно перечисляемые языки, которые не являются рекурсивными, включают:

• Проблема с почтовой корреспонденцией
• Смертность (теория вычислимости)
• Entscheidungsproblem

Свойства закрытия

Рекурсивно перечислимые языки (REL) закрываются при выполнении следующих операций. То есть, если L и P - два рекурсивно перечислимых языка, то следующие языки также рекурсивно перечислимы:

• Клини звезда из L${\ Displaystyle L ^ {*}}$
• конкатенации из L и P${\ Displaystyle L \ circ P}$
• союз ${\ Displaystyle L \ чашка P}$
• пересечение . ${\ Displaystyle L \ cap P}$

Языки с рекурсивным перечислением не закрываются из-за различия или дополнения множеств . Установленная разница - рекурсивно перечислима, если рекурсивна. Если рекурсивно перечислимо, то дополнение к рекурсивно перечислимо тогда и только тогда, когда оно также рекурсивно. ${\ displaystyle L}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle L}$${\ displaystyle L}$${\ displaystyle L}$

Рекомендации

• Sipser, М. (1996), Введение в теорию вычислений , PWS Publishing Co .
• Козен, Д.К. (1997), Автоматы и вычислимость , Springer .

внешние ссылки

• Зоопарк сложности : класс RE
• Слайды лекций