# 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