チューリングジャンプ

チューリングジャンプについて

チューリングジャンプ（Turing jump、または Turing jump operator）は、計算可能性理論における重要な操作の一つです。この名称は、計算の基礎を築いたアラン・チューリングや彼が提案したチューリングマシンに由来しています。チューリングジャンプの主な役割は、特定の決定問題 X に対して、さらに複雑な決定問題 X’を関連付けることにあります。ここで、問題 X’は、Xを解決するためのオラクルを持つ神託機械では決定できないような問題を指しています。このように、チューリングジャンプは問題の難易度を引き上げる働きを持つため「ジャンプ作用素」とも呼ばれています。

定義

まず、集合 X とそれに相対的に計算可能な関数のゲーデル数を考えます。これを記号で表すと、φ_i^X という形になります。このとき、X のチューリングジャンプ X' は以下のように定義されます。

n 番目のチューリングジャンプ X(n) は帰納的に定義されます。また、X の ω ジャンプ X(ω) は、集合の列 ⟨X(n) | n ∈ N⟩の effective join として表されます。ここで p_i により i 番目の素数を表しています。

空集合のチューリングジャンプを示す記号として、様々な表現が使われます。特に、0’は空集合のチューリングジャンプを示す一般的な記号であり、これに対し、0(n) は空集合の n 番目のジャンプを示す記号です。

例

空集合のチューリングジャンプ、記号で表すと ∅’は、実際には停止問題にチューリング同値であることが知られています。全ての n に対している集合 ∅(n) は、算術的階層のレベル Σ_n^0 において m-完全です。さらに、X の述語を含むペアノ算術において真である式のゲーデル数から構成された集合は、X(ω) から相対的に計算可能であることも興味深い事実です。

性質

チューリングジャンプにはいくつかの興味深い性質があります。たとえば、X'は確かに X-帰納的可算ですが、X-計算可能ではありません。また、もし A と B がチューリング同値であれば、A’と B’もチューリング同値です。ただし、この逆は必ずしも成り立つわけではありません。さらに、X から X’への関数の対応付けは、チューリング次数の半順序集合の中で定義することができます。これにより、チューリングジャンプ作用素が持つ様々な性質を調査することができます。

参考文献

詳細な理解を深めるために、いくつかの文献を挙げておきます。

• - Ambos-Spies, K. & Fejer, P.(未出版). Degrees of Unsolvability.
• - Lerman, M. (1983). Degrees of unsolvability: local and global theory. Berlin; New York: Springer-Verlag.
• - Rogers Jr, H. (1987). Theory of recursive functions and effective computability. MIT Press Cambridge, MA, USA.
• - Shore, R.A.; Slaman, T.A. (1999). “Defining the Turing jump”. Math. Res. Lett. 6 (5-6): 711-722.
• - Soare, R.I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer.

チューリングジャンプは、計算可能性の研究において非常に重要な考え方であり、決定問題に対する新たな視点を提供します。この概念の理解は、計算理論や関連する数学分野において、強力な洞察を与える役割を果たします。

もう一度検索