チューリング度

コンピュータ科学や数理論理学において、チューリング度（アラン・チューリングにちなんで名付けられた）または自然数の集合の解けにくさの度合いは、その集合のアルゴリズム的な解けにくさのレベルを測定する。

チューリング次数という概念は計算可能性理論において基本的なものであり、自然数の集合はしばしば決定問題として扱われます。集合のチューリング次数は、その集合に関連付けられた決定問題、つまり任意の数が与えられた集合に含まれるかどうかを判定する問題の難易度を示す尺度です。

2つの集合は、解けないレベルが同じであればチューリング等価である。各チューリング次数はチューリング等価な集合の集合であるため、2つの集合が異なるチューリング次数にあるのは、それらがチューリング等価でないときである。さらに、チューリング次数は部分的に順序付けられているため、集合Xのチューリング次数が集合Yのチューリング次数より小さい場合、 Yに数が含まれるかどうかを正しく判定する（計算不可能な場合もある）手続きは、Xに数が含まれるかどうかを正しく判定する手続きに効果的に変換できる。この意味で、集合のチューリング次数は、その集合のアルゴリズム的解けないレベルに対応する。

チューリング次数はポスト（1944年）によって導入され、クリーネとポスト（1954年）によって多くの基本的な結果が確立されました。チューリング次数はそれ以来、集中的な研究分野となっています。この分野の多くの証明では、優先権法として知られる証明手法が用いられています。

この記事の残りの部分では、 「集合」という言葉は自然数の集合を指すものとします。集合Xが集合Yにチューリング還元可能であるとは、 Yへの帰属に関するオラクルが与えられたときに、Xへの帰属を決定するオラクル チューリング マシンが存在する場合をいいます。表記X ≤ _T Yは、 XがYにチューリング還元可能であることを示します。

2つの集合XとYは、 XがYにチューリング還元可能であり、かつYがXにチューリング還元可能である場合に、チューリング同値であると定義される。表記X≡TYは_、XとYがチューリング同値であることを示す。関係≡T_は同値関係と見なすことができ、これはすべての集合X、Y、Zに対して次のことを意味する。

• X ≡ _T X
• X ≡ _T YならばY ≡ _T Xが成り立つ
• X ≡ _T YかつY ≡ _T ZならばX ≡ _T Zである。

チューリング次数は、関係≡ _Tの同値類です。表記 [ X ] は、集合Xを含む同値類を表します。チューリング次数の全集合は、${\displaystyle {\mathcal {D}}}$。

チューリング次数には、X ≤ _T Yの場合に限り[ X ] ≤ [ Y ]となるような半順序≤ が定義されています。すべての計算可能集合を含むチューリング次数は一意であり、この次数は他のすべての次数よりも小さいです。これは半順序集合の最小要素であるため、 0 (ゼロ)と表記されます。${\displaystyle {\mathcal {D}}}$（チューリング次数を集合と区別するために、太字表記を用いるのが一般的です。ただし、[ X ] のように混同が生じる可能性が全くない場合は、太字表記は不要です。）

任意の集合XとYに対して、集合XとYの結合X ⊕ Yは、集合{2 n : n ∈ X } と {2 m +1 : m ∈ Y } の和集合として定義される。X ⊕ Yのチューリング次数は、XとYの次数の最小上界である。したがって  ${\displaystyle {\mathcal {D}}}$は結合半束である。次数aとbの最小上限はa ∪ bで表される。${\displaystyle {\mathcal {D}}}$これは格子ではありません。なぜなら、最大下限を持たない次数のペアが存在するからです。

任意の集合Xに対して、表記X ′ は、Xをオラクルとして使用したときに (そのインデックスを入力として与えられたときに) 停止するオラクル マシンのインデックス の集合を表します。集合X ′は、 Xのチューリング ジャンプと呼ばれます。次数 [ X ] のチューリング ジャンプは、次数 [ X ′ ] として定義されます。これは、 X ≡ _T Yである限り、X ′ ≡ _T Y ′であるため、有効な定義です。重要な例は、停止問題の次数である0 ′です。

