チューリングジャンプ

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

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

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

定義

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

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

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

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

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

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

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

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

${\displaystyle \emptyset '.}$

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

例

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

性質

• X’は X-帰納的可算だが X-計算可能ではない。
• もし A と B がチューリング同値なら、A’と B’もチューリング同値である。この逆は成り立たない。
• (ShoreとSlaman, 1999) X から X’への関数の対応付けはチューリング次数の成す半順序集合の中で定義可能。

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

参考文献

• 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. http://www.mrlonline.org/mrl/1999-006-006/1999-006-006-010.pdf 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