RE (complejidad)
En la teoría de la computabilidad y la teoría de la complejidad computacional , RE ( recursivamente enumerable ) es la clase de problemas de decisión para los cuales una máquina de Turing puede verificar una respuesta 'sí' en una cantidad de tiempo finita. [1] Informalmente, significa que si la respuesta a una instancia de problema es 'sí', entonces hay algún procedimiento que toma un tiempo finito para determinar esto, y este procedimiento nunca informa falsamente 'sí' cuando la verdadera respuesta es 'no' . Sin embargo, cuando la verdadera respuesta es 'no', no se requiere que el procedimiento se detenga; puede entrar en un " bucle infinito " para algunos casos de 'no'.Este procedimiento a veces se denominasemi-algoritmo , para distinguirlo de un algoritmo , definido como una solución completa a un problema de decisión. [2]
De manera similar, co-RE es el conjunto de todos los idiomas que son complementos de un idioma en RE . En cierto sentido, co-RE contiene idiomas en los que se puede refutar la membresía en un período de tiempo finito, pero probar la membresía puede llevar una eternidad.
De manera equivalente, RE es la clase de problemas de decisión para los cuales una máquina de Turing puede enumerar todas las instancias de 'sí', una por una (esto es lo que significa 'enumerable'). Cada miembro de RE es un conjunto recursivamente enumerable y, por lo tanto, un conjunto diofántico .
Para mostrar que esto es equivalente, tenga en cuenta que si hay una máquina que enumera todas las entradas aceptadas, otra máquina que toma una cadena puede ejecutarse y aceptar si se enumera la cadena. Por el contrario, si una máquina acepta cuando una entrada está en un idioma, otra máquina puede enumerar todas las cadenas en el idioma intercalando simulaciones en cada entrada y generando cadenas que se aceptan (hay un orden de ejecución que eventualmente llegará a cada ejecución). porque hay numerablemente muchos pares ordenados de entradas y pasos).
El conjunto de lenguajes recursivos ( R ) es un subconjunto tanto de RE como de co-RE . [3] De hecho, es la intersección de esas dos clases, porque podemos decidir cualquier problema para el que exista un reconocedor y también un co-reconocedor simplemente intercalándolos hasta obtener un resultado. Por lo tanto:
Por el contrario, el conjunto de lenguas que no son ni RE ni co-RE se conoce como NRNC . Estos son el conjunto de idiomas para los que no se puede probar ni la membresía ni la no membresía en un período de tiempo finito, y contienen todos los demás idiomas que no están en RE ni en co-RE . Es decir: