A decision problem is:
- Decidable if there is some algorithm that correctly generates a “YES-NO” answer for every possible input. Otherwise, it’s undecidable.
- Semi-decidable if there’s some algorithm that correctly generates “YES” answers, but does not terminate on some inputs for which the answer is “NO”.