En la teoría de la complejidad computacional , R es la clase de problemas de decisión que puede resolver una máquina de Turing , que es el conjunto de todos los lenguajes recursivos (también llamados lenguajes decidibles).
Formulaciones equivalentes
R es equivalente al conjunto de todas las funciones computables totales en el sentido de que:
- un problema de decisión está en R si y solo si su función indicadora es computable,
- una función total es calculable si y solo si su gráfica está en R.
Relación con otras clases
Dado que podemos decidir cualquier problema para el que exista un reconocedor y también un co-reconocedor simplemente intercalando hasta obtener un resultado, la clase es igual a RE ∩ co-RE .
Referencias
- Blum, Lenore , Mike Shub y Steve Smale , (1989), "Sobre una teoría de la computación y la complejidad sobre los números reales: NP-completitud, funciones recursivas y máquinas universales", Boletín de la Sociedad Matemática Estadounidense , Nueva Serie, 21 (1): 1-46.