チューリング度

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

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

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 ≡ _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を含む同値類を表します。チューリング次数の全体の集合は と表記されます。 ${\displaystyle {\mathcal {D}}}$

チューリング次数には半順序≤ が定義されており、 X ≤ _T Yの場合にのみ[ X ] ≤ [ Y ] となります。すべての計算可能な集合を含む唯一のチューリング次数があり、この次数は他のどの次数よりも小さくなります。これはposet の最小要素であるため、0 (ゼロ) と表記されます。(チューリング次数を集合と区別するために、太字表記を使用するのが一般的です。[ X ]のように混乱が生じない場合は、太字は不要です。) ${\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で表されます。最大の下限を持たない次数のペアが存在するため、は格子で はないことがわかっています。${\displaystyle {\mathcal {D}}}$${\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}}}$

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

• 最小次数が存在します。次数aが最小となるのは、 aが 0 以外で、 0とa の間に次数が存在しないときです。したがって、次数に関する順序関係は稠密な順序ではありません。
• チューリング次数は≤Tによって線形順序付けられるわけではない_。 [ ^1]
• 実際、ゼロ以外のあらゆる次数aに対して、 aと比較できない次数bが存在します。
• 比較できないチューリング次数のペアが存在します。${\displaystyle 2^{\aleph _{0}}}$
• 最大の下限を持たない次数のペアが存在します。したがって、は格子ではありません。${\displaystyle {\mathcal {D}}}$
• すべての可算な半順序集合はチューリング次数に埋め込むことができます。
• チューリング次数の無限の厳密に増加するシーケンスa ₁、a ₂、... は最小の上限を持つことはできませんが、∀ e ( e < c ∧ e < d ≡ ∃ i e ≤ a _i ) となる正確なペア c、dが常に存在するため、(一意ではない) 最小の上限を持ちます。
• 構成可能性公理を仮定すると、順序型の最大次数連鎖が存在することが示される。^[2]${\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が存在する。
• ポストの定理は、算術階層と空集合の有限反復チューリングジャンプとの間に密接な対応関係を確立します。

• シンプソン（1977b）は、言語⟨ ≤, = ⟩または⟨ ≤, ′, = ⟩におけるの1階理論は、真の2階算術の理論と多対一同値であることを示した。これは、の構造が極めて複雑であることを示す。${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {D}}}$
• Shore & Slaman (1999)は、ジャンプ演算子が言語⟨≤, =⟩の1階構造で定義可能であることを示した。${\displaystyle {\mathcal {D}}}$

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

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

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

