En matemáticas , lógica e informática , un lenguaje recursivo es un tipo de lenguaje formal que también se denomina recursivo , decidible o decidible de Turing .
Hay varias definiciones equivalentes de lenguaje recursivo. Podemos definir esta noción directamente, como una generalización de la de conjunto recursivo (subconjuntos de enteros o aumentos de enteros), o pasar por codificaciones en enteros, utilizando la teoría de la computabilidad .
Para una definición directa, se pueden utilizar máquinas de Turing que utilizan el alfabeto del lenguaje. Un lenguaje recursivo es entonces un lenguaje formal reconocido por una máquina de Turing: la máquina siempre se detiene, acepta una entrada si y solo si se trata de una palabra del idioma.
De manera equivalente, una lengua es recursiva si y solo si ella y su complemento (en el conjunto de todas las palabras del alfabeto de la lengua) son recursivamente enumerables . Los lenguajes recursivamente enumerables son los lenguajes generados por gramáticas generales .
Todos los lenguajes recursivos también se pueden enumerar de forma recursiva , pero lo contrario es falso. Los otros lenguajes de la jerarquía de Chomsky , como los lenguajes regulares, son recursivos.
Por razones intrínsecas a la noción de computabilidad (ligadas a la indecidibilidad del problema de parada ), no podemos dar una forma general “simple” (recursiva) de gramáticas que generen todos los lenguajes recursivos y solo estos. La clase de lenguajes recursivos, por tanto, no aparece como tal en la jerarquía de Chomsky .
La clase de lenguajes recursivos está cerrada para un cierto número de operaciones que se detallan a continuación. Mostramos que si L y P son dos lenguajes recursivos, entonces los siguientes lenguajes también son recursivos: