チューリングジャンプ

集合 X と X-計算可能（X から相対的に計算可能）な関数のゲーデル数 ${\displaystyle \varphi _{i}^{X}}$ があるとする。このとき、X のチューリングジャンプ X’は次のように定義される。

n番目のチューリングジャンプ X⁽ⁿ⁾ は次のように帰納的に定義される。

X の ω ジャンプ X^(ω) は 集合の列 ${\displaystyle \langle X^{(n)}\mid n\in \mathbb {N} \rangle }$ の effective join(en) である:

ここで ${\displaystyle p_{i}}$ は i 番目の素数を表す。

0’は空集合のチューリングジャンプを表す記号としてよく使われる。これは次の書き方もある。

同様に、 ${\displaystyle 0^{(n)}}$ は空集合の n 番目のジャンプである。

• 空集合のチューリングジャンプ ${\displaystyle \emptyset '}$ は停止問題にチューリング同値である。
• 全ての n について、集合 ${\displaystyle \emptyset ^{(n)}}$ は算術的階層のレベル ${\displaystyle \Sigma _{n}^{0}}$ においてm-完全。
• X の述語を含むペアノ算術において真である式のゲーデル数から成る集合は、${\displaystyle X^{(\omega )}}$ から相対的に計算可能。