Reduction (computability theory)

In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets ${\displaystyle A}$ and ${\displaystyle B}$ of natural numbers, is it possible to effectively convert a method for deciding membership in ${\displaystyle B}$ into a method for deciding membership in ${\displaystyle A}$? If the answer to this question is affirmative then ${\displaystyle A}$ is said to be reducible to ${\displaystyle B}$.

The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable set is reducible to a set ${\displaystyle A}$ then ${\displaystyle A}$ must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable.