Definition 9.2.1: a decision problem (p,d) is decidable (or solvable) if there is “straightforward” encoding e(p) of the problem instances into sequences in some alphabet _ so that d: e(p) _ {yes,no} is a total Turing-computable function; otherwise (p,d) is undecidable (or unsolvable).
Since the outcomes are binary, a decision problem (p,d) can also be regarded as a language recognition problem L(p) = {w_e(p)| w=e(_) and d(_)=yes} ___*.
Previous slide | Next slide | Back to first slide | View graphic version |