チューリングジャンプ

ウィキペディア

チューリングジャンプ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/13 10:14 UTC 版)

チューリングジャンプ（Turing jump または Turing jump operator）とは計算可能性理論における操作の一つ。名称はアラン・チューリングやチューリングマシンに因む。

直感的に言えば、何らかの決定問題 X について、より難しい決定問題 X’を対応付けることである。ここでいう X’は、X を解けるようなオラクルを持つ神託機械では決定出来ない問題を指す。

この作用素は問題 X のチューリング次数を増やす（ジャンプさせる）ので「ジャンプ作用素」と呼ばれる。つまり問題 X’は X にチューリング還元可能ではない。 ポストの定理はチューリングジャンプ作用素と自然数の集合の算術的階層との関係を明らかにしている。

定義

集合 X と X-計算可能（X から相対的に計算可能）な関数のゲーデル数 $\varphi _{i}^{X}$