チューリング次数

チューリング次数（～じすう、英: Turing degree, degree of unsolvability）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。

任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。更に、チューリング次数は半順序を成すので、集合 ${\displaystyle X}$ のチューリング次数が集合 ${\displaystyle Y}$ のチューリング次数よりも小さいならば、ある数が ${\displaystyle Y}$ に含まれるかを正しく判定するあらゆる（計算不可能なものも含む）手続きは、ある数が ${\displaystyle X}$ に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。

チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。

チューリング同値

詳細は「チューリング還元」を参照

この記事では以後「集合」と言えば「自然数の集合」を指すこととする。ある数が集合 ${\displaystyle X}$  の元かどうかを、オラクル集合 ${\displaystyle Y}$  を持つ神託機械を用いて決定できるとき、${\displaystyle X}$  は ${\displaystyle Y}$  にチューリング還元可能であると言い、${\displaystyle X\leq _{T}Y}$  と書く。

二つの集合 ${\displaystyle X}$  と ${\displaystyle Y}$  について、${\displaystyle X}$  が ${\displaystyle Y}$  にチューリング還元可能であり、かつ、 ${\displaystyle Y}$  が ${\displaystyle X}$  にチューリング還元可能であるとき、これらの集合は チューリング同値 であると言い、${\displaystyle X\equiv _{T}Y}$  と書く。${\displaystyle \equiv _{T}}$  という関係は同値関係と捉えることができる。すなわち任意の集合 ${\displaystyle X}$ 、${\displaystyle Y}$ 、${\displaystyle Z}$  について

• ${\displaystyle X\equiv _{T}X}$ 
• ${\displaystyle X\equiv _{T}Y}$  ならば ${\displaystyle Y\equiv _{T}X}$ 
• もし ${\displaystyle X\equiv _{T}Y}$  かつ ${\displaystyle Y\equiv _{T}Z}$  ならば、${\displaystyle X\equiv _{T}Z}$ 。

チューリング次数

チューリング次数は関係 ${\displaystyle \equiv _{T}}$  の同値類である。${\displaystyle [X]}$  と書いて集合 ${\displaystyle X}$  を含むような同値類を表す。 チューリング次数全体を表す記号として ${\displaystyle {\mathcal {D}}}$  と書く。

チューリング次数は半順序 ${\displaystyle \leq }$ を持つ。定義として、${\displaystyle [X]\leq [Y]}$  である必要十分条件は ${\displaystyle X\leq _{T}Y}$ である。(計算可能集合)を全て含む特別なチューリング次数が存在し、この次数は他の如何なる次数よりも小さい。この次数は半順序集合 ${\displaystyle {\mathcal {D}}}$  の最小元なので、0（ゼロ）と書く。（チューリング次数を表記する際は、集合と混同しないように太字 (boldface) で書くのが普通である。混同する恐れが無いなら（例えば ${\displaystyle [X]}$  ）太字にせずとも良い。）

任意の集合 ${\displaystyle X}$  と ${\displaystyle Y}$  について、${\displaystyle X}$  と ${\displaystyle Y}$  の結び（ ${\displaystyle X\oplus Y}$  と書く）を、集合 ${\displaystyle {2n:n\in X}}$ と${\displaystyle {2m+1:m\in Y}}$ の和集合として定義できる。 ${\displaystyle X\oplus Y}$  のチューリング次数は ${\displaystyle X}$  と ${\displaystyle Y}$  の次数の上限である。従って ${\displaystyle {\mathcal {D}}}$  は結びを持つ半束である。 次数 a と b の上限を a ∪ b と書く。下限を持たない次数の対が存在するので、${\displaystyle {\mathcal {D}}}$  は束ではないことが知られている。

