Editing Decision problem (section)

==Definition==
A ''decision problem'' is the [[formal language]] of all inputs for which the output (the answer to the yes-no question on a given input) is ''YES''.<ref group="notes" name="def"/>

* These inputs can be natural numbers, but can also be values of some other kind, like binary [[string (computer science)|string]]s or strings over some other [[Alphabet (computer science)|alphabet]].

* For example, if every input can be encoded by the alphabet <math>\{0,1\}</math>, then a decision problem is a subset <math>L\subseteq\{0,1\}^*</math>.<ref group="notes" name="def"/>

* For another example, using an encoding such as [[Gödel numbering]], any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. Therefore, the decision procedure of a decision problem is to compute the [[Indicator function|characteristic function]] of a subset of the natural numbers.