|
High (computability)
In computability theory, a Turing degree [''X''] is high if it is computable in 0′, and the Turing jump [''X''′] is 0′′, which is the greatest possible degree in terms of Turing reducibility for the jump of a set which is computable in 0′. Similarly, a degree is ''high n'' if its n'th jump is the (n+1)'st jump of 0. Even more generally, a degree d is ''generalized high n'' if its n'th jump is the n'th jump of the join of d with 0′. See also * Low (computability) References Computability theory {{mathlogic-stub, date=February 2009 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computability 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. I ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turing Degree
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. Overview The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems. The Turing degree of a set is a measure of how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set. Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered, so that if the Turing degree of a set ''X'' is less than the Turing degree of a set ''Y'', then any (noncomputable) procedure that correctly decides whether numbers a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turing Jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for . The operator is called a ''jump operator'' because it increases the Turing degree of the problem . That is, the problem is not Turing-reducible to . Post's theorem establishes a relationship between the Turing jump operator and the arithmetical hierarchy of sets of natural numbers.. Informally, given a problem, the Turing jump returns the set of Turing machines that halt when given access to an oracle that solves that problem. Definition The Turing jump of ''X'' can be thought of as an oracle to the halting problem for oracle machines with an oracle for ''X''. Formally, given a set and a Gödel numbering of the -computable functions, the Turing jump of is defined as : X'= \. The th Turing jump is defined i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turing Reducibility
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving ''B''. The concept can be analogously applied to function problems. If a Turing reduction from A to B exists, then every algorithm for B can be used to produce an algorithm for A, by inserting the algorithm for B at each place where the oracle machine computing A queries the oracle for B. However, because the oracle machine may query the oracle a large number of times, the resulting algorithm may require more time asymptotically than either the algorithm for B or the oracle machine computing A. A Turing reduction in which the oracle machine runs in polynomial time is known as a Cook reduction. The first formal definition of relative computability, then called relative reducibility, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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, prop ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
