計算可能枚挙可能集合とチューリング次数

計算可能枚挙可能集合とは、その要素を効果的に列挙できる集合であり、チューリング次数は、相対的な計算可能性によってすべての集合をランク付けし、未解決問題の状況を整理します。

Definition

あるアルゴリズムがその要素を正確に列挙する場合、その集合は計算可能枚挙可能であるとされます。ある集合が別の集合にチューリング還元可能であるとは、その別の集合をオラクルとして使用して計算できる場合を指し、相互還元可能性の下での同値類がチューリング次数であり、相対的な計算可能性によって半順序付けられます。

Scope

このトピックでは、計算可能枚挙可能集合とその基本的な特性、チューリング還元可能性と次数の半順序、完全枚挙可能集合としての停止集合、ポストの問題とその優先度法による解決、および計算可能枚挙可能次数の構造理論について扱います。

Core questions

• 計算可能集合と単に計算可能枚挙可能集合の違いは何ですか？
• チューリング還元可能性は2つの集合の困難さをどのように比較しますか？
• 計算可能集合と停止問題の間に厳密に位置する計算可能枚挙可能次数は存在しますか？
• 決定不能性の次数の全体構造はどうなっていますか？

Key theories

補集合と停止集合

集合が計算可能であるのは、その集合と補集合の両方が計算可能枚挙可能である場合のみであり、停止集合は計算可能枚挙可能ですが計算可能ではなく、典型的な完全枚挙可能集合です。

ポストの問題と優先度法

ポストは、計算可能集合と停止問題の間に厳密に位置する計算可能枚挙可能次数が存在するかどうかを問い、フリードバーグとムチニクは有限損傷優先度法を発明することによって「はい」と答えました。

次数の構造

チューリング次数と計算可能枚挙可能次数は、高度な優先度構成を通じて研究される豊かで密な順序構造を形成し、複雑な定義可能性と埋め込み特性を明らかにします。

Clinical relevance

次数の理論は、未解決問題の精密な分類を提供し、決定不能性が無限に多くの厳密に増加するレベルで存在することを示しています。また、それらを研究するために開発された優先度法は、逆数学やアルゴリズム的ランダム性の分析に影響を与えた中心的な証明手法です。

History

ポストは1944年に計算可能枚挙可能集合を導入し、不完全な非計算可能枚挙可能次数が存在するかどうかを問う問題を提起しました。フリードバーグとムチニクは、1956年頃に優先度法を用いて独立にこれを解決し、この方法はサックス、ソア、その他多くの研究者によって追求された次数の深い構造研究の主要なツールとなりました。

Key figures

• Emil Post
• Richard Friedberg
• Albert Muchnik
• Robert Soare

Seminal works

• soare1987
• post1944
• rogers1987

Frequently asked questions

計算可能性理論におけるオラクルとは何ですか？

オラクルとは、固定された集合に対するメンバーシップの質問に即座に答える外部ソースです。オラクルを持つ機械は、計算中にそれらの回答を使用でき、チューリング還元可能性は、ある集合が別の集合をオラクルとして備えた機械によって計算できるかどうかを問います。

ポストの問題はなぜ重要だったのですか？

それは、計算可能枚挙可能集合の中で、決定可能集合と停止問題の間に中間的なレベルの決定不能性が存在するかどうかを問うものでした。肯定的な回答は、次数の微細な構造を明らかにし、主題全体を形作った強力な新しい手法である優先度法を必要としました。