• すべてのチューリング次数は可算無限であり、つまり、ちょうど$\displaystyle \aleph _{0}}$セット。
• がある${\displaystyle 2^{\aleph _{0}}}$異なるチューリング度。
• 各次数aに対して、厳密な不等式a < a ′が成り立つ。
• 各次数aに対して、 aより小さい次数の集合は可算である。a より大きい次数の集合のサイズは${\displaystyle 2^{\aleph _{0}}}$。

チューリング次数の構造については、数多くの研究が行われてきました。以下の概説では、既知の多くの研究結果のうち、ごく一部を紹介するにとどめます。これらの研究から導き出せる一般的な結論の一つは、チューリング次数の構造が極めて複雑であるということです。

次数が再帰的に列挙可能(re) または計算可能列挙可能(ce) と呼ばれるのは、それが再帰的に列挙可能な集合を含む場合である。すべての re 次数は0 ′より小さいが、 0 ′より小さいすべての次数が re であるとは限らない。ただし、集合は${\displaystyle A}$多対一が0 ′に還元可能であるのは、${\displaystyle A}$は再です。^{[ 3 ]}

• サックス（1964）：re 度は密である。任意の 2 つの re 度の間には、3 番目の re 度が存在する。
• ラクラン（1966a）とイェーツ（1966）：re次数には最大下限がない2つのre次数があります。
• ラクラン（1966a）とイェーツ（1966）：最大下限が0である非ゼロのre次数のペアが存在する。
• ラクラン（1966b）：最大下限が0で最小上限が0 ′であるようなre次数の組は存在しない。この結果は非公式に非ダイヤモンド定理と呼ばれている。
• Thomason (1971) : すべての有限分配束はre 次数に埋め込むことができます。実際、可算無原子ブール代数は、上限と下限を保存する方法で埋め込むことができます。
• Lachlan & Soare (1980) : すべての有限格子がre 次数に埋め込めるわけではありません (上限と下限を保存する埋め込みによって)。具体的な例を右に示します。
• LA HarringtonとTA Slaman ( Nies、Shore & Slaman (1998)を参照): 言語⟨ 0、≤、= ⟩における re 次数の一階理論は、真の一階算術の理論と多対一で同等である。

さらに、ショーエンフィールドの極限補題があり、集合Aは以下を満たす。${\displaystyle [A]\leq _{T}\emptyset '}$その特性関数に「再帰的近似」が存在する場合に限る。すなわち、十分大きなsに対して、${\displaystyle g(s)=\chi _{A}(s)}$[ ^{4 ]​}

集合Aは、関数の族が存在する場合にn -r eと呼ばれます。${\displaystyle (A_{s})_{s\in \mathbb {N} }}$したがって：^{[ 4 ]}

• A _sはAの再帰的近似です。あるtに対して、任意のs ≥ tに対してA _s ( x ) = A ( x )が成り立ち、特にAとその特性関数が混同されます。 （この条件を取り除くと、 A が「弱n -再帰的」であるという定義が得られます。）
• A _sは「n試行述語」です: すべてのxに対して、A ₀ ( x )=0 であり、${\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}$n ≤です。

n -re次数の性質: ^{[ 4 ]}

• n -re次数を持つ集合のクラスは、 ( n +1)-re次数を持つ集合のクラスの厳密な部分クラスである。
• すべてのn > 1に対して、 2 つの ( n + 1)-re 次数a、bが存在し、$\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }$セグメントが${\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}$n -re次数は含まれていません。
• ${\displaystyle A}$そして${\displaystyle {\overline {A}}}$両方の集合が弱n -reである場合に限り、( n +1)-re である。

エミール・ポストはreチューリング次数を研究し、 0と0 ′ の間に厳密に存在するre次数があるかどうかを問いかけた。このような次数を構成する（あるいは存在しないことを示す）問題は、ポスト問題として知られるようになった。この問題は1950年代にフリードバーグとムチニクによって独立に解決され、中間的なre次数が存在することが示された（フリードバーグ＝ムチニクの定理）。彼らの証明はそれぞれ、re次数を構成するための同じ新しい方法を開発し、それは優先法として知られるようになった。優先法は現在、re集合に関する結果を確立するための主要な手法となっている。

集合Xを構築するための優先順位法の考え方は、 X が満たさなければならない要件の可算シーケンスを列挙することです。たとえば、 0と0 ′の間の集合X を構築するには、各自然数eに対して要件A _eとB _eを満たすだけで十分です。ここで、A _eはインデックスeのオラクル マシンがXから0 ′ を計算しないことを要求し、B _eはインデックスeのチューリング マシン(オラクルなし) がXを計算しないことを要求します。これらの要件は優先順位付けされ、これは要件と自然数の明示的な全単射です。証明は各自然数に対して 1 つのステージで帰納的に進み、これらのステージは集合Xが列挙される時間のステップと考えることができます。各ステージでは、要件を満たすために(つまり、 X全体が列挙された後に強制的に成立させるために)、数値がXに追加されるか、または (損傷を受けない限り) 永久に X に追加されないようにすることができます。場合によっては、ある要件を満たすために数値をXに列挙することができますが、そうすると、以前に満たされていた要件が満たされなくなる（つまり、損なわれる）ことがあります。この場合、どの要件を満たすかを決定するために、要件の優先順位が使用されます。非公式な考え方としては、要件が損なわれた場合、より優先順位の高いすべての要件が損なわれなくなった後に、その要件も損なわれなくなるということですが、すべての優先順位の議論がこの性質を持つわけではありません。全体の集合Xが re であり、すべての要件を満たすという議論を行う必要があります。優先順位の議論は、 re 集合に関する多くの事実を証明するために使用できます。必要な結果を生み出すためには、使用する要件と、それらを満たす方法を慎重に選択する必要があります。

例えば、単純な（したがって計算不可能な）低X（低とはX ′=0′を意味する）は、次のように無限に多くの段階で構築できる。 段階nの開始時に、T _nを出力（バイナリ）テープとし、これまでに1を配置したセルインデックスの集合と同一視する（したがってX =∪n _T n _; T 0 ₌ ∅）。また、P _n ( m )_を位置mで1を出力しない優先度とする。P 0 ( m )=∞。 段階nで、可能であれば（そうでなければこの段階では何​​もしない）、∀ m P _n ( m )≠ iとなる最小のi < nを選択し、チューリングマシンiは、∀ m ∈ S \ T _n P _n ( m )≥ iとなる入力S ⊇ T _nで< nステップで停止する。任意の（有限の）Sを選択し、T _{n +1} = Sと設定し、マシンiがS上で訪問するすべてのセルmについて、P _{n +1} ( m ) = min( i , P _n ( m ))と設定し、優先度> iのすべてのセルを∞に設定し、次にSに含まれない優先度∞のセル（どれでも可）を優先度iに設定します。基本的に、優先度< iを乱さずにマシンiを停止できる場合は停止させ、マシン> iが停止を妨害しないように優先度を設定します。すべての優先度は最終的に一定になります。

Xが低いことを確認するには、マシンi がX で停止するのは、マシン i が、X で停止するマシン i 未満が n − i ステップ未満で停止するような T n 上で nステップ未満で停止する場合に限ります(再帰により、_これは0 ′から一様に計算可能です)。X は計算不可能です。そうでなければ、チューリング マシンがYで停止するのはY \ X が空でない場合のみとなり、 X は任意の大きなiに対して優先度i のセルを除外するため、構成に矛盾します。また、 Xは単純です。なぜなら、各iに対して優先度i のセルの数は有限だからです。

• マーティン測定