En teoría de la computabilidad y 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 finita de tiempo. [1] De manera informal, significa que si la respuesta a una instancia del 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 respuesta verdadera es "no". Sin embargo, cuando la respuesta verdadera es "no", no se requiere que el procedimiento se detenga; puede entrar en un " bucle infinito " para algunos casos "no". A este procedimiento a veces se lo llama semialgoritmo , 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 lenguajes que son complementos de un lenguaje en RE . En cierto sentido, co-RE contiene lenguajes cuya pertenencia puede refutar en un tiempo finito, pero demostrar la pertenencia 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 "sí", una por una (esto es lo que significa "enumerable"). Cada miembro de RE es un conjunto enumerable recursivamente y, por lo tanto, un conjunto diofántico .
Para demostrar que esto es equivalente, observe que si hay una máquina que enumera todas las entradas aceptadas, otra máquina que acepta una cadena puede ejecutarse y aceptar si la cadena está enumerada. Por el contrario, si una máquina acepta cuando una entrada está en un lenguaje, otra máquina puede enumerar todas las cadenas en el lenguaje intercalando simulaciones de en cada entrada y generando cadenas que se aceptan (hay un orden de ejecución que eventualmente llegará a cada paso de ejecución porque hay una cantidad contable de 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 idiomas que no son ni RE ni co-RE se conoce como NRNC . Se trata del conjunto de idiomas para los que no se puede demostrar ni la pertenencia ni la no pertenencia en un tiempo finito, y que contiene todos los demás idiomas que no son ni RE ni co-RE . Es decir:
Estos problemas no sólo son indecidibles, sino que ni ellos ni sus complementos son recursivamente enumerables.
En enero de 2020, una preimpresión anunció una prueba de que RE era equivalente a la clase MIP* (la clase en la que un verificador clásico interactúa con múltiples probadores cuánticos todopoderosos que comparten entrelazamiento ); [4] una prueba revisada, pero aún no completamente revisada, se publicó en Communications of the ACM en noviembre de 2021. La prueba implica que el problema de incrustación de Connes y el problema de Tsirelson son falsos. [5]
RE-completo es el conjunto de problemas de decisión que son completos para RE . En cierto sentido, estos son los problemas recursivamente enumerables "más difíciles". Generalmente, no se impone ninguna restricción sobre las reducciones utilizadas, excepto que deben ser reducciones de muchos a uno .
Ejemplos de problemas RE-completar:
co-RE-completo es el conjunto de problemas de decisión que están completos para co-RE . En cierto sentido, son los complementos de los problemas recursivamente enumerables más difíciles.
Ejemplos de problemas co-RE-completos:
Un método de solución se denominará semialgoritmo para [un problema] P en [un dispositivo] M si la solución a P (si existe alguna) aparece después de la realización de un número finito de pasos. Un semialgoritmo se denominará algoritmo si , además, siempre que el problema no tenga solución, el método permite al dispositivo determinarla después de un número finito de pasos y paradas.
