|
Low (computability)
In computability theory, a Turing degree 'X''is low if the Turing jump 'X''′is 0′. A set is low if it has low degree. Since every set is computable from its jump, any low set is computable in 0′, but the jump of sets computable in 0′ can bound any degree r.e. in 0′ (Schoenfield Jump Inversion). ''X'' being low says that its jump ''X''′ has the least possible degree in terms of Turing reducibility for the jump of a set. There are various related properties to low degrees: * A degree is ''lown'' if its n'th jump is the n'th jump of 0.C. J. Ash, J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), p. 22 * A set ''X'' is ''generalized low'' if it satisfies ''X''′ ≡T ''X'' + 0′, that is: if its jump has the lowest degree possible. * A degree d is ''generalized low n'' if its n'th jump is the (n-1)'st jump of the join of d with 0′. More generally, pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Recursion Theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include: * What does it mean for a function on the natural numbers to be computable? * How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |