View source for Recognition problem

An [[Algorithmic problem|algorithmic problem]] in which, given a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801001.png" />, it is required to construct an [[Algorithm|algorithm]] recognizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801002.png" /> with respect to another set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801003.png" /> containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801004.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801005.png" />), that is, an algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801006.png" /> which is applicable to any element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801007.png" />, and such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801008.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r0801009.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r08010010.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r08010011.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r08010012.png" />) with respect to the set of all formulas in the theory (the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080100/r08010013.png" />).

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|Decision problem]]).