В математике , логике и информатике формальный язык ( набор конечных последовательностей символов , взятых из фиксированного алфавита ) называется рекурсивным, если он является рекурсивным подмножеством множества всех возможных конечных последовательностей по алфавиту языка. Эквивалентно, формальный язык является рекурсивным, если существует машина Тьюринга, которая, когда на входе дана конечная последовательность символов, всегда останавливается и принимает ее, если она принадлежит языку, и останавливается и отвергает ее в противном случае. В теоретической информатике такие постоянно останавливающиеся машины Тьюринга называются полными машинами Тьюринга или алгоритмами . [1] Рекурсивные языки еще называют разрешимыми .
Понятие разрешимости может быть распространено на другие модели вычислений . Например, можно говорить о языках, разрешимых на недетерминированной машине Тьюринга . Поэтому всякий раз, когда возможна двусмысленность, синоним, используемый для «рекурсивного языка», — это разрешимый по Тьюрингу язык , а не просто разрешимый .
Класс всех рекурсивных языков часто называют R , хотя это имя также используется для класса RP .
Этот тип языка не был определен в иерархии Хомского . [2] Все рекурсивные языки также являются рекурсивно перечислимыми . Все обычные , контекстно-свободные и контекстно-зависимые языки рекурсивны.
Есть два эквивалентных основных определения понятия рекурсивного языка:
Согласно второму определению, можно показать, что любая проблема решения разрешима, представив для нее алгоритм , который завершается на всех входах. Неразрешимая проблема – это проблема, которая неразрешима.
Как отмечалось выше, каждый контекстно-зависимый язык является рекурсивным. Таким образом, простым примером рекурсивного языка является набор L={abc, aabbcc, aaabbbccc, ...} ; более формально, множество
является контекстно-зависимым и, следовательно, рекурсивным.
Примеры разрешимых языков, не зависящих от контекста, описать труднее. Для одного такого примера требуется некоторое знакомство с математической логикой : арифметика Пресбургера — это теория натуральных чисел первого порядка со сложением (но без умножения). Хотя набор правильно сформированных формул в арифметике Пресбургера является контекстно-свободным, каждая детерминированная машина Тьюринга, принимающая набор истинных утверждений в арифметике Пресбургера, имеет время выполнения в наихудшем случае не менее , для некоторой константы c > 0. [3] Здесь n обозначает длину данной формулы. Поскольку каждый контекстно-зависимый язык может быть принят линейным ограниченным автоматом , и такой автомат может быть смоделирован детерминированной машиной Тьюринга с временем работы в наихудшем случае не более чем для некоторой константы c [ нужна цитата ] , набор действительных формул в Арифметика Пресбургера не является контекстно-зависимой. Положительным моментом является то, что известно, что существует детерминированная машина Тьюринга, работающая со временем не более трехкратной экспоненты от n , которая определяет набор истинных формул арифметики Пресбургера. [4] Таким образом, это пример языка, который разрешим, но не зависит от контекста.
Рекурсивные языки закрываются при следующих операциях. То есть, если L и P — два рекурсивных языка, то следующие языки также рекурсивны:
Последнее свойство следует из того, что разность множеств можно выразить через пересечение и дополнение.
