チューリングジャンプ

チューリングジャンプ（Turing jump または Turing jump operator）とは、計算可能性理論におけるある数学的な操作に付与された名前。名称はアラン・チューリングに因む。直感的に言えば、何らかの決定問題 X について、より難しい決定問題 X’を対応付けることである。ここでいう X’は、X を解けるようなオラクルを持つ神託機械では決定出来ない問題を指す。
この作用素は問題 X のチューリング次数を増やす（ジャンプさせる）ので「ジャンプ作用素」と呼ばれる。つまり問題 X’は X にチューリング還元可能ではない。
ポストの定理はチューリングジャンプ作用素と自然数の集合の算術的階層との関係を明らかにしている。
定義.
集合 X と X-計算可能（X から相対的に計算可能）な関数のゲーデル数 formula_1 があるとする。このとき、X のチューリングジャンプ X’は次のように定義される。
"n"番目のチューリングジャンプ X("n") は次のように帰納的に定義される。
X の ω ジャンプ X(ω) は 集合の列 formula_2 の effective join() である:
ここで formula_3 は "i" 番目の素数を表す。
0’は空集合のチューリングジャンプを表す記号としてよく使われる。これは次の書き方もある。
同様に、 formula_4 は空集合の "n" 番目のジャンプである。
性質.
チューリングジャンプ作用素が持つ様々な性質について、チューリング次数を参照されたい。