|
In computability theory, a decision problem is undecidable if there is no algorithm
that can always give the correct answer.
If there is an algorithm that answers YES if and only if the correct answer is YES, but that may run forever when the correct
answer is NO, then the problem is partially
decidable. A problem can be both undecidable and partially decidable. One example of this is the halting problem, but Rice's theorem states that all non-trivial problems on the final results of computer programs are
undecidable.
If there is an algorithm that always answers correctly, both for YES and NO answers, then the problem is decidable, and is not undecidable.
A formal language is said to be undecidable if the decision
problem "is a given string in this language" is undecidable. (See further: Decidable language)
|