En matemáticas , lógica e informática , un lenguaje formal (un conjunto de secuencias finitas de símbolos tomados de un alfabeto fijo ) se llama recursivo si es un subconjunto recursivo del conjunto de todas las secuencias finitas posibles sobre el alfabeto del lenguaje. De manera equivalente, un lenguaje formal es recursivo si existe una máquina de Turing que, cuando se le da una secuencia finita de símbolos como entrada, siempre la detiene y la acepta si pertenece al lenguaje y la detiene y rechaza en caso contrario. En informática teórica , estas máquinas de Turing que siempre se detienen se denominan máquinas o algoritmos de Turing totales (Sipser 1997). Los lenguajes recursivos también se llaman decidibles .
El concepto de decidibilidad puede extenderse a otros modelos de computación . Por ejemplo, se puede hablar de lenguajes decidibles en una máquina de Turing no determinista . Por lo tanto, siempre que sea posible una ambigüedad, el sinónimo utilizado para "lenguaje recursivo" es lenguaje decidible por Turing , en lugar de simplemente decidible .
La clase de todos los lenguajes recursivos suele denominarse R , aunque este nombre también se utiliza para la clase RP .
Este tipo de lenguaje no estaba definido en la jerarquía de Chomsky (Chomsky 1959). Todos los lenguajes recursivos también son recursivamente enumerables . Todos los lenguajes normales , libres de contexto y sensibles al contexto son recursivos.
Hay dos definiciones principales equivalentes para el concepto de lenguaje recursivo:
Según la segunda definición, se puede demostrar que cualquier problema de decisión es decidible exhibiendo un algoritmo que termine en todas las entradas. Un problema indecidible es un problema que no es decidible.
Como se señaló anteriormente, todo lenguaje sensible al contexto es recursivo. Así, un ejemplo sencillo de lenguaje recursivo es el conjunto L={abc, aabbcc, aaabbcccc, ...} ; más formalmente, el conjunto
es sensible al contexto y por lo tanto recursivo.
Los ejemplos de lenguajes decidibles que no son sensibles al contexto son más difíciles de describir. Para poner un ejemplo de este tipo, se requiere cierta familiaridad con la lógica matemática : la aritmética de Presburger es la teoría de primer orden de los números naturales con suma (pero sin multiplicación). Si bien el conjunto de fórmulas bien formadas en la aritmética de Presburger está libre de contexto, cada máquina determinista de Turing que acepta el conjunto de enunciados verdaderos en la aritmética de Presburger tiene un tiempo de ejecución en el peor de los casos de al menos , para alguna constante c > 0 (Fischer y Rabin 1974 ). Aquí, n denota la longitud de la fórmula dada. Dado que todo lenguaje sensible al contexto puede ser aceptado por un autómata lineal acotado , y dicho autómata puede ser simulado por una máquina de Turing determinista con un tiempo de ejecución en el peor de los casos como máximo para una constante c [ cita requerida ] , el conjunto de fórmulas válidas en La aritmética de Presburger no depende del contexto. En el lado positivo, se sabe que existe una máquina determinista de Turing que funciona en el tiempo a lo sumo triplemente exponencial en n y que decide el conjunto de fórmulas verdaderas en la aritmética de Presburger (Oppen 1978). Por lo tanto, este es un ejemplo de un lenguaje que es decidible pero no sensible al contexto.
Los lenguajes recursivos se cierran mediante las siguientes operaciones. Es decir, si L y P son dos lenguajes recursivos, entonces los siguientes lenguajes también son recursivos:
La última propiedad se deriva del hecho de que la diferencia de conjuntos se puede expresar en términos de intersección y complemento.
