チューリングジャンプのソースを表示

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

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

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

==定義==

集合 X と [[相対計算可能性|X-計算可能]]（X から相対的に計算可能）な関数の[[ゲーデル数]] <math>\varphi_i^X</math> があるとする。このとき、X のチューリングジャンプ X’は次のように定義される。
{{Indent|<math>X'= \{x \mid \varphi_x^X(x) \ \mbox{is defined} \}.</math><ref>訳注：ゲーデル数が指す決定問題に、それ自身を入力した時の結果が defined （＝停止する）だと言っているので、つまり X’は X（をオラクルとして保有する神託機械）の停止問題の解法を符号化した集合である。X は自分自身の停止問題は解けないので、それを解ける X’との間にはジャンプが存在し、階層を成すことが解る。</ref>}}

'''''n''番目のチューリングジャンプ''' X<sup>(''n'')</sup> は次のように帰納的に定義される。
{{Indent|<math>X^{(0)} = X, \,</math><br />
<math>X^{(n+1)}=(X^{(n)})'. \,</math>}}

X の '''&omega; ジャンプ''' X<sup>(&omega;)</sup> は 集合の列 <math>\langle X^{(n)}\mid n \in \mathbb{N}\rangle</math> の effective join([[:en:effective join|en]]) である:

{{Indent|<math>X^{(\omega)} = \{p_i^k \mid k \in X^{(i)}\},\,</math>}}

ここで <math>p_i</math> は ''i'' 番目の素数を表す。

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

{{Indent|<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
* {{cite book
 | author = Lerman, M.
 | year = 1983
 | title = Degrees of unsolvability: local and global theory
 | publisher = Berlin; New York: Springer-Verlag
 | isbn = 3-540-12155-2
}}
* {{cite book
 | author = Rogers Jr, H.
 | year = 1987
 | title = Theory of recursive functions and effective computability
 | publisher = MIT Press Cambridge, MA, USA
 | isbn = 0-07-053522-1
}}
* {{cite journal
 | author = Shore, R.A.
 | coauthors = Slaman, T.A.
 | year = 1999
 | title = Defining the Turing jump
 | journal = Math. Res. Lett.
 | volume = 6
 | issue = 5-6
 | pages = 711-722
 | url = http://www.mrlonline.org/mrl/1999-006-006/1999-006-006-010.pdf
 | accessdate = 2008-07-13
}}
* {{cite book
 | author = Soare, R.I.
 | year = 1987
 | title = Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets
 | publisher = Springer
 | isbn = 3-540-15299-7
}}

==脚注==
<references/>

{{DEFAULTSORT:ちゆうりんくしやんふ}}

[[Category:数理論理学]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]