R (complejidad)

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).

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 computable si y solo si su gráfica está en R.

Puesto que podemos decidir cualquier problema para el que exista un reconocedor y también un co-reconocedor simplemente intercalándolos hasta obtener un resultado, la clase es igual a RE ∩ co-RE .

• 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 Americana , Nueva Serie, 21 (1): 1-46.

Zoológico de la complejidad : Clase R