Content deleted Content added
No edit summary |
added Category:Computability theory using HotCat |
||
(25 intermediate revisions by 23 users not shown) | |||
Line 1:
==Equivalent formulations==
Since we can decide any problem for which there exists a recogniser and also a co-recogniser, the class is equal to <math>RE \cap coRE</math>.▼
R is equivalent to the set of all total [[computable function]]s 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 of a function|graph]] is in R.
==Relationship with other classes==
▲Since we can decide any problem for which there exists a [[recognizer|recogniser]] and also a co-recogniser by simply interleaving them until one obtains a result, the class is equal to
==References==
*[[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==
{{CZoo|Class R|R#r}}
{{ComplexityClasses}}▼
[[Category:Complexity classes]]
[[Category:Computability theory]]
▲{{ComplexityClasses}}
{{comp-sci-theory-stub}}
|