Online Encyclopedia
Turing degree
In computability theory, the Turing degree of a subset X of the natural numbers, ω, is the equivalence class of all subsets of ω equivalent to X under Turing reducibility. Turing reducibility induces a partial order on the Turing degrees. The degree of a set X is denoted . The minimal element in the partial order is and contains all recursive sets (computable sets).
A recursively enumerable Turing degree (computably enumerable Turing degree) is one containing a recursively enumerable set (computably enumerable set). The recursively enumerable Turing degrees under the partial order induced by Turing reducibility form an upper semi-lattice and are an object that has been much studied by the logic community.
Last updated: 02-27-2005 19:14:39