チューリング次数
チューリング次数（～じすう、）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。
任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。更に、チューリング次数は半順序を成すので、集合 formula_1 のチューリング次数が集合 formula_2 のチューリング次数よりも小さいならば、ある数が formula_2 に含まれるかを正しく判定するあらゆる（計算不可能なものも含む）手続きは、ある数が formula_1 に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。
チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。