R

En la teoría de la complejidad computacional, R es la clase de problemas de decisión solubles por 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 computable si y solo si su grafo está en R. Relación con otras clases Dado que podemos decidir cualquier problema para el cual existe un reconocedor y también un co-reconocedor simplemente intercalándolos hasta obtener un resultado, la clase es igual a RE ∩ co-RE. Referencias Blum, Lenore, Mike Shub, and Steve Smale, (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines", Bulletin of the American Mathematical Society, New Series, 21 (1): 1-46.