R
- Instance of
- Subclass of
- Part of
Overview
All data
6 statements · 17% with external sources · numbers in brackets are citations
On other databases
1 identifiers linking RE across the web's reference databases
6 statements · 17% with external sources · numbers in brackets are citations
1 identifiers linking RE across the web's reference databases
From Wikipedia, the free encyclopedia · Read full article · Text CC BY-SA 4.0
In computability theory and computational complexity theory, RE 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 to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem.