R (complexity)

In computational complexity theory, R is the class of decision problems solvable by a Turing machine, which is the set of all recursive languages.

Equivalent formulations

R is equal to the set of all total computable functions.

Relationship with other classes

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.

gollark: They aren't stealing money from me because I don't have income.
gollark: That would be bad, so you don't.
gollark: Also, my website would stop working.
gollark: If the internet ceased to exist, the world economy would collapse utterly.
gollark: Still can't work. You use energy keeping your temperature at 37degC or so. You need an input of new chemical energy to keep that working.

References
  • Blum, Lenore, Mike Shub, and Steve Smale. "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines." Bulletin (New Series) of the American Mathematical Society 21.1 (1989): 1-46.

Complexity Zoo: Class R

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.