| has gloss | eng: In computability theory and computational complexity theory, 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. Informally, it means that if the answer is yes, then there is some procedure which takes finite time to determine this. On the other hand, if the answer is no, 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). |