View source for Recognition problem

{{TEX|done}}
An [[Algorithmic problem|algorithmic problem]] in which, given a set $A$, it is required to construct an [[Algorithm|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|Decision problem]]).