Lenguaje recursivo

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 denomina 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 se detiene y la acepta si pertenece al lenguaje y se detiene y la rechaza en caso contrario. En informática teórica , estas máquinas de Turing que siempre se detienen se denominan máquinas de Turing totales o algoritmos . ^[1] Los lenguajes recursivos también se denominan 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 según Turing , en lugar de simplemente decidible .

La clase de todos los lenguajes recursivos a menudo se denomina R , aunque este nombre también se utiliza para la clase RP .

Este tipo de lenguaje no fue definido en la jerarquía de Chomsky . ^[2] Todos los lenguajes recursivos son también recursivamente enumerables . Todos los lenguajes regulares , independientes del contexto y sensibles al contexto son recursivos.

Existen dos definiciones principales equivalentes para el concepto de lenguaje recursivo:

1. Un lenguaje formal recursivo es un subconjunto recursivo del conjunto de todas las palabras posibles sobre el alfabeto del lenguaje .
2. Un lenguaje recursivo es un lenguaje formal para el cual existe una máquina de Turing que, cuando se le presenta una cadena de entrada finita , se detiene y acepta si la cadena está en el lenguaje, y se detiene y rechaza en caso contrario. La máquina de Turing siempre se detiene: se la conoce como decisora ​​y se dice que decide el lenguaje recursivo.

Según la segunda definición, se puede demostrar que cualquier problema de decisión es decidible si se presenta un algoritmo que finalice 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. Por lo tanto, un ejemplo simple de lenguaje recursivo es el conjunto L={abc, aabbcc, aaabbccc, ...} ; más formalmente, el conjunto

${\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ para algún }}n\geq 1\,\}}$

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 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 adición (pero sin multiplicación). Si bien el conjunto de fórmulas bien formadas en la aritmética de Presburger es libre de contexto, cada máquina de Turing determinista que acepta el conjunto de declaraciones verdaderas 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. ^[3] Aquí, n denota la longitud de la fórmula dada. Dado que cada 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 alguna constante c ^{[ cita requerida ]} , el conjunto de fórmulas válidas en la aritmética de Presburger no es sensible al contexto. En el lado positivo, se sabe que hay una máquina de Turing determinista que funciona en un tiempo como máximo triplemente exponencial en n que decide el conjunto de fórmulas verdaderas en la aritmética de Presburger. ^[4] Por lo tanto, este es un ejemplo de un lenguaje que es decidible pero no sensible al contexto.${\displaystyle 2^{2^{cn}}}$$Estilo de visualización c^{n}}$

Los lenguajes recursivos se cierran en virtud de las siguientes operaciones. Es decir, si L y P son dos lenguajes recursivos, entonces los siguientes lenguajes también son recursivos:

• La estrella de Kleene $Estilo de visualización L*$
• La imagen φ(L) bajo un homomorfismo e-libre φ
• La concatenación${\estilo de visualización L\circ P}$
• La unión${\displaystyle L\cup P}$
• La intersección${\displaystyle L\cap P}$
• El complemento de${\estilo de visualización L}$
• La diferencia de conjuntos${\estilo de visualización LP}$

La última propiedad se desprende del hecho de que la diferencia de conjuntos puede expresarse en términos de intersección y complemento.

• Lenguaje recursivamente enumerable
• Conjunto computable
• Recursión

• Chomsky, Noam (1959). "Sobre ciertas propiedades formales de las gramáticas". Información y Control . 2 (2): 137–167. doi :10.1016/S0019-9958(59)90362-6.
• Fischer, Michael J. ; Rabin, Michael O. (1974). "Complejidad superexponencial de la aritmética de Presburger". Actas del Simposio SIAM-AMS sobre Matemáticas Aplicadas . 7 : 27–41.
• Oppen, Derek C. (1978). "Un límite superior de 222pn en la complejidad de la aritmética de Presburger". J. Comput. Syst. Sci . 16 (3): 323–332. doi : 10.1016/0022-0000(78)90021-1 .
• Sipser, Michael (1997). "Decidibilidad" . Introducción a la teoría de la computación . PWS Publishing. pp. 151–170. ISBN 978-0-534-94728-6.