チューリング次数
更に、チューリング次数は半順序を成すので、集合 X {\displaystyle X} のチューリング次数が集合 Y {\displaystyle Y} のチューリング次数よりも小さいならば、ある数が Y {\displaystyle Y} に含まれるかを正しく判定するあらゆる(計算不可能なものも含む)手続きは、ある数が X {\displaystyle X} に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。
チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。