Turing degree
In computability theory and mathematical logic of the Turing degrees measures (also degree of insolubility ) of a set of natural numbers the algorithmic unsolvability of the crowd. The concept of the Turing degree is fundamental in computability theory where sets of natural numbers are often viewed as decision problems; the Turing degree of a quantity indicates how difficult is the decision problem of the crowd.
Two sets are Turing equivalent if they have the same degree of unsolvability; each Turing degree is a lot Turing equivalent amounts, so that two sets if and only lie in different Turing degrees, if they are not Turing - equivalent. In addition, the Turing degrees in the following sense are partially ordered. If the Turing degree of a set X is less than the Turing degree of a set Y is, then each ( unpredictable ) procedure, which decides correctly whether or not numbers are in Y, are predictable converted into a procedure, which decides correctly whether numbers in X lie. In this sense, the Turing degree of a set with the level of algorithmic unsolvability corresponds.
The Turing degrees were introduced in 1944 by Emil Leon Post and many fundamental results have been proved in 1954 by Stephen Cole Kleene and Post. The Turing degrees are still a matter of intense research. Many proofs in this area use a proof technique, which is known as a priority method.
- 6.1 launches
- 6.2 Special works
- 6.3 Research Papers
Turing equivalence
In the following, the word set refers to sets of natural numbers. A set X is called Turing - reducible to a set Y if there is an oracle Turing machine that decides with the help of an oracle for Y if X lie in numbers. The notation X ≤ TY stands for: X to Y is Turing reducible.
Two sets X and Y are called Turing - equivalent if they are Turing reducible to each other. The notation X ≡ TY stands for: X and Y are Turing equivalent. The relation ≡ T is an equivalence relation, that is, for all sets X, Y and Z where:
- X ≡ T X
- X ≡ T Y implies Y ≡ T X
- If X ≡ T Y and Y ≡ T Z, then X ≡ T Z.
Turing degrees
A Turing degree is an equivalence class of the relation ≡ T. The notation [ x ] denotes the equivalence class that includes the set X. The class of all Turing degrees is denoted by.
The Turing degrees have a partial order ≤. It is defined such that [X ] ≤ [ Y] if and only if X ≤ T Y. There is a Turing degree contains exactly the decidable sets, and this degree is smaller than all the others. He is 0 ( zero ) because it is the smallest element of the partially ordered set. Turing degrees are usually designated by bold type, to distinguish them from quantities. As variables for Turing degrees are bold lower case letters a, b , etc.
For all sets X and Y, X join Y, written X ⊕ Y, the union of the sets { 2n: n ∈ X} and { 2m 1: m ∈ Y}. The Turing degree of X ⊕ Y is the supremum of the degrees [X ] and [ Y]. This is an upper semilattice. The supremum of the degrees of a and b is denoted by a ∪ b. It is known that no association is because there are a couple of degrees without infimum.
For any set X is X 'is the set of indices of oracle machines that keep their own index as input when they use X as an oracle. The set X ' is called Turing jump of X. The Turing jump of a degree [X ] is the degree of [X ']; this is well defined, since X ' ≡ TY ' follows from X ≡ TY. An important example is '0 ', the level of the holding problem.
Basic features of the Turing degrees
- Every Turing degree is countable infinite, that is, it contains the exact amounts.
- There are different Turing degrees.
- For every degree a strict inequality a < a '.
- For every degree a is the amount of degrees is at most countable under a. The amount of degrees above a has cardinality.
Structure of the Turing degrees
The structure of the Turing degrees has been studied extensively. The following list shows just a few of the many known results. In general it can be concluded from the known results that the structure of the Turing degrees is very complicated.
Order properties
- There are minimum levels. A level is a minimum, if a is not 0 and there is no degree of between 0 and a. Hence, the order of the degrees of non-sealing.
- For each class a is not 0, there is a degree b, which is not comparable with a.
- There are not mutually comparable Turing degrees.
- There are a couple of degrees without infimum. This is not a lattice.
- Any countable partial order can be embedded into the Turing degrees.
- No infinite, strictly increasing sequence of degrees has a supremum.
Properties of the jump operator
- For each level, there is a degree of a between a and a '. There is even a countably infinite sequence of pairwise non-comparable degrees between a and a '.
- A degree a has the form b ' for some b if and only if 0' ≤ a valid.
- For each coefficient a, there is a level B, so that a
- There is an infinite sequence ai of degrees, so that a 'i 1 ≤ ai for all i
Logical properties
- Simpson ( 1977) showed that the theory of the first-order logic in the language < ≤, => or < ≤, ', => many-one equivalent to the theory of natural numbers in the predicate calculus second stage.
- Shore and Slaman (1999) showed that the jump operator can be defined in the structure of degrees in first-order logic with the language < ≤, =>.
Structure of the recursively enumerable Turing degrees
A degree is called recursively enumerable if it contains a recursively enumerable set. Every recursively enumerable degree is less than or equal to 0 ', but not every degree below 0 ' is recursively enumerable.
- ( Set of Friedberg and Muchnik, 1956) There are recursive enumerable degrees 0-0 '.
- (GE Sacks, 1964) The recursively enumerable degrees are dense, that is, there is always a third recursively enumerable degrees between two recursively enumerable degrees.
- (AH Lachlan, 1966a and CEM Yates, 1966 ) There are two recursively enumerable degrees who have no infimum in the recursively enumerable degrees.
- (AH Lachlan, 1966a and CEM Yates, 1966) There is a pair of recursively enumerable degrees equal to 0, the infimum is 0.
- (SK Thomason, 1971) Every finite distributive lattice can be embedded into the recursively enumerable degrees. It is even possible that a countable Boolean algebra without atoms embed so that Suprema and infima are preserved.
- (AH Lachlan and RI Soare, 1980) Not all finite groups can be embedded in the recursively enumerable degrees, so Suprema and infima are preserved. In particular, the following can not be embedded Association:
- (AH Lachlan, 1966b ) There is no pair of recursively enumerable degrees, the infimum is 0 and whose supremum 0'ist,
- (LA Harrington and TA Slaman, see Nies, Shore, and Slaman (1998)) The theory of recursively enumerable degrees in the language <0, ≤, => in first-order logic is many-one equivalent to the theory of arithmetic in logic first stage.