チューリングジャンプ

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

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

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

定義

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

$X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{is defined}}\}.$ ^[1]

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

$X^{(0)}=X,\,$
$X^{(n+1)}=(X^{(n)})'.\,$

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

$X^{(\omega )}=\{p_{i}^{k}\mid k\in X^{(i)}\},\,$

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

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

$\emptyset '.$

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

チューリングジャンプ作用素が持つ様々な性質について、チューリング次数を参照されたい。

Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. 未出版。 http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
Lerman, M. (1983). Degrees of unsolvability: local and global theory. Berlin; New York: Springer-Verlag. ISBN 3-540-12155-2
Rogers Jr, H. (1987). Theory of recursive functions and effective computability. MIT Press Cambridge, MA, USA. ISBN 0-07-053522-1
Shore, R.A.; Slaman, T.A. (1999). “Defining the Turing jump”. Math. Res. Lett. 6 (5-6): 711-722 2008年7月13日閲覧。.
Soare, R.I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. ISBN 3-540-15299-7

^ 訳注：ゲーデル数が指す決定問題に、それ自身を入力した時の結果が defined （＝停止する）だと言っているので、つまり X’は X（をオラクルとして保有する神託機械）の停止問題の解法を符号化した集合である。X は自分自身の停止問題は解けないので、それを解ける X’との間にはジャンプが存在し、階層を成すことが解る。