集合Aがn -r e.と呼ばれるのは、次のような関数の族が存在するときである: ^[4]${\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 ₀ ( x )=0 であり、の濃度は≤n です。${\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 次数は含まれません。${\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }$${\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}$
• ${\displaystyle A}$およびは( n +1)-reであり、両方の集合が弱n -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 がすべて列挙されたら、それらが保持されるように強制します)。場合によっては、 Xに数値を列挙して1 つの要件を満たすことができますが、これを行うと、以前に満たされていた要件が満たされなくなる (つまり、損傷する) ことになります。この場合、どの要件を満たすかを決定するために、要件の優先順位が使用されます。非公式な考え方では、要件が損傷している場合は、より優先度の高いすべての要件が損傷しなくなった後に、最終的にその要件も損傷しなくなりますが、すべての優先順位の議論がこの特性を持っているわけではありません。全体のセットXが re であり、すべての要件を満たすという議論を行う必要があります。優先順位の議論を使用して、re セットに関する多くの事実を証明することができます。必要な結果を生成するには、使用する要件とそれらを満たす方法を慎重に選択する必要があります。

たとえば、単純な(したがって計算不可能な)低い X (低いとはX ′=0′ を意味する) は、次のように無限の段階で構築できます。ステージnの開始時に、T _{n を}出力 (バイナリ) テープとし、これまでに 1 を配置したセル インデックスのセットで識別します (つまり、X =∪ _n T _n ; T ₀ =∅)。また、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で停止するのは、iより小さいマシンがXで停止するのはnステップ未満であるようなT _nで停止する場合のみです(再帰により、これは 0′ から一様に計算可能です) 。Xは計算不可能です。なぜなら、そうでなければチューリング マシンはYで停止するのはY \ Xが空でない場合のみだからです。これは、 X が任意の大きさのiに対して優先度i のセルの一部を除外するため、構成と矛盾します。また、各iに対して優先度i のセルの数は有限であるため、 X は単純です。

• マーティンメジャー

• クーパー、SB (2004)。計算可能性理論。フロリダ州ボカラトン：チャップマン＆ホール/CRC。p. 424。ISBN 1-58488-237-9。
• Cutland, Nigel J. (1980)。計算可能性、再帰関数理論入門。ケンブリッジ-ニューヨーク:ケンブリッジ大学出版局。p. 251。ISBN 0-521-22384-9。; ISBN 0-521-29465-7 

• アンボス・スピーズ、クラウス、フェイエル、ピーター（2006年3月20日）。「解決不可能性の度合い」（PDF） 。 2023年8月20日閲覧。未発表
• Epstein, RL; Haas, R; Kramer, LR (1981)。Leman, M; Schmerl, J.; Soare, R. (編)。集合の階層と 0 未満の次数。数学講義ノート。第 859 巻。Springer-Verlag。
• レルマン、M. (1983)。解決不可能性の度合い。数理論理学の展望。ベルリン：シュプリンガー出版社。ISBN 3-540-12155-2。
• オディフレッディ、ピエールジョルジオ(1989)。古典的再帰理論。論理学と数学の基礎研究。第 125 巻。アムステルダム: 北ホラント。ISBN 978-0-444-87295-1. MR  0982269。
• オディフレッディ、ピエールジョルジオ(1999)。古典的再帰理論。第 II 巻。論理学と数学の基礎研究。第 143 巻。アムステルダム: 北ホラント。ISBN 978-0-444-50205-6. MR  1718169。
• ロジャース、ハートリー(1967)。再帰関数と実効計算可能性の理論。マサチューセッツ州ケンブリッジ：MIT プレス。ISBN 9780262680523. OCLC  933975989 . 2020年5月6日閲覧。
• サックス、GE (1966)。「解けない度合い」。数学研究年報。プリンストン大学出版局。ISBN 978-0-6910-7941-7. JSTOR  j.ctt1b9x0r8.
• シンプソン、スティーブン G. (1977a)。「解けない度合い: 結果の調査」。数学研究年報。論理学と数学の基礎の研究。90 。エルゼビア: 631–652。doi :10.1016/S0049-237X(08) 71117-0。ISBN 9780444863881。
• ショーンフィールド、ジョセフ R. (1971)。解決不可能性の度合い。ノースホランド/エルゼビア。ISBN 978-0-7204-2061-6。
• Shore, R. (1993)。「T、tt、wtt re 度の理論: 決定不能性とそれ以降」。Univ. Nac. del Sur、Bahía Blanca (編)。第 9 回ラテンアメリカ数理論理シンポジウム議事録、第 1 部 (Bahía Blanca、1992)。Notas Lógica Mat。第 38 巻。pp. 61–70。
• Soare, Robert Irving (1987)。「再帰的に列挙可能な集合と次数: 計算可能な関数と計算可能に生成された集合の研究」。数理論理学の展望。ベルリン: Springer-Verlag。ISBN 3-540-15299-7。
• Soare, Robert Irving (1978)。「再帰的に列挙可能な集合と次数」。Bull . Amer. Math. Soc . 84 (6): 1149–1181. doi : 10.1090/S0002-9904-1978-14552-2 . MR  0508451. S2CID  29549997.

• Chong ,  CT ; Yu, Liang (2007 年 12 月)。「チューリング次数における最大連鎖」。Journal of Symbolic Logic。72 ( 4): 1219–1227。doi :10.2178/ jsl /1203350783。JSTOR 27588601。S2CID 38576214  。
• DeAntonio, Jasper (2010 年 9 月 24 日). 「チューリング次数とその線形順序の欠如」(PDF) 。2023 年8 月 20 日閲覧。
• クリーネ、スティーブン・コール、ポスト、エミル・L. (1954)、「再帰的不解性の度合いの上限半格子」、数学年報、第 2 シリーズ、59 (3): 379–407、doi :10.2307/1969708、ISSN  0003-486X、JSTOR  1969708、MR  0061078
• Lachlan, Alistair H. (1966a)、「再帰的に列挙可能な次数のペアの下限値」、ロンドン数学会紀要、3 (1): 537–569、CiteSeerX  10.1.1.106.7893、doi :10.1112/plms/s3-16.1.537。
• Lachlan, Alistair H. (1966b)、「再帰的に列挙可能な次数の相対補数を見つけることの不可能性」、J. Symb. Log.、31 (3): 434–454、doi :10.2307/2270459、JSTOR  2270459、S2CID  30992462。
• ラクラン、アリスター H.;ソアレ、ロバート アーヴィング(1980)、「すべての有限格子が再帰的に列挙可能な次数に埋め込まれるわけではない」、Advances in Mathematics、37 : 78–82、doi : 10.1016/0001-8708(80)90027-4
• Nies, André; Shore, Richard A.; Slaman, Theodore A. (1998)、「再帰的に列挙可能な次数における解釈可能性と定義可能性」、Proceedings of the London Mathematical Society、77 (2): 241–291、CiteSeerX  10.1.1.29.9588、doi :10.1112/S002461159800046X、ISSN  0024-6115、MR  1635141、S2CID  16488410
• ポスト、エミール L. (1944)、「正の整数の再帰的に列挙可能な集合とその決定問題」、アメリカ数学会誌、50 (5): 284–316、doi : 10.1090/S0002-9904-1944-08111-1、ISSN  0002-9904、MR  0010514
• サックス、GE (1964)、「再帰的に列挙可能な次数は稠密である」、数学年報、第 2 シリーズ、80 (2): 300–312、doi :10.2307/1970393、JSTOR  1970393
• ショア、リチャード A. ;スラマン、セオドア A. (1999)、「チューリングジャンプの定義」、数学研究レター、6 (6): 711–722、doi : 10.4310/mrl.1999.v6.n6.a10、ISSN  1073-2780、MR  1739227
• シンプソン、スティーブン G. (1977b) 。「再帰的不解の次数の第一階理論」。数学年報。第 2 シリーズ。105 (1): 121–139。doi : 10.2307 /1971028。ISSN 0003-486X。JSTOR  1971028。MR  0432435  。
• Thomason, SK (1971)、「再帰的に列挙可能な次数のサブラティス」、Z. Math. Logik Grundlag. Math.、17 : 273–280、doi :10.1002/malq.19710170131
• イェーツ、CEM (1966)、「再帰的に列挙可能な次数の最小ペア」、Journal of Symbolic Logic、31 (2): 159–168、doi :10.2307/2269807、JSTOR  2269807、S2CID  38778059