RE (complexity)
From Wikipedia, the free encyclopedia
RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. (If the answer is 'no,' on the other hand, the machine might never halt.)
Equivalently, RE is the class of decision problems for which a Turing machine can list all the 'yes' instances, one by one (this is what 'enumerable' means).
For class of the 'no' answers, see Co-RE.
Each member of RE is a recursively enumerable set.
[edit] Relations to other classes
RE is known to be strictly greater than R, and strictly nonequal to Co-RE. We have that
[edit] External links
|
|||||
