Online Encyclopedia Search Tool

Your Online Encyclopedia


Online Encylopedia and Dictionary Research Site

Online Encyclopedia Free Search Online Encyclopedia Search    Online Encyclopedia Browse    welcome to our free dictionary for your research of every kind

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 \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