チューリング次数
チューリング次数(~じすう、英: Turing degree, degree of unsolvability)は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ(非可解性)の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。
任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。
個々のチューリング次数は可算無限である。すなわち、一つの次数には丁度 א 0 {\displaystyle \aleph _{0}} 個の集合が対応する。
互いに相異なるチューリング次数は 2 א 0 {\displaystyle 2^{\aleph _{0}}} 個存在する。
各次数 a について、不等式 a < a′ が厳密に成り立つ。
各次数 a について、a よりも小さい次数の集合の濃度はたかだか可算。a よりも大きい次数の集合の濃度は 2 א 0 {\displaystyle 2^{\aleph _{0}}} 。
極小次数が存在する。 次数 a が「極小」であるとは、a が 0 でなく、かつ、次数 0 と a の間に他の次数が存在しないことである。従って次数の順序関係は稠密順序ではない。
0 でない全ての次数 a について、a とは比較不可能な次数 b が存在する。
互いに比較不可能なチューリング次数の対は 2 א 0 {\displaystyle 2^{\aleph _{0}}} 通りある。
次数の対で下限を持たないものが存在する。従って D {\displaystyle {\mathcal {D}}} は束ではない。
全ての可算な半順序集合は、チューリング次数に埋め込める。
チューリング次数の狭義単調増加する無限列は、上限を持たない。