In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages (also called decidable languages).
Equivalent formulations
editR is equivalent to the set of all total computable functions in the sense that:
- a decision problem is in R if and only if its indicator function is computable,
- a total function is computable if and only if its graph is in R.
Relationship with other classes
editSince we can decide any problem for which there exists a recogniser and also a co-recogniser by simply interleaving them until one obtains a result, the class is equal to RE ∩ co-RE.
References
edit- 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.
External links
edit