チューリングジャンプ
X’は X-帰納的可算だが X-計算可能ではない。
もし A と B がチューリング同値なら、A’と B’もチューリング同値である。この逆は成り立たない。
(ShoreとSlaman, 1999) X から X’への関数の対応付けはチューリング次数の成す半順序集合の中で定義可能。
チューリングジャンプ作用素が持つ様々な性質について、チューリング次数を参照されたい。
X の ω ジャンプ X は 集合の列 ⟨ X ( n ) ∣ n ∈ N ⟩ {\displaystyle \langle X^{(n)}\mid n\in \mathbb {N} \rangle } の effective join(en) である:
X ( ω ) = { p i k ∣ k ∈ X ( i ) } , {\displaystyle X^{(\omega )}=\{p_{i}^{k}\mid k\in X^{(i)}\},\,}
ここで p i {\displaystyle p_{i}} は i 番目の素数を表す。
0’は空集合のチューリングジャンプを表す記号としてよく使われる。これは次の書き方もある。
∅ ′ . {\displaystyle \emptyset '.}
同様に、 0 ( n ) {\displaystyle 0^{(n)}} は空集合の n 番目のジャンプである。