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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Вычислимо перечислимое множество
• Рекурсия

• Сипсер, М. (1996), Введение в теорию вычислений , PWS Publishing Co.
• Козен, округ Колумбия (1997), Автоматы и вычислимость , Springer .

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