相対計算可能性とチューリング次数

ウィキペディア小見出し辞書

相対計算可能性とチューリング次数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)

「再帰理論」の記事における「相対計算可能性とチューリング次数」の解説

詳細は「チューリング還元」および「チューリング次数」を参照 数理論理学における再帰理論は、伝統的に相対計算可能性（relative computability）に注目してきた。これは、チューリングが1939年に神託機械を使って定義したチューリング計算可能性を一般化したものである。神託機械は、普通のチューリングマシンにオラクルへの質問機能を加えた仮説的な機械である。オラクルは自然数の特別な集合であり、「n はオラクル集合の中にあるか?」という形式の問いにだけ答えることができる。その回答は、たとえそのオラクル集合が計算不可能であっても即座に行われる。従って、計算不可能なオラクルを持った神託機械は、オラクルなしでは計算不可能な集合を計算することができる。 非形式的に言えば、自然数の集合 A が集合 B にチューリング還元可能であるとは、B をオラクル集合として持つ神託機械を用いれば、ある数が A に属するかどうかを正しく示せることを意味する（この例では、集合 A は B から（相対的に）計算可能、 B について再帰的とも称する）。集合 A が集合 B にチューリング還元可能であり、かつ、B が A にチューリング還元可能であるとき、これらの集合は同じチューリング次数（「決定不能性の次数」とも）を持つと言う。ある集合のチューリング次数は、その集合の計算不能な度合いの正確な尺度となる。 計算不能な集合の自然な例として、さまざまな形の停止問題を符号化して得られる互いに異なる集合たちがあるが、それらには次のような共通点がある。 それらは帰納的可算集合である。 多対一還元によって互いに変換可能である。すなわち、集合 A と B について、A = {x : f(x) ∈ B} となる計算可能関数 f が存在する。これらの集合を多対一同値（またはm-同値）であるという。 多対一還元はチューリング還元より強い。計算不能集合の自然な例は全て多対一同値だが、A を B にチューリング還元可能だが多対一還元不可能な帰納的可算集合 A と B を構築することもできる。すべての帰納的可算集合は停止問題に多対一還元可能であることが判っているので、多対一還元とチューリング還元の観点で、停止問題は最も複雑な帰納的可算集合である。1944年、ポストは、すべての帰納的可算集合は計算可能かあるいは停止問題にチューリング同値かのいずれかだろうか、という疑問を投げかけた。つまり、チューリング次数がこの2つの間になるような帰納的可算集合は存在するか、という問いである。 その問題を考える過程で、ポストは帰納的可算集合の分類として単純集合/超単純集合/超々単純集合といった自然な型を定義した。ポストはこれらの集合が、多対一還元の観点から見たとき、計算可能集合と停止問題の厳密に中間に位置することを示した。ポストはまた、チューリング還元よりも強い意味の還元（真理値表還元）を用いた場合においても、それらの一部が厳密に中間に位置することを示した。しかし、結局ポストは中間のチューリング次数を持つ帰納的可算集合が存在するかという主問題は未解決のまま残し、これはポストの問題(en)と呼ばれるようになった。10年後の1954年、クリーネとポストは計算可能集合と停止問題の間のチューリング次数が存在することは示せたが、そのチューリング次数に属する帰納的可算集合が存在するかは示せなかった。その直後、Friedberg と Muchnik がそれぞれ独立に中間次数の帰納的可算集合が存在することを示し、ポストの問題を解決した。この画期的な成果により、帰納的可算集合のチューリング次数に関する広範な研究が始まり、非常に複雑かつ自明でない構造の存在が明らかになった。 帰納的可算でない集合は非可算個存在しており、一般の集合のチューリング次数に関する研究も、帰納的可算なチューリング次数に関する研究と同様に、再帰理論における主要な研究対象である。様々な特定の次数が構成されている。 hyperimmune-free degrees：この次数から相対的に計算可能な関数は（非相対化された）計算可能関数によって majorize される high degrees：この次数からは（全ての計算可能関数 g を支配するような）関数 f が相対的に計算可能。ここでいう支配とは、g に依存する定数 c が存在し、全ての x > c についてg(x) < f(x)が成り立つことを指す random degrees：アルゴリズム的ランダムな無限列が該当 1-generic degrees：1-generic集合の次数 極限再帰（英語版）集合の停止問題より下の次数 任意のチューリング次数（帰納的可算とは限らない）の研究では、チューリングジャンプの研究が関係してくる。ある集合 A のチューリングジャンプとは、オラクル集合 A を持つ神託機械の停止問題を符号化した自然数の集合である。任意の集合のチューリングジャンプは、元の集合よりチューリング次数が常に高く、Friedberg の定理によって、停止問題を計算する任意の集合は別の集合のチューリングジャンプとなることが示されている。ポストの定理は、チューリングジャンプと算術的階層（算術における定義可能性に基づいて自然数の部分集合を分類したもの）との密接な関係を示している。 チューリング次数に関する近年の研究は、チューリング次数の集合の全体構造と、帰納的可算集合のチューリング次数の集合に注目してきた。Shore と Slaman (1999)の深い定理によれば、次数 x をそのチューリングジャンプの次数に変換するような関数は、チューリング次数のなす半順序の中で定義できる。Ambos-Spies and Fejer (2006) にそのような研究の歴史が概観されている。