În matematică , logică și informatică , un limbaj recursiv este un tip de limbaj formal care este, de asemenea, numit recursiv , decisiv sau Turing .
Există mai multe definiții echivalente ale limbajului recursiv. Putem defini această noțiune direct, ca o generalizare a acelei seturi recursive (subseturi de numere întregi sau upluri de numere întregi), sau putem parcurge codificări în numere întregi, utilizând teoria calculabilității .
Pentru o definiție directă se pot folosi mașini Turing care folosesc alfabetul limbii. Un limbaj recursiv este apoi un limbaj formal recunoscut de o mașină Turing: mașina se oprește întotdeauna, acceptă o intrare dacă și numai dacă acesta este un cuvânt al limbii.
În mod echivalent, un limbaj este recursiv dacă și numai dacă acesta și complementul său (în setul tuturor cuvintelor din alfabetul limbii) sunt recursiv enumerabile . Limbile recursiv enumerabile sunt limbile generate de gramaticile generale .
Toate limbajele recursive sunt, de asemenea, recursiv enumerabile , dar inversul este fals. Celelalte limbi ale ierarhiei Chomsky , la fel ca limbile obișnuite, sunt recursive.
Din motive intrinseci noțiunii de calculabilitate (legată de indecidabilitatea problemei de oprire ), nu putem oferi o formă generală „simplă” (recursivă) de gramatici care generează toate limbajele recursive și numai acestea. Prin urmare, clasa limbajelor recursive nu apare ca atare în ierarhia Chomsky .
Clasa limbajelor recursive este închisă pentru un anumit număr de operații care sunt detaliate în continuare. Arătăm că dacă L și P sunt două limbi recursive, atunci și următoarele limbi sunt recursive: