チューリング度

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

概要

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

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

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

チューリング等価性

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

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

X ≡ _TX
X ≡ _TYならばY ≡ _TXが成り立つ
X ≡ _TYかつY ≡ _TZならばX ≡ _TZである。

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

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

任意の集合XとYに対して、集合XとYの結合X ⊕ Yは、集合{2 n : n ∈ X } と {2 m +1 : m ∈ Y } の和集合として定義される。X ⊕ Yのチューリング次数は、XとYの次数の最小上界である。したがって ${\mathcal {D}}$ は結合半束である。次数aとbの最小上限はa ∪ bで表される。 ${\mathcal {D}}$ is not a lattice, as there are pairs of degrees with no greatest lower bound.

For any set X the notation X′ denotes the set of indices of oracle machines that halt (when given their index as input) when using X as an oracle. The set X′ is called the Turing jump of X. The Turing jump of a degree [X] is defined to be the degree [X′]; this is a valid definition because X′≡_TY′ whenever X≡_TY. A key example is 0′, the degree of the halting problem.

Basic properties of the Turing degrees

Every Turing degree is countably infinite, that is, it contains exactly $\displaystyle \aleph _{0}}$ sets.
There are $2^{\aleph _{0}}$ distinct Turing degrees.
For each degree a the strict inequality a < a′ holds.
For each degree a, the set of degrees below a is countable. The set of degrees greater than a has size $2^{\aleph _{0}}$ .

Structure of the Turing degrees

A great deal of research has been conducted into the structure of the Turing degrees. The following survey lists only some of the many known results. One general conclusion that can be drawn from the research is that the structure of the Turing degrees is extremely complicated.

Order properties

There are minimal degrees. A degree a is minimal if a is nonzero and there is no degree between 0 and a. Thus the order relation on the degrees is not a dense order.
The Turing degrees are not linearly ordered by ≤_T.^[1]
In fact, for every nonzero degree a there is a degree b incomparable with a.
There is a set of $2^{\aleph _{0}}$ pairwise incomparable Turing degrees.
There are pairs of degrees with no greatest lower bound. Thus ${\mathcal {D}}$ is not a lattice.
Every countable partially ordered set can be embedded in the Turing degrees.
チューリング次数が無限に増加する数列a ₁ , a ₂ , ... は最小上界を持つことはできませんが、常に $\forall$ $e$ $($ $e$ $<$ $c$ $\land$ $e$ $<$ $d$ $\Leftrightarrow \exists$ $i$ $e$ $\leq$ $a$ $i$ $)$ となるような正確なペアc , dが存在します(したがって、上界を持ちます)。
構成可能性の公理を仮定すると、順序型の次数の最大連鎖が存在することが示される。 $\displaystyle \omega _{1}}$ [ ²^]

ジャンプに関連する特性

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

論理特性

シンプソン（1977b ）は、 ${\mathcal {D}}$ 言語⟨ ≤ , = ⟩または⟨ ≤ , ′ , = ⟩は、真の二階算術の理論と多対一で等価である。これは、構造が ${\mathcal {D}}$ 非常に複雑です。
Shore & Slaman (1999)は、ジャンプ演算子が一次構造で定義可能であることを示した。 ${\mathcal {D}}$ 言語⟨ ≤ , = ⟩を使用します。

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

次数が再帰的に列挙可能(re) または計算可能列挙可能(ce) と呼ばれるのは、それが再帰的に列挙可能な集合を含む場合である。すべての re 次数は0 ′より小さいが、 0 ′より小さいすべての次数が re であるとは限らない。ただし、集合は $A$ 多対一が0 ′に還元可能であるのは、 $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は以下を満たす。 $[A]\leq _{T}\emptyset '$ その特性関数に「再帰的近似」が存在する場合に限る。すなわち、十分大きなsに対して、 $g(s)=\chi _{A}(s)$ [ ⁴^]

集合Aは、関数の族が存在する場合にn -r eと呼ばれます。 $(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 であり、 $\{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} }$ セグメントが $\{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}$ n -re次数は含まれていません。
$A$ そして ${\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 =\cupn T n; T 0 = \emptyset）$ 。また、P _n ( m ) $を$ 位置mで1を出力しない優先度とする。P $0 (m)=\infty$ 。段階nで、可能であれば（そうでなければこの段階では何もしない）、 $\forall$ $m$ $P$ $n$ $($ $m$ $)\neq$ $i$ となる最小のi < nを選択し、チューリングマシンiは、 $\forall$ $m$ $\in$ $S$ $\$ $T$ $n$ $P$ $n$ $($ $m$ $)\geq$ $i$ となる入力 $S$ $\supseteq$ $T$ $n$ で< nステップで停止する。任意の（有限の）Sを選択し、T _n₊₁ = Sと設定し、マシンiがS上で訪問するすべてのセルmについて、P _n₊₁ ( 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 のセルの数は有限だからです。

参考文献

専門書（学部レベル）

クーパー、SB（2004）。計算可能性理論。フロリダ州ボカラトン：チャップマン＆ホール/CRC。424ページ。ISBN 1-58488-237-9。
カットランド、ナイジェル・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 未満の集合の階層と次数. Lecture Notes in Mathematics. Vol. 859. Springer-Verlag.
ラーマン、M. (1983).解けない度合い。数理論理学の展望。ベルリン：シュプリンガー・フェルラーク。ISBN 3-540-12155-2。
オディフレッディ、ピエルジョルジオ（1989）。古典的再帰理論。論理学と数学の基礎に関する研究。第 125巻。アムステルダム：ノースホランド。ISBN 978-0-444-87295-1MR 0982269 .
オディフレッディ、ピエルジョルジオ（1999）。古典的再帰理論。第II巻。論理学と数学の基礎に関する研究。第 143巻。アムステルダム：ノースホランド。ISBN 978-0-444-50205-6. MR 1718169 .
ロジャース、ハートリー（1967）。再帰関数と有効計算可能性の理論。マサチューセッツ州ケンブリッジ：MIT Press。ISBN 9780262680523. OCLC 933975989 . 2020年5月6日取得.
サックス、GE（1966）。「解けない問題の度合い」。数学研究年報。プリンストン大学出版局。ISBN 978-0-6910-7941-7. JSTOR j.ctt1b9x0r8 .
シンプソン、スティーブン・G. (1977a). 「解けない問題の度合い：結果の概観」. Annals of Mathematics Studies . Studies in Logic and the Foundations of Mathematics. 90. Elsevier : 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 部 (バイアブランカ、1992 年)』。Notas Lógica Mat. Vol. 38. pp. 61–70 .
ソアレ、ロバート・アーヴィング（1987）。再帰的に列挙可能な集合と次数：計算可能な関数と計算可能な生成集合の研究。数理論理学の展望。ベルリン：シュプリンガー・フェルラーク。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日取得。
Kleene, Stephen Cole ; Post, Emil L. (1954)、「再帰的非可解性の次数の上半格子」、Annals of Mathematics、第2シリーズ、59 (3): 379–407、doi : 10.2307/1969708、ISSN 0003-486X、JSTOR 1969708、MR 0061078
Lachlan, Alistair H. (1966a)、「再帰的に列挙可能な次数のペアの下限」、Proceedings of the London Mathematical Society、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。
Lachlan, Alistair H.; Soare, Robert Irving (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
Post, Emil L. (1944)、「正の整数の再帰的に列挙可能な集合とその決定問題」、Bulletin of the American Mathematical Society、50 (5): 284–316、doi : 10.1090/S0002-9904-1944-08111-1、ISSN 0002-9904、MR 0010514
Sacks, GE (1964)、「再帰的に列挙可能な次数は稠密である」、Annals of Mathematics、第2シリーズ、80 (2): 300–312、doi : 10.2307/1970393、JSTOR 1970393
Shore, Richard A. ; Slaman, Theodore A. (1999)、「チューリングジャンプの定義」、Mathematical Research Letters、6 (6): 711–722、doi : 10.4310/mrl.1999.v6.n6.a10、ISSN 1073-2780、MR 1739227
Simpson, Stephen G. (1977b). 「再帰的不確定性の次数に関する一階理論」. Annals of Mathematics . Second Series. 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
Yates, CEM (1966)、「再帰的に列挙可能な次数の最小ペア」、Journal of Symbolic Logic、31 (2): 159–168、doi : 10.2307/2269807、JSTOR 2269807、S2CID 38778059

[FOOTNOTEDeAntonio20109-1] DeAntonio 2010、p. 9。

[FOOTNOTEChongYu20071224-2] Chong & Yu 2007、p. 1224。

[FOOTNOTEOdifreddi1989252,_258-3] オディフレディ 1989 年、p. 252、258。

[FOOTNOTEEpsteinHaasKramer1981-4] 1 2 3エプスタイン、ハース、クレイマー 1981 年。

[1]

2

[ 3 ]

4