チューリング度

コンピュータサイエンスと数理論理学において、チューリング度（アラン・チューリングにちなんで名付けられた）または自然数の集合の解決不可能性の度合いは、集合のアルゴリズム的解決不可能性の程度を測定する。

概要

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

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

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

チューリング同値

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

二つの集合XとY は、 XがYにチューリング還元可能であり、かつYがXにチューリング還元可能であるとき、チューリング同値であると定義されます。X ≡ T Yという表記は、 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を含む同値類を表す。チューリング次数全体の集合は と表記される。 D{\displaystyle {\mathcal {D}}}

チューリング次数には半順序≤ が定義されており、[ X ] ≤ [ Y ] はX ≤ T Yの場合に限り成立する。すべての計算可能集合を含む唯一のチューリング次数が存在し、この次数は他のどの次数よりも小さい。これはposet の最小要素であるため、0 （ゼロ）と表記される。（チューリング次数を集合と区別するために、太字表記が一般的である。[ X ]のように混乱が生じない場合は、太字表記は不要である。） D{\displaystyle {\mathcal {D}}}

任意の集合XとYについて、集合X join Y （ X ⊕ Yと表記）は、集合{2 n  : n ∈ X } と {2 m +1 : m ∈ Y } の和集合として定義されます。 X ⊕ Yのチューリング次数は、 XとYの次数の最小上限です。したがって、はjoin-semilatticeです。次数aとbの最小上限はa ∪ bと表されます。最大の下限を持たない次数のペアが存在するため、 はlatticeではないことが分かっています。D{\displaystyle {\mathcal {D}}}D{\displaystyle {\mathcal {D}}}

任意の集合Xについて、 X ′という表記は、 Xをオラクルとして用いる際に（インデックスを入力として与えられた場合に）停止するオラクルマシンのインデックスの集合を表す。集合X ′ はXのチューリングジャンプと呼ばれる。次数 [ X ] のチューリングジャンプは次数 [ X ′] と定義される。これは有効な定義である。なぜなら、X ≡ T Yであれば常にX ′ ≡ T Y ′となるからである。重要な例として、停止問題の次数である0 ′ が挙げられる。

チューリング度の基本的性質

  • すべてのチューリング次数は可算無限です。つまり、正確に個の集合が含まれます。ℵ0{\displaystyle \aleph_{0}}
  • 異なるチューリング度が存在します。2ℵ0{\displaystyle 2^{\aleph _{0}}}
  • 各次数aに対して、厳密な不等式a < a ′ が成立します。
  • 各次数aについて、 aより小さい次数の集合は個可算である。 aより大きい次数の集合の大きさは 個である。2ℵ0{\displaystyle 2^{\aleph _{0}}}

チューリング度合いの構造

チューリング次数の構造については、多くの研究が行われてきました。以下の調査は、多くの既知の結果のうちほんの一部を列挙したものです。これらの研究から導き出される一般的な結論の一つは、チューリング次数の構造が非常に複雑であるということです。

注文プロパティ

  • 最小次数が存在する。次数aが最小であるとは、a が0でなく、かつ0とaの間に次数がないことを意味する。したがって、次数に関する順序関係は稠密順序ではない。
  • チューリング次数は≤Tによって線形順序付けられない。[ 1 ]
  • 実際、あらゆる非ゼロの次数aに対して、 aと比較できない次数bが存在します。
  • 比較できないチューリング次数が一組存在します。2ℵ0{\displaystyle 2^{\aleph _{0}}}
  • 最大の下限を持たない次数のペアが存在する。したがって、は格子ではない。D{\displaystyle {\mathcal {D}}}
  • すべての可算な半順序集合はチューリング次数に埋め込むことができます。
  • チューリング次数の無限厳密に増加するシーケンスa 1、a 2、 ... には最小上限を持つことはできませんが、常にچ e ( e < c ∧ e < d ⇔ ∃ i e ≤ a i )となる正確なペアc、dが存在します(したがって、上限があります)。
  • 構成可能性公理を仮定すると、順序型の最大次数連鎖が存在することが示される。[ 2 ]ω1{\displaystyle \omega _{1}}

ジャンプに関する特性

  • あらゆる次数aに対し、 aとa ′の間に厳密に一致する次数が存在します。実際、aとa ′ の間には、互いに比較できない次数の族が可算無限個存在します。
  • ジャンプ反転: 次数aが形式b ′ となるのは、 0 ′ ≤ aの場合のみです。
  • 任意の次数aに対して、 a < bかつb ′ = a ′となる次数bが存在します。このような次数bはaに対して低いと呼ばれます。
  • 各iに対してa ′ i +1 ≤ a iとなるような無限次数列a iが存在する。
  • ポストの定理は、算術階層と空集合の有限反復チューリングジャンプとの間に密接な対応関係を確立します。

論理プロパティ

再帰的に列挙可能なチューリング次数

re 次数に埋め込むことができない有限格子。

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

さらに、ショーンフィールドの極限補題があり、集合Aがを満たすのは、その特性関数の「再帰近似」が存在する場合のみである。つまり、十分に大きいsに対して、となる関数gが存在する場合である。[ 4 ][あ]≤T∅′{\displaystyle [A]\leq _{T}\emptyset '}グラム（s）＝χあ（s）{\displaystyle g(s)=\chi _{A}(s)}

集合Aがn -r e.であるとは、次のような関数の族が存在するときである。 [ 4 ]（あs）s∈北{\displaystyle (A_{s})_{s\in \mathbb {N} }}

  • A sはAの再帰近似である。あるtに対して、任意のs ≥ tに対して、 A s ( x ) = A ( x )が成り立ち、特にAとその特性関数を融合する。 （この条件を取り除くと、 A は 「弱n -re」であると定義される。）
  • A sは「n試行述語」です。つまり、すべてのxに対して、A 0 ( x )=0 であり、の濃度はn ≤ です。{s∣あs（×）≠あs+1（×）}{\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}

n -re度の特性: [ 4 ]

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

ポストの問題と優先法

エミール・ポストは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がすべて列挙されたら、それらの数字が保持されるように強制する）。場合によっては、1 つの要件を満たすために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が、 ∀ m ∈ S \ T n P n ( m ) ≥ iである入力S ⊇ T nに対して< nステップで停止するような最小のi < nを選択します。そのような（有限の） S を任意に選び、T n +1 = Sとし、マシンiがS上で訪問するすべてのセルmについて、P n +1 ( m ) = min( i , P n ( m )) とし、すべての優先度 > i を∞に設定し、 Sにない優先度 ∞ のセル 1 つ（どれでも可）を優先度iに設定します。基本的に、優先度 < i を崩さずにマシンi を停止させ、その後、マシン > i が停止を妨げないように優先度を設定します。つまり、すべての優先度は最終的に一定になります。

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

参照

参考文献

モノグラフ（学部レベル）

モノグラフと調査論文（大学院レベル）

研究論文

注記

「 https://en.wikipedia.org/w/index.php?title=Turing_degree&oldid=1334591509#Post's_problem_and_the_priority_method」より取得