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

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

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

Класс всех рекурсивных языков часто называют R , хотя это название также используется для класса RP .

Этот тип языка не был определен в иерархии Хомского . ^[2] Все рекурсивные языки также рекурсивно перечислимы . Все регулярные , контекстно-свободные и контекстно-зависимые языки являются рекурсивными.

Определения

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

1. Рекурсивный формальный язык — это рекурсивное подмножество во множестве всех возможных слов в алфавите языка .
2. Рекурсивный язык — это формальный язык, для которого существует машина Тьюринга , которая при предъявлении любой конечной входной строки останавливается и принимает, если строка находится в языке, и останавливается и отклоняет в противном случае. Машина Тьюринга всегда останавливается: она известна как решатель и , как говорят, определяет рекурсивный язык.

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

Примеры

Как было отмечено выше, каждый контекстно-зависимый язык является рекурсивным. Таким образом, простым примером рекурсивного языка является множество L={abc, aabbcc, aaabbbccc, ...} ; более формально, множество

${\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}}$

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

Примеры разрешимых языков, не зависящих от контекста, описать сложнее. Для одного такого примера требуется некоторое знакомство с математической логикой : арифметика Пресбургера — это теория первого порядка натуральных чисел со сложением (но без умножения). В то время как множество правильно сформированных формул в арифметике Пресбургера является контекстно-свободным, каждая детерминированная машина Тьюринга, принимающая множество истинных утверждений в арифметике Пресбургера, имеет худшее время выполнения не менее , для некоторой константы c >0. ^[3] Здесь n обозначает длину данной формулы. Поскольку каждый контекстно-зависимый язык может быть принят линейным ограниченным автоматом , и такой автомат может быть смоделирован детерминированной машиной Тьюринга с худшим временем выполнения не более для некоторой константы c ^{[ требуется ссылка ]} , множество допустимых формул в арифметике Пресбургера не является контекстно-зависимым. С положительной стороны, известно, что существует детерминированная машина Тьюринга, работающая за время, не превышающее трижды экспоненциальную величину от n , которая определяет множество истинных формул в арифметике Пресбургера. ^[4] Таким образом, это пример языка, который является разрешимым, но не контекстно-зависимым. ${\displaystyle 2^{2^{cn}}}$ ${\displaystyle c^{n}}$

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

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

• Звезда Клини ${\displaystyle L^{*}}$
• Образ φ(L) при e-свободном гомоморфизме φ
• Конкатенация ${\displaystyle L\circ P}$
• Профсоюз ${\displaystyle L\cup P}$
• Пересечение ${\displaystyle L\cap P}$
• Дополнение ${\displaystyle L}$
• Разница в наборе ${\displaystyle L-P}$

Последнее свойство следует из того факта, что разность множеств может быть выражена через пересечение и дополнение.

Смотрите также

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

Ссылки

1. Сипсер (1997).
2. Хомский (1959).
3. Фишер и Рабин (1974).
4. Оппен (1978).

• Хомский, Ноам (1959). «О некоторых формальных свойствах грамматик». Информация и управление . 2 (2): 137–167. doi :10.1016/S0019-9958(59)90362-6.
• Фишер, Майкл Дж .; Рабин, Майкл О. (1974). «Суперэкспоненциальная сложность арифметики Пресбургера». Труды симпозиума SIAM-AMS по прикладной математике . 7 : 27–41.
• Оппен, Дерек К. (1978). «Верхняя граница сложности арифметики Пресбургера в 222pn». J. Comput. Syst. Sci . 16 (3): 323–332. doi : 10.1016/0022-0000(78)90021-1 .
• Сипсер, Майкл (1997). «Разрешимость» . Введение в теорию вычислений . PWS Publishing. стр. 151–170. ISBN 978-0-534-94728-6.