集合 ${\displaystyle X}$  について、${\displaystyle X}$  をオラクルに持つときに停止する神託機械を指すインデクスの集合を ${\displaystyle X'}$  と書く。集合${\displaystyle X'}$ は${\displaystyle X}$ のチューリングジャンプと呼ばれる。次数 ${\displaystyle [X]}$  のチューリングジャンプは次数 ${\displaystyle [X']}$  であると定義される。これは${\displaystyle X\equiv _{T}Y}$  であれば必ず ${\displaystyle X'\equiv _{T}Y'}$  ことからも妥当な定義である。一つの重要な例として 0′があるが、これは停止問題の次数である。

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

• 個々のチューリング次数は可算無限である。すなわち、一つの次数には丁度 ${\displaystyle \aleph _{0}}$  個の集合が対応する。

• 互いに相異なるチューリング次数は ${\displaystyle 2^{\aleph _{0}}}$  個存在する。

• 各次数 a について、不等式 a < a′ が厳密に成り立つ。

• 各次数 a について、a よりも小さい次数の集合の濃度はたかだか可算。a よりも大きい次数の集合の濃度は ${\displaystyle 2^{\aleph _{0}}}$ 。

チューリング次数の構造

チューリング次数の構造については大変多くの研究がある。以下に示す一覧は、知られている結果のごく一部を示すに過ぎない。一連の研究から得られた一つの一般的な結論は、チューリング次数の構造が極端に複雑だということである。

順序性

• 極小次数が存在する。 次数 a が「極小」であるとは、a が 0 でなく、かつ、次数 0 と a の間に他の次数が存在しないことである。従って次数の順序関係は稠密順序ではない。
• 0 でない全ての次数 a について、a とは比較不可能な次数 b が存在する。
• 互いに比較不可能なチューリング次数の対は ${\displaystyle 2^{\aleph _{0}}}$  通りある。
• 次数の対で(下限)を持たないものが存在する。従って ${\displaystyle {\mathcal {D}}}$  は束ではない。
• 全ての可算な半順序集合は、チューリング次数に埋め込める。
• チューリング次数の狭義単調増加する無限列は、(上限)を持たない。

ジャンプに関する性質

• 全ての次数 a について、a と a′の厳密に中間に位置する次数が存在する。実際に、a と a′の間にある互いに比較不可能な次数の対は可算個存在する。
• ある次数 a が b′と書ける必要十分条件は、0′≤ a。
• 如何なる次数 a についても、次数 b が存在して、a < b かつ b′= a′を満たす。このような次数 b を a から相対的に「低い」と呼ぶ。
• 全ての i について、${\displaystyle \mathbf {a} '_{i+1}\leq \mathbf {a} _{i}}$  を満たすような次数の無限列 a_i が存在する。

論理的性質

• (Simpson, 1977) ${\displaystyle {\mathcal {D}}}$  の言語{${\displaystyle \left\langle \leq ,=\right\rangle }$ } または {${\displaystyle \left\langle \leq ,',=\right\rangle }$ } を用いた一階理論は真の二階算術に多対一同値。これは ${\displaystyle {\mathcal {D}}}$  の構造が極端に複雑であることを示している。
• (Shore and Slaman, 1999) ジャンプ作用素は次数の一階構造の中で言語 ${\displaystyle \left\langle \leq ,=\right\rangle }$  を用いて定義可能。

r.e.チューリング次数の構造

帰納的可算集合を持つ次数は r.e.（recursively enumerable 帰納的可算）または c.e.（computably enumerable 計算可枚挙） と呼ばれる。全ての r.e.次数は 0′よりも小さいか等しい。しかしながら 0′よりも小さい全ての次数が r.e.次数という訳ではない。

• (G. E. Sacks, 1964) r.e.次数は稠密。任意の二つのr.e.次数の間には、必ず別のr.e.次数がある。
• (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) r.e.次数の中には下限を持たないような、r.e.次数の対が存在する。
• (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) 下限が 0 であるような 0 でないr.e.次数の対が一つ存在する。
• (S. K. Thomason, 1971) 全ての有限な分配束はr.e.次数に埋め込める。実際に、可算で atomless なブール束を上限と下限を保つように埋め込むことが出来る。
• (A. H. Lachlan and R. I. Soare, 1980) （上限と下限を保つように）r.e.次数に埋め込めないような、有限な束が存在する。特に次の束は r.e.次数に埋め込めない。

 

• (A. H. Lachlan, 1966b) r.e.次数の対で、下限が0かつ上限が 0′であるものは存在しない。この結果は非公式に「ノンダイアモンド定理」と呼ばれている。
• (L. A. Harrington and T. A. Slaman, see Nies, Shore, and Slaman (1998))言語${\displaystyle \left\langle 0,\leq ,=\right\rangle }$  を用いて書かれたr.e.次数の一階理論は真である一階算術と多対一同値。

ポストの問題と優先度法

エミール・ポストは r.e.チューリング次数を研究し、0 と 0′の厳密に中間であるような r.e.次数は存在するか、と問うた。このような次数を構成する問題（または、それが不可能であることの証明）はポストの問題として知られるようになった。この問題は1950年代に Friedberg と Muchnik によって独立に解決され、そのような中間の r.e.次数が実在することが示された。彼らの証明方法は、r.e.次数を構成するための同じ新技法をそれぞれが導入したもので、これは優先度法として知られるようになった。今日、優先度法は r.e.集合について何らかの結果を得る際には主役となるテクニックである。

r.e.集合 ${\displaystyle X}$  を構成する上で、優先度法のアイディアは、${\displaystyle X}$  が満たさねばならない可算個の「要件」の列を作るというものである。 例えば、0 と 0′の中間である r.e.集合を作るには、全ての自然数 ${\displaystyle e}$  について要件 ${\displaystyle A_{e}}$  と ${\displaystyle B_{e}}$  を満たせば十分である。ここで、${\displaystyle A_{e}}$  はインデクス ${\displaystyle e}$  が指す神託機械が ${\displaystyle X}$  から 0′ を計算できないという要件であり、${\displaystyle B_{e}}$  はインデクス ${\displaystyle e}$  が指す（オラクルを持たない）チューリングマシンが ${\displaystyle X}$  を計算できないという要件である。 これらの要件は「優先順序」（要件と自然数との間の明示的な全単射）に従って並べられる。 証明は個々の自然数毎に一つずつの「段階」を踏んで帰納法的に進む。ここでいう段階とは、${\displaystyle X}$  の内容を枚挙する過程だと思えばよい。 個々の段階では、何らかの数を ${\displaystyle X}$  に加えるか、又は ${\displaystyle X}$  に加えることを恒久的に禁止して、「要件」を満足させていく（つまり ${\displaystyle X}$  の全てが枚挙されたなら全ての要件が成り立つように強いる）。 時として、ある数を ${\displaystyle X}$  に加えると、一つの要件が満たされる代わりにそれまで満たされていた別の要件が満たされなくなる（「傷付けられる」と言う）ことが起きる。 この場合は要件の優先順序を用いてどの要件を満たすべきかを決定する。 大まかなアイディアとしては、もし何らかの要件が傷付けられるなら、それより優先度が高い他の要件が何れ全て傷付けられなくなれば、最終的には傷付けられなくなるだろう、ということである。とはいえ全ての優先度論法がこのような性質を持つ訳ではない。 出来上がった集合 ${\displaystyle X}$  が r.e.であり全ての要件を満たすことを論証する必要がある。 優先度論法は r.e.集合に関する様々な証明に使える。所期の集合を生成するには、要件とその満たし方を注意深く選ばねばならない。

参考文献

入門書

• Cooper, S.B. Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004. (ISBN 1-58488-237-9)
• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. (ISBN 0-521-22384-9); (ISBN 0-521-29465-7)

専門書など

• Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Lerman, M. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. (ISBN 3-540-12155-2)
• Odifreddi, P. G. (1989), Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, 125, Amsterdam: North-Holland, ISBN (978-0-444-87295-1), MR982269 
• Odifreddi, P. G. (1999), Classical recursion theory. Vol. II, Studies in Logic and the Foundations of Mathematics, 143, Amsterdam: North-Holland, ISBN (978-0-444-50205-6), MR1718169 
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. (ISBN 0-262-68052-1); (ISBN 0-07-053522-1)
• Simpson, S. Degrees of unsolvability: a survey of results. Handbook of Mathematical Logic, North-Holland, 1977, pp. 631--652.
• Shore, R. The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond. Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahia Blanca, 1992), 61--70, Notas Logica Mat., 38, Univ. Nac. del Sur, Bahia Blanca, 1993.
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. (ISBN 3-540-15299-7)
• Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149--1181.

研究論文

• Kleene, Stephen Cole; Post, Emil L. (1954), “The upper semi-lattice of degrees of recursive unsolvability”, Annals of Mathematics. Second Series 59: 379?407, ISSN 0003-486X, MR0061078 
• Lachlan, A.H. (1966a). “Lower Bounds for Pairs of Recursively Enumerable Degrees”. Proceedings of the London Mathematical Society 3 (1): 537. 
• Lachlan, A.H. (1966b). “The impossibility of finding relative complements for recursively enumerable degrees”. J. Symb. Logic 31: 434-454. 
• Lachlan, A.H.; Soare, R.I. (1980). “Not every finite lattice is embeddable in the recursively enumerable degrees”. Advances in Math 37: 78-82. 
• Nies, Andre; Shore, Richard A.; (Slaman, Theodore A.) (1998), “Interpretability and definability in the recursively enumerable degrees”, Proc. London Math. Soc. (3) 77: 241-291, ISSN 0024-6115, MR1635141 
• Post, Emil L. (1944), “Recursively enumerable sets of positive integers and their decision problems”, en:Bulletin of the American Mathematical Society 50: 284?316, ISSN 0002-9904, MR0010514 
• Sacks, G.E. (1964). “The recursively enumerable degrees are dense”. Ann. of Math.(2) 80: 300-312. http://links.jstor.org/sici?sici=0003-486X(196409)2%3A80%3A2%3C300%3ATREDAD%3E2.0.CO%3B2-0 2008年7月13日閲覧。. 
• Shore, Richard A.; (Slaman, Theodore A.) (1999), “Defining the Turing jump”, Mathematical Research Letters 6: 711-722, ISSN 1073-2780, MR1739227 
• Simpson, Stephen G. (1977), “First-order theory of the degrees of recursive unsolvability”, Annals of Mathematics. Second Series 105: 121-139, ISSN 0003-486X, MR0432435 
• Thomason, S.K. (1971). “Sublattices of the recursively enumerable degrees”. Z. Math. Logik Grundlagen Math 17: 273-280. 
• Yates, C.E.M. (1966). “A minimal pair of recursively enumerable degrees”. J. Symbolic Logic 31 (2): 159-168. http://links.jstor.org/sici?sici=0022-4812(196606)31%3A2%3C159%3AAMPORE%3E2.0.CO%3B2-H 2008年7月13日閲覧。.