Recognition problem

An algorithmic problem in which, given a set $A$, it is required to construct an algorithm recognizing $A$ with respect to another set $B$ containing $A$ ($A\subseteq B$), that is, an algorithm $\mathfrak A$ which is applicable to any element of $B$, and such that $\mathfrak A(x)=1$ if $x\in A$ and $\mathfrak A(x)=0$ if $x\in B\setminus A$. 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 $A$) with respect to the set of all formulas in the theory (the set $B$).

The term "recognition problem" should be distinguished from the term "decidability problem", which is the question whether some mathematical problem or other (for example, an algorithmic problem) is solvable (cf. Decision problem).