チューリングジャンプ
空集合のチューリングジャンプ ∅ ′ {\displaystyle \emptyset '} は停止問題にチューリング同値である。
全ての n について、集合 ∅ ( n ) {\displaystyle \emptyset ^{(n)}} は算術的階層のレベル Σ n 0 {\displaystyle \Sigma _{n}^{0}} においてm-完全。
X の述語を含むペアノ算術において真である式のゲーデル数から成る集合は、 X ( ω ) {\displaystyle X^{(\omega )}} から相対的に計算可能。
集合 X と X-計算可能(X から相対的に計算可能)な関数のゲーデル数 φ i X {\displaystyle \varphi _{i}^{X}} があるとする。このとき、X のチューリングジャンプ X’は次のように定義される。
X ′ = { x ∣ φ x X ( x ) is defined } . {\displaystyle X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{is defined}}\}.}
n番目のチューリングジャンプ X は次のように帰納的に定義される。
X ( 0 ) = X , {\displaystyle X^{(0)}=X,\,} X ( n + 1 ) = ( X ( n ) ) ′ . {\displaystyle X^{(n+1)}=(X^{(n)})'.\,}