Язык с рекурсивным перечислением

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

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

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

• 1 Определения
• 2 Пример
• 3 Свойства замыкания
• 4 Ссылки
• 5 Внешние ссылки

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

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

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

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

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

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

• проблема почтового соответствия
• смертность (теория вычислимости)
• Entscheidungsproblem

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

• звезда Клини $L\; \ast \; \{\backslash \; displaystyle\; L\; ^\; \{*\}\}$из L
• конкатенация $L\; \circ \; P\; \{\backslash \; displaystyle\; L\; \backslash \; circ\; P\}$из L и P
• соединение $L\; \cup \; P\; \{\backslash \; displaystyle\; L\; \backslash \; cup\; P\}$
• intersection $L\; \cap \; P\; \{\backslash \; displaystyle\; L\; \backslash \; cap\; P\}$.

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

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

• Complexity Zoo : Class RE
• Слайды лекций