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

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

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

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

Определения

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

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

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

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

Пример

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

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

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

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

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

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

Рекурсивно перечислимые языки не замкнуты относительно множества различий или дополнений. Разница в наборе $L-P$ является рекурсивно перечислимым, если $P$является рекурсивным. Если $L$ рекурсивно перечислимо, то дополнение $L$ рекурсивно перечислим тогда и только тогда, когда $L$ также является рекурсивным.

См. также

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

Источники

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

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

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