Your Online Encyclopedia

Online Encylopedia and Dictionary Research Site

Online Encyclopedia Search    Online Encyclopedia Browse

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 $\textbf{deg}(X)$. The minimal element in the partial order is $\textbf{deg}(\emptyset)$ 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