From Wikipedia, the free encyclopedia
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
[edit]R 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
[edit]Since 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]Considered feasible | |
---|---|
Suspected infeasible | |
Considered infeasible | |
Class hierarchies | |
Families of classes | |
P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |
Hidden category:
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url
url