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).