Difference between revisions of "Reduction (recursion theory)"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) (Created page with "In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. == Description == They are motiva...") |
Karl Jones (Talk | contribs) (→See also) |
||
| Line 17: | Line 17: | ||
* [[Decision problem]] | * [[Decision problem]] | ||
* [[Recursive set]] | * [[Recursive set]] | ||
| + | |||
| + | [[Category:Computation]] | ||
| + | [[Category:Computer science]] | ||
| + | [[Category:Mathematics]] | ||
| + | [[Category:Paradox]] | ||
| + | [[Category:Recursion]] | ||
== External links == | == External links == | ||
* [https://en.wikipedia.org/wiki/Reduction_(recursion_theory) Creating Reduction (recursion theory)] @ Wikipedia | * [https://en.wikipedia.org/wiki/Reduction_(recursion_theory) Creating Reduction (recursion theory)] @ Wikipedia | ||
Latest revision as of 15:51, 20 April 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
External links
- Creating Reduction (recursion theory) @ Wikipedia
