This article includes a list of general
references, but it lacks sufficient corresponding
inline citations. (September 2018) |
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem X a successively harder decision problem X′ with the property that X′ is not decidable by an oracle machine with an oracle for X.
The operator is called a jump operator because it increases the Turing degree of the problem X. That is, the problem X′ is not Turing-reducible to X. Post's theorem establishes a relationship between the Turing jump operator and the arithmetical hierarchy of sets of natural numbers. [1] 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.
The Turing jump of X can be thought of as an oracle to the halting problem for oracle machines with an oracle for X. [1]
Formally, given a set X and a Gödel numbering φiX of the X-computable functions, the Turing jump X′ of X is defined as
The nth Turing jump X(n) is defined inductively by
The ω jump X(ω) of X is the effective join of the sequence of sets X(n) for n ∈ N:
where pi denotes the ith prime.
The notation 0′ or ∅′ is often used for the Turing jump of the empty set. It is read zero-jump or sometimes zero-prime.
Similarly, 0(n) is the nth jump of the empty set. For finite n, these sets are closely related to the arithmetic hierarchy, [2] and is in particular connected to Post's theorem.
The jump can be iterated into transfinite ordinals: there are jump operators for sets of natural numbers when is an ordinal that has a code in Kleene's (regardless of code, the resulting jumps are the same by a theorem of Spector), [2] in particular the sets 0(α) for α < ω1CK, where ω1CK is the Church–Kleene ordinal, are closely related to the hyperarithmetic hierarchy. [1] Beyond ω1CK, the process can be continued through the countable ordinals of the constructible universe, using Jensen's work on fine structure theory of Gödel's L. [3] [2] The concept has also been generalized to extend to uncountable regular cardinals. [4]
Many properties of the Turing jump operator are discussed in the article on Turing degrees.
This article includes a list of general
references, but it lacks sufficient corresponding
inline citations. (September 2018) |
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem X a successively harder decision problem X′ with the property that X′ is not decidable by an oracle machine with an oracle for X.
The operator is called a jump operator because it increases the Turing degree of the problem X. That is, the problem X′ is not Turing-reducible to X. Post's theorem establishes a relationship between the Turing jump operator and the arithmetical hierarchy of sets of natural numbers. [1] 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.
The Turing jump of X can be thought of as an oracle to the halting problem for oracle machines with an oracle for X. [1]
Formally, given a set X and a Gödel numbering φiX of the X-computable functions, the Turing jump X′ of X is defined as
The nth Turing jump X(n) is defined inductively by
The ω jump X(ω) of X is the effective join of the sequence of sets X(n) for n ∈ N:
where pi denotes the ith prime.
The notation 0′ or ∅′ is often used for the Turing jump of the empty set. It is read zero-jump or sometimes zero-prime.
Similarly, 0(n) is the nth jump of the empty set. For finite n, these sets are closely related to the arithmetic hierarchy, [2] and is in particular connected to Post's theorem.
The jump can be iterated into transfinite ordinals: there are jump operators for sets of natural numbers when is an ordinal that has a code in Kleene's (regardless of code, the resulting jumps are the same by a theorem of Spector), [2] in particular the sets 0(α) for α < ω1CK, where ω1CK is the Church–Kleene ordinal, are closely related to the hyperarithmetic hierarchy. [1] Beyond ω1CK, the process can be continued through the countable ordinals of the constructible universe, using Jensen's work on fine structure theory of Gödel's L. [3] [2] The concept has also been generalized to extend to uncountable regular cardinals. [4]
Many properties of the Turing jump operator are discussed in the article on Turing degrees.