Recognition problem
An algorithmic problem in which, given a set , it is required to construct an algorithm recognizing
with respect to another set
containing
(
), that is, an algorithm
which is applicable to any element of
, and such that
if
and
if
. An important class of algorithmic problems is constituted by the recognition problems for formal theories, that is, the recognition problem for the set of all provable formulas in a theory (the set
) with respect to the set of all formulas in the theory (the set
).
The term "recognition problem" should be distinguished from the term "decidability problemdecidability problem" , which is the question whether some mathematical problem or other (for example, an algorithmic problem) is solvable (cf. Decision problem).
Recognition problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Recognition_problem&oldid=33203