チューリングジャンプ
チューリングジャンプ（Turing jump または Turing jump operator）とは、計算可能性理論におけるある数学的な操作に付与された名前。名称はアラン・チューリングに因む。直感的に言えば、何らかの決定問題 X について、より難しい決定問題 X’を対応付けることである。ここでいう X’は、X を解けるようなオラクルを持つ神託機械では決定出来ない問題を指す。
この作用素は問題 X のチューリング次数を増やす（ジャンプさせる）ので「ジャンプ作用素」と呼ばれる。つまり問題 X’は X にチューリング還元可能ではない。 ポストの定理はチューリングジャンプ作用素と自然数の集合の算術的階層との関係を明らかにしている。
定義
集合 X と X-計算可能（X から相対的に計算可能）な関数のゲーデル数 [math]\varphi_i^X[/math] があるとする。このとき、X のチューリングジャンプ X’は次のように定義される。
[math]X'= \{x \mid \varphi_x^X(x) \ \mbox{is defined} \}.[/math][1]
n番目のチューリングジャンプ X(n) は次のように帰納的に定義される。
[math]X^{(0)} = X, \,[/math]
[math]X^{(n+1)}=(X^{(n)})'. \,[/math]
X の ω ジャンプ X(ω) は 集合の列 [math]\langle X^{(n)}\mid n \in \mathbb{N}\rangle[/math] の effective join(en) である:
[math]X^{(\omega)} = \{p_i^k \mid k \in X^{(i)}\},\,[/math]
ここで [math]p_i[/math] は i 番目の素数を表す。
0’は空集合のチューリングジャンプを表す記号としてよく使われる。これは次の書き方もある。
[math]\emptyset'.[/math]
同様に、 [math]0^{(n)}[/math] は空集合の n 番目のジャンプである。
例
- 空集合のチューリングジャンプ [math]\emptyset'[/math] は停止問題にチューリング同値である。
- 全ての n について、集合 [math]\emptyset^{(n)}[/math] は算術的階層のレベル [math]\Sigma^0_n[/math] においてm-完全。
- X の述語を含むペアノ算術において真である式のゲーデル数から成る集合は、[math]X^{(\omega)}[/math] から相対的に計算可能。
性質
- 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 . 2008閲覧..
- 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’との間にはジャンプが存在し、階層を成すことが解る。