RE (complexity)

Computer/Terms 2008. 4. 7. 18:45

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.

Reference:
http://en.wikipedia.org/wiki/RE_%28complexity%29

Posted by 알 수 없는 사용자
,