Editing Decision problem (section)

== Decidability ==

{{main|Undecidable problem|Decidability (logic)}}

* A decision problem is ''decidable'' or ''effectively solvable'' if the set of inputs for which the answer is ''YES'' is a [[recursive set]].<ref group="notes" name="rec-set"/>
* A decision problem is ''partially decidable'', ''semidecidable'', ''solvable'', or ''provable'' if the set of inputs for which the answer is ''YES'' is a [[recursively enumerable set]].

Problems that are not decidable are ''undecidable'', which means it is not possible to create an algorithm (efficient or not) that solves them. The [[halting problem]] is an important undecidable decision problem; for more examples, see [[list of undecidable problems]].