Turing_degree Turing_degree

Turing degree - Definition and Overview

In computability theory, the Turing degree of a subset <math>X<math> of the natural numbers, <math>\omega<math>, is the equivalence class of all subsets of <math>\omega<math> equivalent to <math>X<math> under Turing reducibility. Turing reducibility induces a partial order on the Turing degrees. The degree of a set <math>X<math> is denoted <math>\textbf{deg}(X)<math>. The minimal element in the partial order is <math>\textbf{deg}(\emptyset)<math> 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.

Example Usage of Turing

azizfarhat: why did i call Anil Asif?? why? what am i Turing into?
picklemouse5000: Weird way to go Jerry Fuchs, drummer for !!!, Juan Maclean, Maserati, Turing Machine, dies after fall in elevator shaft http://bit.ly/2wurfp
mircbot: kotauchi submits 363B of Python for Turing Machine, ranking #2 (3829pts).
Copyright 2009 WordIQ.com - Privacy Policy  :: Terms of Use  :: Contact Us  :: About Us
This article is licensed under the GNU Free Documentation License. It uses material from the this Wikipedia article.