|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
チューリングジャンプ（Turing jump または Turing jump operator）とは、計算可能性理論におけるある数学的な操作に付与された名前。名称はアラン・チューリングに因む。直感的に言えば、何らかの決定問題 X について、より難しい決定問題 X’を対応付けることである。ここでいう X’は、X を解けるようなオラクルを持つ神託機械では決定出来ない問題を指す。 この作用素は問題 X のチューリング次数を増やす（ジャンプさせる）ので「ジャンプ作用素」と呼ばれる。つまり問題 X’は X にチューリング還元可能ではない。 ポストの定理はチューリングジャンプ作用素と自然数の集合の算術的階層との関係を明らかにしている。 ==定義== 集合 X と X-計算可能（X から相対的に計算可能）な関数のゲーデル数 があるとする。このとき、X のチューリングジャンプ X’は次のように定義される。 ''n''番目のチューリングジャンプ X(''n'') は次のように帰納的に定義される。 X の ω ジャンプ X(ω) は 集合の列 の effective join(en) である: ここで は ''i'' 番目の素数を表す。 0’は空集合のチューリングジャンプを表す記号としてよく使われる。これは次の書き方もある。 同様に、 は空集合の ''n'' 番目のジャンプである。 X の ω ジャンプ X(ω) は 集合の列 の effective join(en) である: ここで は ''i'' 番目の素数を表す。 0’は空集合のチューリングジャンプを表す記号としてよく使われる。これは次の書き方もある。 同様に、 は空集合の ''n'' 番目のジャンプである。 ω ジャンプ X(ω) は 集合の列 の effective join(en) である: ここで は ''i'' 番目の素数を表す。 0’は空集合のチューリングジャンプを表す記号としてよく使われる。これは次の書き方もある。 同様に、 は空集合の ''n'' 番目のジャンプである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「チューリングジャンプ」の詳細全文を読む スポンサード リンク
|