チューリングジャンプ – Wikipedia

チューリングジャンプTuring jump または Turing jump operator)とは、計算可能性理論におけるある数学的な操作に付与された名前。名称はアラン・チューリングに因む。直感的に言えば、何らかの決定問題 X について、より難しい決定問題 X’を対応付けることである。ここでいう X’は、X を解けるようなオラクルを持つ神託機械では決定出来ない問題を指す。

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

集合 X と X-計算可能(X から相対的に計算可能)な関数のゲーデル数

φiX{displaystyle varphi _{i}^{X}}

があるとする。このとき、X のチューリングジャンプ X’は次のように定義される。

X′={x∣φxX(x) is defined}.{displaystyle X’={xmid varphi _{x}^{X}(x) {mbox{is defined}}}.}

[1]

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

X(0)=X,{displaystyle X^{(0)}=X,,}


X(n+1)=(X(n))′.{displaystyle X^{(n+1)}=(X^{(n)})’.,}

X の ω ジャンプ X(ω) は 集合の列

⟨X(n)∣n∈N⟩{displaystyle langle X^{(n)}mid nin mathbb {N} rangle }

の effective join(en) である:

X(ω)={pik∣k∈X(i)},{displaystyle X^{(omega )}={p_{i}^{k}mid kin X^{(i)}},,}

ここで

pi{displaystyle p_{i}}

i 番目の素数を表す。

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

∅′.{displaystyle emptyset ‘.}

同様に、

0(n){displaystyle 0^{(n)}}

は空集合の n 番目のジャンプである。

  • 空集合のチューリングジャンプ
    ∅′{displaystyle emptyset ‘}

    は停止問題にチューリング同値である。
  • 全ての n について、集合
    ∅(n){displaystyle emptyset ^{(n)}}

    は算術的階層のレベル Σn0{displaystyle Sigma _{n}^{0}}

    においてm-完全。
  • X の述語を含むペアノ算術において真である式のゲーデル数から成る集合は、
    X(ω){displaystyle X^{(omega )}}

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

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

参考文献[編集]

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