チューリング次数

この記事では以後「集合」と言えば「自然数の集合」を指すこととする。ある数が集合 ${\displaystyle X}$ の元かどうかを、オラクル集合 ${\displaystyle Y}$ を持つ神託機械を用いて決定できるとき、${\displaystyle X}$ は ${\displaystyle Y}$ にチューリング還元可能であると言い、${\displaystyle X\leq _{T}Y}$ と書く。

二つの集合 ${\displaystyle X}$ と ${\displaystyle Y}$ について、${\displaystyle X}$ が ${\displaystyle Y}$ にチューリング還元可能であり、かつ、 ${\displaystyle Y}$ が ${\displaystyle X}$ にチューリング還元可能であるとき、これらの集合は チューリング同値 であると言い、${\displaystyle X\equiv _{T}Y}$ と書く。${\displaystyle \equiv _{T}}$ という関係は同値関係と捉えることができる。すなわち任意の集合 ${\displaystyle X}$、${\displaystyle Y}$、${\displaystyle Z}$ について

• ${\displaystyle X\equiv _{T}X}$
• ${\displaystyle X\equiv _{T}Y}$ ならば ${\displaystyle Y\equiv _{T}X}$
• もし ${\displaystyle X\equiv _{T}Y}$ かつ ${\displaystyle Y\equiv _{T}Z}$ ならば、${\displaystyle X\equiv _{T}Z}$。

チューリング次数は関係 ${\displaystyle \equiv _{T}}$ の同値類である。${\displaystyle [X]}$ と書いて集合 ${\displaystyle X}$ を含むような同値類を表す。 チューリング次数全体を表す記号として ${\displaystyle {\mathcal {D}}}$ と書く。

チューリング次数は半順序 ${\displaystyle \leq }$を持つ。定義として、${\displaystyle [X]\leq [Y]}$ である必要十分条件は ${\displaystyle X\leq _{T}Y}$である。計算可能集合を全て含む特別なチューリング次数が存在し、この次数は他の如何なる次数よりも小さい。この次数は半順序集合 ${\displaystyle {\mathcal {D}}}$ の最小元なので、0（ゼロ）と書く。（チューリング次数を表記する際は、集合と混同しないように太字 (boldface) で書くのが普通である。混同する恐れが無いなら（例えば ${\displaystyle [X]}$ ）太字にせずとも良い。）

任意の集合 ${\displaystyle X}$ と ${\displaystyle Y}$ について、${\displaystyle X}$ と ${\displaystyle Y}$ の結び（ ${\displaystyle X\oplus Y}$ と書く）を、集合 ${\displaystyle {2n:n\in X}}$と${\displaystyle {2m+1:m\in Y}}$の和集合として定義できる。 ${\displaystyle X\oplus Y}$ のチューリング次数は ${\displaystyle X}$ と ${\displaystyle Y}$ の次数の上限である。従って ${\displaystyle {\mathcal {D}}}$ は結びを持つ半束である。 次数 a と b の上限を a ∪ b と書く。下限を持たない次数の対が存在するので、${\displaystyle {\mathcal {D}}}$ は束ではないことが知られている。

集合 ${\displaystyle X}$ について、${\displaystyle X}$ をオラクルに持つときに停止する神託機械を指すインデクスの集合を ${\displaystyle X'}$ と書く。集合${\displaystyle X'}$は${\displaystyle X}$のチューリングジャンプと呼ばれる。次数 ${\displaystyle [X]}$ のチューリングジャンプは次数 ${\displaystyle [X']}$ であると定義される。これは${\displaystyle X\equiv _{T}Y}$ であれば必ず ${\displaystyle X'\equiv _{T}Y'}$ ことからも妥当な定義である。一つの重要な例として 0′があるが、これは停止問題の次数である。

• 個々のチューリング次数は可算無限である。すなわち、一つの次数には丁度 ${\displaystyle \aleph _{0}}$ 個の集合が対応する。

• 互いに相異なるチューリング次数は ${\displaystyle 2^{\aleph _{0}}}$ 個存在する。

• 各次数 a について、不等式 a < a′ が厳密に成り立つ。

• 各次数 a について、a よりも小さい次数の集合の濃度はたかだか可算。a よりも大きい次数の集合の濃度は ${\displaystyle 2^{\aleph _{0}}}$。

チューリング次数の構造については大変多くの研究がある。以下に示す一覧は、知られている結果のごく一部を示すに過ぎない。一連の研究から得られた一つの一般的な結論は、チューリング次数の構造が極端に複雑だということである。

• 極小次数が存在する。 次数 a が「極小」であるとは、a が 0 でなく、かつ、次数 0 と a の間に他の次数が存在しないことである。従って次数の順序関係は稠密順序ではない。
• 0 でない全ての次数 a について、a とは比較不可能な次数 b が存在する。
• 互いに比較不可能なチューリング次数の対は ${\displaystyle 2^{\aleph _{0}}}$ 通りある。
• 次数の対で下限を持たないものが存在する。従って ${\displaystyle {\mathcal {D}}}$ は束ではない。
• 全ての可算な半順序集合は、チューリング次数に埋め込める。
• チューリング次数の狭義単調増加する無限列は、上限を持たない。

• 全ての次数 a について、a と a′の厳密に中間に位置する次数が存在する。実際に、a と a′の間にある互いに比較不可能な次数の対は可算個存在する。
• ある次数 a が b′と書ける必要十分条件は、0′≤ a。
• 如何なる次数 a についても、次数 b が存在して、a < b かつ b′= a′を満たす。このような次数 b を a から相対的に「低い」と呼ぶ。
• 全ての i について、${\displaystyle \mathbf {a} '_{i+1}\leq \mathbf {a} _{i}}$ を満たすような次数の無限列 a_i が存在する。

• (Simpson 1977) ${\displaystyle {\mathcal {D}}}$ の言語{${\displaystyle \left\langle \leq ,=\right\rangle }$} または {${\displaystyle \left\langle \leq ,',=\right\rangle }$} を用いた一階理論は真の二階算術に多対一同値。これは ${\displaystyle {\mathcal {D}}}$ の構造が極端に複雑であることを示している。
• (Shore and Slaman, 1999) ジャンプ作用素は次数の一階構造の中で言語 ${\displaystyle \left\langle \leq ,=\right\rangle }$ を用いて定義可能。