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 respuesta afirmativa puede ser verificada por una máquina de Turing en una cantidad de tiempo finita. [1] De manera informal, significa que si la respuesta a una instancia de problema es 'sí', entonces existe 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 verdadera respuesta es "no", no es necesario 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 cuya membresía se puede refutar en un período de tiempo finito, pero demostrar la membresía puede llevar una eternidad.
Definición equivalente
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 enumerable recursivamente y, por lo tanto, un conjunto diofantino .
Para demostrar 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 ejecutar y aceptar si la cadena está enumerada. 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 de en todas las cadenas de entrada y salida que se aceptan (hay un orden de ejecución que eventualmente llegará a cada paso de ejecución porque hay muchos pares ordenados de entradas y pasos).
Relaciones con otras clases
El conjunto de lenguajes recursivos ( R ) es un subconjunto de RE y 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 intercalando hasta que se obtenga un resultado. Por lo tanto:
- .
Por el contrario, el conjunto de idiomas que no son 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:
- .
Estos problemas no sólo son indecidibles, sino que ni ellos ni su complemento son enumerables de forma recursiva.
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 el entrelazamiento). [4]
Volver a completar
RE-complete es el conjunto de problemas de decisión que están completos para RE . En cierto sentido, estos son los problemas enumerables recursivamente más "difíciles". Por lo general, no se imponen restricciones a las reducciones utilizadas, excepto que deben ser reducciones de muchos uno .
Ejemplos de problemas RE-complete:
- Problema de detención : si un programa con una entrada finita termina de ejecutarse o se ejecutará para siempre.
- Según el teorema de Rice , decidir la pertenencia a cualquier subconjunto no trivial del conjunto de funciones recursivas es RE- difícil. Estará completo siempre que el conjunto sea enumerable de forma recursiva.
- John Myhill ( 1955 ) [5] demostró que todos los conjuntos creativos son RE- completos.
- El problema verbal uniforme para grupos o semigrupos . (De hecho, el problema verbal para algunos grupos individuales es RE -completar).
- Decidir la pertenencia a una gramática formal general sin restricciones . (Nuevamente, ciertas gramáticas individuales tienen problemas de membresía RE -completada).
- El problema de validez de la lógica de primer orden .
- Problema de correspondencia posterior : Dada una lista de pares de cadenas, determine si hay una selección de estos pares (que permite repeticiones) de modo que la concatenación de los primeros elementos (de los pares) sea igual a la concatenación de los segundos elementos.
- Determinar si una ecuación diofántica tiene soluciones enteras.
volver a completar
co-RE-complete es el conjunto de problemas de decisión que están completos para co-RE . En cierto sentido, estos son los complementos de los problemas enumerables recursivamente más difíciles.
Ejemplos de problemas de co-RE-completar:
- El problema del dominó para las fichas de Wang .
- El problema de satisfacibilidad para la lógica de primer orden .
Ver también
Referencias
- ^ Complejidad Zoo : Clase RE
- ^ Korfhage, Robert R. (1966). Lógica y algoritmos, con aplicaciones a la informática y las ciencias de la información . Wiley. pag. 89 .
Un método de solución se denominará semialgoritmo para [un problema] P en [un dispositivo] M si la solución de P (si existe) aparece después de realizar un número finito de pasos. Un semi-algoritmo se denominará algoritmo si, además, siempre que el problema no tiene solución, el método permite al dispositivo determinarlo después de un número finito de pasos y paradas.
- ^ Complejidad Zoo : Clase co-RE
- ^ Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2020). "MIP * = RE". arXiv : 2001.04383 [ quant-ph ].
- ^ Myhill, John (1955), "Conjuntos creativos", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 (2): 97–108, doi : 10.1002 / malq.19550010205 , MR 0071379 CS1 maint: parámetro desalentado ( enlace ).