Degree of undecidability

Turing degree

An equivalence relation $ \equiv _ {T} $ induced by the relation $ \leq _ {T} $ of Turing reducibility on subsets of the series of natural numbers ( $ A \equiv _ {T} B $ if $ A \leq _ {T} B $ and $ B \leq _ {T} A $). In other words, two sets have the same degree of undecidability if for each of them there is a decision procedure which is effective in the sense that it is possible to reduce the question of whether a number belongs this set to the question of whether it belongs to the other set (see also Algorithmic reducibility). Degrees of undecidability can also be defined as equivalence classes on the set of everywhere-defined functions (mapping the series of natural numbers into itself) induced by the relation $ \leq _ {R} $ of relative recursiveness. (A function $ f $ is recursive relative to a function $ g $ if $ f $ has a recursive definition in which among the initial functions, apart from the usual ones, there also occurs $ g $.) In this case the degree of undecidability of the function is also called its degree of non-computability; it is also called its Turing degree or $ T $- degree. The set of all degrees of undecidability turns out to be, for both approaches, an upper semi-lattice, and the resulting semi-lattices of the degrees of undecidability of sets and functions are isomorphic. It is in this sense that the definitions of equivalence are taken.

The structure of the semi-lattice of degrees of undecidability has been studied in much detail (see [1]–[3]). The elementary theory of this semi-lattice is unsolvable [6].

On the set of degrees of undecidability is defined a jump operation, assigning to a degree of undecidability $ a $ another one $ a ^ \prime $, which is maximal among the degrees of undecidability that are recursively enumerable relative to $ a $. (A set $ B $ is recursively enumerable relative to a set $ A $ if $ B $ is the projection of a set that is recursive relative to $ A $, and a degree of undecidability $ b $ is said to be recursively enumerable relative to another one $ a $ if $ b $ contains a set $ B $ that is recursively enumerable relative to some $ A \in a $.) The jump operation is monotone: $ a \leq b $ implies $ a ^ \prime \leq b ^ \prime $( but not vice versa). For every degree of undecidability $ a \geq 0 ^ \prime $ there is another one, $ b $, such that $ a = b ^ \prime $. The degrees of undecidability $ 0 ^ {(} n) $ are maximal and accessible in the classes $ \Sigma _ {n} $ and $ \Pi _ {n} $ of arithmetic sets. Of special interest are the recursively-enumerable degrees of undecidability (those of recursively-enumerable sets), which form a sub-semi-lattice in the semi-lattice of all degrees of undecidability. Maximal among the recursively-enumerable degrees of undecidability is $ 0 ^ \prime $( that of a complete set). The question whether there exist recursively-enumerable degrees of undecidability other than 0 and $ 0 ^ \prime $( the so-called Post problem) has an affirmative answer (see [4], [5]). To solve this problem the priority method was developed. The semi-lattice of recursively-enumerable degrees of unsolvability (in contrast to that of all degrees of unsolvability) is dense, and every countable partially ordered set can be imbedded in it. For many types of decidability problems arising in mathematics, consisting in a search for a decision algorithm for a certain set (such as the word (identity) problem in group theory, the decision problem for a finitely-axiomatizable elementary theory, etc.), it has been proved that there are undecidable problems of the type in question having an arbitrary recursively-enumerable degree of undecidability.

The degrees of undecidability of the most important types of recursively-enumerable sets have been investigated. (Thus, all creative sets (cf. Creative set) have degree of undecidability $ 0 ^ \prime $, simple sets can have any non-zero recursively-enumerable degree of undecidability, and any recursively-enumerable degree of undecidability $ a $ for which $ a ^ \prime = 0 ^ {\prime\prime} $ is maximal.)

The concept of a degree can also be introduced for types of algorithmic reducibility other than Turing's (in particular, $ 1 $-, $ m $-, $ tt $- degrees and others), and it has been investigated whether the degree of undecidability falls into these "finer" degrees. Some of these intermediate types of reducibility turn out to be connected with an estimate of the complexity of the amount of work and the specification of algorithms (see also Algorithmic information theory).

References

[1]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)
[2]	J. Shoenfield, "Degrees of unsolvability" , North-Holland (1971)
[3]	G.E. Sacks, "Degrees of unsolvability" , Princeton Univ. Press (1963)
[4]	A.A. Muchnik, "On the unsolvability of the reducibility problem in the theory of algorithms" Dokl. Akad. Nauk SSSR , 108 : 2 (1956) pp. 194–197 (In Russian)
[5]	R.M. Friedberg, "Two recursively enumerable sets of incomparible degrees of unsolvability (solution of Post's problem)" Proc. Nat. Acad. Sci. USA , 43 (1957) pp. 236–238
[6]	A.H. Lachlan, "Distributive intial segments of the degrees of unsolvability" Z. Math. Logik und Grundl. Math. , 14 (1968) pp. 457–472

Comments

For $ tt $- reducibility see Truth-table reducibility.