Difference between revisions of "Reduction (recursion theory)"

Revision as of 06:13, 24 February 2016

In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied.

Description

They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively convert a method for deciding membership in B into a method for deciding membership in A? If the answer to this question is affirmative then A is said to be reducible to B.

The study of reducibility notions is motivated by the study of decision problems.

For many notions of reducibility, if any Recursive set (or noncomputable set) is reducible to a set A then A must also be noncomputable.

This gives a powerful technique for proving that many sets are noncomputable.

See also

• Computability theory
• Decision problem
• Recursive set

External links

• Creating Reduction (recursion theory) @ Wikipedia