FACTOID # 146: About one-quarter of all nations drive on the left-hand-side of the road. Most of them are former British colonies.
 
 Home   Encyclopedia   Statistics   Countries A-Z   Flags   Maps   Education   Forum   FAQ   About 
 
WHAT'S NEW
RECENT ARTICLES
More Recent Articles »
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


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.



 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments
Please enter the 5-letter protection code

Want to know more?
Search encyclopedia, statistics and forums:

 


Lesson Plans | Student Area | Student FAQ | Reviews | Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.