チューリングジャンプ

計算可能性理論において、チューリングジャンプまたはチューリングジャンプ演算子は、アラン・チューリングにちなんで名付けられ、各決定問題 Xに、 X ′ がXの神託を持つ神託マシンによって決定可能ではないという特性を持つ、次第に難しくなる決定問題X ′を割り当てる操作です。

この演算子は、問題Xのチューリング次数を増やすため、ジャンプ演算子と呼ばれます。つまり、問題X ′ はXにチューリング還元できません。ポストの定理は、チューリングジャンプ演算子と自然数の集合の算術階層との関係を確立します。 ^[1]非公式には、問題が与えられると、チューリングジャンプは、その問題を解決するオラクルへのアクセスを与えられたときに停止するチューリングマシンの集合を返します。

Xのチューリングジャンプは、Xのオラクルを持つオラクルマシンの停止問題に対するオラクルと考えることができる。^[1]

正式には、集合XとX計算可能関数のゲーデル数 φ _i ^Xが与えられたとき、XのチューリングジャンプX ′は次のように定義される。

${\displaystyle X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{が定義される}}\}}.}$

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

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

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

Xのω ジャンプX ^(ω)は、n ∈ Nの集合のシーケンスX ^{( n )}の有効な結合です。

${\displaystyle X^{(\omega )}=\{p_{i}^{k}\mid i\in \mathbb {N} {\text{ および }}k\in X^{(i)}\},}$

ここで、p _{i は}i番目の素数を表します。

0′または∅′という表記は、空集合のチューリングジャンプを表すためによく使用されます。これはゼロジャンプまたはゼロプライムと読みます。

同様に、0 ^{( n )は}空集合のn番目のジャンプです。有限のnに対して、これらの集合は算術階層と密接に関連しており、^[2]特にポストの定理と関連しています。

ジャンプは超限順序数に反復することができます。がクリーネのコードを持つ順序数である場合、自然数の集合に対するジャンプ演算子が存在します（コードに関係なく、結果として得られるジャンプはスペクターの定理により同じです）^[2]。特に、ω ₁ ^CKがチャーチ–クリーネ順序数であるとき、α < ω ₁ ^CKに対する集合0 ^(α)は、超算術階層と密接に関連しています。^[1] ω ₁ ^CK を超えて、ジェンセンのゲーデルの Lの微細構造理論に関する研究を使用して、構成可能宇宙の可算順序数を通してプロセスを続けることができます。^{[3] [2]この概念は、非可算な}正則基数 に拡張するように一般化されています。^[4]${\displaystyle j^{\delta}}$${\displaystyle \delta}$${\displaystyle {\mathcal {O}}}$

• 空集合のチューリングジャンプ0′は停止問題とチューリング同値である。^[5]
• 各nに対して、集合0 ^{( n ) は}算術階層のレベルでm 完全である(ポストの定理による)。${\displaystyle \Sigma _{n}^{0}}$
• Xに対する述語を持つペアノ算術言語における真の公式のゲーデル数の集合は、X ^(ω)から計算可能である。^[6]

• X ′はX計算可能列挙可能であるが、 X計算可能ではない。
• AがBとチューリング同値である場合、A ′ はB ′とチューリング同値です。この含意の逆は真ではありません。
• (ショアとスラマン、1999) XをX ′に写像する関数はチューリング次数の半順序で定義できる。 ^[5]

チューリングジャンプ演算子の多くの特性については、チューリング次数に関する記事で説明されています。

• Ambos-Spies, K. および Fejer, P. 解決不可能性の度合い。未発表。http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• レルマン、M. (1983)。解決不可能性の度合い：局所理論と全体理論。ベルリン、ニューヨーク：シュプリンガー・フェアラーグ。ISBN 3-540-12155-2。
• Lubarsky, Robert S. (1987 年 12 月)。「非可算マスター コードとジャンプ階層」。Journal of Symbolic Logic。第 52 巻、第 4 号。952 ～ 958 ページ。JSTOR 2273829  。
• Rogers Jr, H. (1987).再帰関数の理論と効果的な計算可能性. MIT Press , Cambridge, MA, USA. ISBN 0-07-053522-1。
• Shore, RA; Slaman, TA (1999). 「チューリングジャンプの定義」(PDF) . Mathematical Research Letters . 6 (5–6): 711–722. doi : 10.4310/mrl.1999.v6.n6.a10 . 2008-07-13に閲覧。
• Soare, RI (1987)。『再帰的に列挙可能な集合と次数：計算可能な関数と計算可能に生成された集合の研究』。Springer。ISBN 3-540-15299-7。