Język rekurencyjny

Ten artykuł dotyczy klasy języków formalnych, które są badane w matematyce i informatyce teoretycznej. W przypadku języków komputerowych, które pozwalają funkcji wywoływać się rekurencyjnie, zobacz Rekursja (informatyka) .

W matematyce , logice i informatyce język formalny ( zbiór skończonych sekwencji symboli wziętych z ustalonego alfabetu ) nazywany jest rekurencyjnym , jeśli jest rekurencyjnym podzbiorem zbioru wszystkich możliwych ciągów skończonych w alfabecie języka. Odpowiednio, język formalny jest rekurencyjny, jeśli istnieje całkowita maszyna Turinga ( maszyna Turinga który zatrzymuje się dla każdego podanego wejścia), który, gdy na wejściu otrzyma skończoną sekwencję symboli, akceptuje go, jeśli należy do języka, i odrzuca go w przeciwnym razie. Języki rekurencyjne nazywane są także rozstrzygalnymi .

Pojęcie rozstrzygalności można rozszerzyć na inne modele obliczeń . Można na przykład mówić o językach rozstrzygalnych na niedeterministycznej maszynie Turinga . Dlatego też, gdy tylko możliwa jest niejednoznaczność, synonimem używanym do określenia „języka rekurencyjnego” jest język rozstrzygalny metodą Turinga , a nie po prostu rozstrzygalny .

Klasa wszystkich języków rekurencyjnych jest często nazywana R , chociaż tej nazwy używa się również w odniesieniu do klasy RP .

Ten typ języka nie został zdefiniowany w hierarchii Chomsky'ego ( Chomsky 1959 ). Wszystkie języki rekurencyjne są również rekurencyjnie przeliczalne . Wszystkie języki regularne , bezkontekstowe i wrażliwe na kontekst są rekurencyjne.

Definicje

Istnieją dwie równoważne główne definicje pojęcia języka rekurencyjnego:

1. Rekurencyjny język formalny to rekurencyjny podzbiór w zbiorze wszystkich możliwych słów w alfabecie tego języka .
2. Język rekurencyjny to język formalny, dla którego istnieje maszyna Turinga , która po zaprezentowaniu dowolnego skończonego ciągu wejściowego zatrzymuje się i akceptuje, jeśli ciąg znaków znajduje się w języku, a w przeciwnym razie zatrzymuje się i odrzuca. Maszyna Turinga zawsze się zatrzymuje: nazywa się ją decydentem i mówi się, że decyduje o języku rekurencyjnym.

Zgodnie z drugą definicją każdy problem decyzyjny można wykazać jako rozstrzygalny, przedstawiając dla niego algorytm , który kończy się na wszystkich wejściach. Problem nierozstrzygalny to problem, którego nie da się rozwiązać.

Przykłady

Jak zauważono powyżej, każdy język kontekstowy jest rekurencyjny. Zatem prostym przykładem języka rekurencyjnego jest zbiór L={abc, aabbcc, aaabbbccc, ...} ; bardziej formalnie, zestaw

${\ Displaystyle L = \ {\, w \ in \ {a, b, c \} ^ {*}\mid w=a^{n}b^{n}c^{n}{\mbox{ dla niektórych }}n\geq 1\,\}}$

jest kontekstowy i dlatego rekurencyjny.

Trudniej jest opisać przykłady języków rozstrzygalnych, które nie są wrażliwe na kontekst. W przypadku jednego z takich przykładów wymagana jest pewna znajomość logiki matematycznej : arytmetyka Presburgera jest teorią pierwszego rzędu liczb naturalnych z dodawaniem (ale bez mnożenia). Chociaż zbiór dobrze sformułowanych formuł w arytmetyce Presburgera jest bezkontekstowy, każda deterministyczna maszyna Turinga akceptująca zbiór prawdziwych instrukcji w arytmetyce Presburgera ma czas wykonania w najgorszym przypadku wynoszący co najmniej ${\ displaystyle 2 ^ {2 ^ {cn}}}$ , dla pewnej stałej c > 0 ( Fischer i Rabin 1974 ). Tutaj n oznacza długość danego wzoru. Ponieważ każdy język kontekstowy może zostać zaakceptowany przez automat ograniczony liniowo , a $taki automat może być symulowany przez deterministyczną maszynę Turinga z czasem działania$ najgorszym przypadku pewnej stałej c , zbiór prawidłowych formuł w arytmetyce Presburgera nie jest zależny od kontekstu. Z drugiej strony wiadomo, że istnieje deterministyczna maszyna Turinga działająca w czasie co najwyżej potrójnie wykładniczym w n , która decyduje o zbiorze prawdziwych formuł w arytmetyce Presburgera ( Oppen 1978 ). Jest to zatem przykład języka, który jest rozstrzygalny, ale nie jest zależny od kontekstu.

Właściwości zamknięcia

Języki rekurencyjne są zamykane w ramach następujących operacji. Oznacza to, że jeśli L i P są dwoma językami rekurencyjnymi, to następujące języki również są rekurencyjne:

• Gwiazda Kleene'a L $\ displaystyle L ^ {*}}$
• Obraz φ(L) pod e-wolnym homomorfizmem φ
• Połączenie ${\ displaystyle L \ circ P}$
• Związek ${\ displaystyle L \ puchar P}$
• Skrzyżowanie ${\ displaystyle L \ cap P}$
• Dopełnienie ${\ displaystyle L}$
• Ustawiona różnica ${\ displaystyle LP}$

Ostatnia właściwość wynika z faktu, że różnicę zadaną można wyrazić w kategoriach przecięcia i dopełnienia.

Zobacz też

• Język rekurencyjnie przeliczalny
• Zestaw obliczeniowy
• Rekurencja

•   Michaela Sipsera (1997). „Rozstrzygalność” . Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. s. 151–170 . ISBN 978-0-534-94728-6 .
• Chomsky, Noam (1959). „O niektórych formalnych właściwościach gramatyk” . Informacja i kontrola . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
• Fischer, Michael J .; Rabin, Michael O. (1974). „Nadwykładnicza złożoność arytmetyki Presburgera” . Materiały z sympozjum SIAM-AMS w matematyce stosowanej . 7 : 27–41.
• Oppen, Derek C. (1978). „Górna granica 2 ^{2 2 pn} złożoności arytmetyki Presburgera” . J. Oblicz. System. Nauka . 16 (3): 323–332. doi : 10.1016/0022-0000(78)90021-1 .