チューリング次数
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 are in "Y" can be effectively converted to a procedure that correctly decides whether numbers are in "X". It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability.