チューリング還元

チューリング還元

チューリング還元（Turing reduction）は、計算量理論の中で重要な役割を果たす概念の一つです。この考え方は、ある問題の解決が別の問題の解決に依存していることを示します。具体的には、ある問題 A が問題 B に対してチューリング還元されるとは、問題 B が簡単に解けると仮定した場合に、問題 A もまた簡単に解けるということを意味します。

この概念は、アラン・チューリングが1939年に提唱したもので、彼は神託機械を用いて相対計算可能性を正式に定義しました。彼の理論に基づき、1944年にはエミール・ポストが「チューリング還元可能性」という用語を初めて使用しました。チューリング還元は、決定問題に限らず、関数問題にも適用できます。

チューリング還元の定義

具体的には、2つの集合 A と B があるとき、A が B にチューリング還元可能であるとは、B に関する神託を持つ神託機械を利用して A の特性関数を計算できることです。この関係は次のように表されます：

A ≤ T B

この記号は、A が B に対してチューリング還元可能であることを意味します。また、他にも B-帰納的（B-recursive）または B-計算可能（B-computable）とも表現されます。

さらに、もし A が B にチューリング同値である場合は、次のように表します：

A ≡ T B

この場合、A と B の両方が互いにチューリング還元可能であることを示します。

具体例

例えば、インデックス e のチューリングマシンが受け取る停止する入力値を W_e とするとします。この場合、

A = { e | e ∈ W_e }
B = { (e, n) | n ∈ W_e }

となる集合 A と B は、チューリング同値です。A から B へのチューリング還元は、

e ∈ A ⇔ (e, e) ∈ B

という関係から導かれ、B から A への還元も成立します。このようにして、A と B は相互依存する関係にあることがわかります。

チューリング還元の特性

チューリング還元にはいくつかの重要な特性があります。まず、任意の集合は自身の補集合とチューリング同値であって、帰納的集合は他の帰納的集合にチューリング還元可能です。また、チューリング還元は推移的であり、この関係は擬順序関係として機能します。さらに、チューリング還元不可能な集合の対も存在します。

より強い還元と弱い還元

チューリング還元よりも弱い還元の手法としては、神託の回数や方式を制限するものや、計算資源を制限するものがあります。逆に、チューリング還元よりも強い還元も検討されており、特定の公理や構造を用いて問題を定義することが可能です。

このように、チューリング還元は計算量理論における基本的かつ重要な概念であり、未来の計算理論の研究においても引き続き重要な役割を果たしています。

もう一度検索