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