チューリング次数のソースを表示

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

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

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

==チューリング同値==
{{main|チューリング還元}}

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

二つの集合 <math>X</math> と <math>Y</math> について、<math>X</math> が <math>Y</math> にチューリング還元可能であり、かつ、 <math>Y</math> が <math>X</math> にチューリング還元可能であるとき、これらの集合は '''チューリング同値''' であると言い、<math>X \equiv_T Y</math> と書く。<math>\equiv_T</math> という関係は[[同値関係]]と捉えることができる。すなわち任意の集合 <math>X</math>、<math>Y</math>、<math>Z</math> について
* <math>X \equiv_T X</math>
* <math>X \equiv_T Y</math> ならば <math>Y \equiv_T X</math>
* もし <math>X \equiv_T Y</math> かつ <math>Y \equiv_T Z</math> ならば、<math>X \equiv_T Z</math>。

==チューリング次数==
'''チューリング次数'''は関係 <math>\equiv_T</math> の[[同値類]]である。<math>[X]</math> と書いて集合 <math>X</math> を含むような同値類を表す。 チューリング次数全体を表す記号として <math>\mathcal{D}</math> と書く。

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

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

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

==チューリング次数の基本的性質==
* 個々のチューリング次数は[[可算集合|可算無限]]である。すなわち、一つの次数には丁度 <math>\aleph_0</math> 個の集合が対応する。

* 互いに相異なるチューリング次数は <math>2^{\aleph_0}</math> 個存在する。

* 各次数 '''a''' について、不等式 '''a''' < '''a&prime;''' が厳密に成り立つ。

* 各次数 '''a''' について、'''a''' よりも小さい次数の集合の濃度はたかだか[[可算集合|可算]]。'''a''' よりも大きい次数の集合の濃度は <math>2^{\aleph_0}</math>。

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

===順序性===
* '''極小次数'''が存在する。  次数 '''a''' が「極小」であるとは、'''a''' が 0 でなく、かつ、次数 '''0''' と '''a''' の間に他の次数が存在しないことである。従って次数の順序関係は[[稠密順序|稠密]]順序ではない。
* 0 でない全ての次数 '''a''' について、'''a''' とは比較不可能な次数 '''b''' が存在する。
* 互いに比較不可能なチューリング次数の対は <math>2^{\aleph_0}</math> 通りある。
* 次数の対で[[順序集合#上界、最大、極大、上限、上方集合|下限]]を持たないものが存在する。従って <math>\mathcal{D}</math> は[[束 (束論)|束]]ではない。
* 全ての可算な[[順序集合|半順序集合]]は、チューリング次数に埋め込める。
* チューリング次数の[[単調写像|狭義単調増加]]する無限列は、[[順序集合#上界、最大、極大、上限、上方集合|上限]]を持たない。

===ジャンプに関する性質===
* 全ての次数 '''a''' について、'''a''' と '''a&prime;'''の厳密に中間に位置する次数が存在する。実際に、'''a''' と '''a&prime;'''の間にある互いに比較不可能な次数の対は可算個存在する。
* ある次数 '''a''' が '''b&prime;'''と書ける必要十分条件は、'''0&prime;'''≤ '''a'''。
* 如何なる次数 '''a''' についても、次数 '''b''' が存在して、'''a''' < '''b''' かつ '''b&prime;'''= '''a&prime;'''を満たす。このような次数 '''b''' を '''a''' から相対的に「低い」と呼ぶ。
* 全ての ''i'' について、<math>\mathbf{a}'_{i+1} \le \mathbf{a}_i</math> を満たすような次数の無限列 '''a'''<sub>i</sub> が存在する。

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

==r.e.チューリング次数の構造==
[[帰納的可算集合]]を持つ次数は '''r.e.'''（recursively enumerable 帰納的可算）または '''c.e.'''（computably enumerable 計算可枚挙） と呼ばれる。全ての r.e.次数は '''0&prime;'''よりも小さいか等しい。しかしながら '''0&prime;'''よりも小さい全ての次数が 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.次数の対が一つ存在する。
* {{harv|S. K. Thomason|1971}} 全ての有限な[[束 (束論)|分配束]]はr.e.次数に埋め込める。実際に、可算で atomless な[[束 (束論)|ブール束]]を上限と下限を保つように埋め込むことが出来る。
* (A. H. Lachlan and R. I. Soare, 1980) （上限と下限を保つように）r.e.次数に埋め込めないような、有限な束が存在する。特に次の束は r.e.次数に埋め込めない。

::[[ファイル:rehasse.png]]

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

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

r.e.集合 <math>X</math> を構成する上で、優先度法のアイディアは、<math>X</math> が満たさねばならない可算個の「要件」の列を作るというものである。
例えば、'''0''' と '''0&prime;'''の中間である r.e.集合を作るには、全ての自然数 <math>e</math> について要件 <math>A_e</math> と <math>B_e</math> を満たせば十分である。ここで、<math>A_e</math> はインデクス <math>e</math> が指す[[神託機械]]が <math>X</math> から '''0&prime;''' を計算できないという要件であり、<math>B_e</math> はインデクス <math>e</math> が指す（オラクルを持たない）[[チューリングマシン]]が <math>X</math> を計算できないという要件である。
これらの要件は「優先順序」（要件と自然数との間の明示的な全単射）に従って並べられる。
証明は個々の自然数毎に一つずつの「段階」を踏んで帰納法的に進む。ここでいう段階とは、<math>X</math> の内容を枚挙する過程だと思えばよい。
個々の段階では、何らかの数を <math>X</math> に加えるか、又は <math>X</math> に加えることを恒久的に禁止して、「要件」を満足させていく（つまり <math>X</math> の全てが枚挙されたなら全ての要件が成り立つように強いる）。
時として、ある数を <math>X</math> に加えると、一つの要件が満たされる代わりにそれまで満たされていた別の要件が満たされなくなる（「傷付けられる」と言う）ことが起きる。
この場合は要件の優先順序を用いてどの要件を満たすべきかを決定する。
大まかなアイディアとしては、もし何らかの要件が傷付けられるなら、それより優先度が高い他の要件が何れ全て傷付けられなくなれば、最終的には傷付けられなくなるだろう、ということである。とはいえ全ての優先度論法がこのような性質を持つ訳ではない。
出来上がった集合 <math>X</math> が 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
* {{Citation | last1=Odifreddi | first1=P. G. | title=Classical Recursion Theory | publisher=North-Holland | location=Amsterdam | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-87295-1 | id={{MathSciNet|id=982269}} | year=1989 | volume=125}}
* {{Citation | last1=Odifreddi | first1=P. G. | title=Classical recursion theory. Vol. II | publisher=North-Holland | location=Amsterdam | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-50205-6 | id={{MathSciNet | id = 1718169}} | year=1999 | volume=143}}
* Rogers, H.   ''The Theory of Recursive Functions and Effective Computability'', MIT Press. ISBN 0-262-68052-1;  ISBN 0-07-053522-1
* {{citation |author=Simpson, Stephen G |year=1977 |title=Degrees of unsolvability: a survey of results |url=https://doi.org/10.1016/S0049-237X(08)71117-0 |series=Studies in Logic and the Foundations of Mathematics |volume=90 |pages=631-652 |publisher=Elsevier |doi=10.1016/S0049-237X(08)71117-0 |ISSN=0049-237X |ref={{harvid|Simpson|1977a}}}}
* 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.

=== 研究論文 ===
* {{Citation | last1=Kleene | first1=Stephen Cole | author1-link=:en:Stephen Kleene | last2=Post | first2=Emil L. | title=The upper semi-lattice of degrees of recursive unsolvability | id={{MathSciNet | id = 0061078}} | year=1954 | journal=[[:en:Annals of Mathematics|Annals of Mathematics. Second Series]] | issn=0003-486X | volume=59 | pages=379?407}}
* {{cite journal
 | author = Lachlan, A.H.
 | year = 1966a
 | title = Lower Bounds for Pairs of Recursively Enumerable Degrees
 | journal = Proceedings of the London Mathematical Society
 | volume = 3
 | issue = 1
 | pages = 537
}}
* {{cite journal
 | author = Lachlan, A.H.
 | year = 1966b
 | title = The impossibility of finding relative complements for recursively enumerable degrees
 | journal = J. Symb. Logic
 | volume = 31
 | pages = 434-454
}}
* {{cite journal
 | author = Lachlan, A.H.
 | coauthors = Soare, R.I.
 | year = 1980
 | title = Not every finite lattice is embeddable in the recursively enumerable degrees
 | journal = Advances in Math
 | volume = 37
 | pages = 78-82
}}
* {{Citation | last1=Nies | first1=Andre | last2=Shore | first2=Richard A. | last3=Slaman | first3=Theodore A. | author3-link=Theodore Slaman |title=Interpretability and definability in the recursively enumerable degrees | id={{MathSciNet | id = 1635141}} | year=1998 | journal=Proc. London Math. Soc. (3) | issn=0024-6115 | volume=77 | pages=241-291}}
* {{Citation | last1=Post | first1=Emil L. | title=Recursively enumerable sets of positive integers and their decision problems | id={{MathSciNet | id = 0010514}} | year=1944 | journal=[[:en:Bulletin of the American Mathematical Society]] | issn=0002-9904  |volume=50 |issue=5 | pages=284-316 |url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-50/issue-5/Recursively-enumerable-sets-of-positive-integers-and-their-decision-problems/bams/1183505800.full?tab=ArticleFirstPage}}
* {{cite journal
 | author = [[:en:Gerald Sacks |Sacks, G.E.]]
 | year = 1964
 | title = The recursively enumerable degrees are dense
 | journal = Ann. of Math.(2)
 | volume = 80
 | pages = 300-312
 | url = http://links.jstor.org/sici?sici=0003-486X(196409)2%3A80%3A2%3C300%3ATREDAD%3E2.0.CO%3B2-0
 | accessdate = 2008-07-13
}}{{404|date=2024-05}}
* {{Citation | last1=Shore | first1=Richard A. | last2=Slaman | first2=Theodore A. | author2-link=Theodore Slaman |title=Defining the Turing jump | id={{MathSciNet | id = 1739227}} | year=1999 | journal=Mathematical Research Letters | issn=1073-2780 | volume=6 | pages=711-722}}
* {{Citation | last1=Simpson | first1=Stephen G. | title=First-order theory of the degrees of recursive unsolvability | id={{MathSciNet | id = 0432435}} | year=1977 | journal=[[:en:Annals of Mathematics|Annals of Mathematics. Second Series]] | issn=0003-486X | volume=105 | pages=121-139 |url=https://www.jstor.org/stable/1971028 |doi=10.2307/1971028}}
* {{cite journal |author=Thomason, S. K. |year=1971 |url=https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19710170131 |title=Sublattices of the Recursively Enumerable Degrees |journal=Mathematical Logic Quarterly |volume=17 |issue=1 |pages=273-280 |doi=10.1002/malq.19710170131 |ref={{harvid|S. K. Thomason|1971}}}}
* {{cite journal
 | author = Yates, C.E.M.
 | year = 1966
 | title = A minimal pair of recursively enumerable degrees
 | journal = J. Symbolic Logic
 | volume = 31
 | issue = 2
 | pages = 159-168
 | doi=10.2307/2269807
 | url=https://doi.org/10.2307/2269807
 | accessdate = 2024-05-30
}}

{{Normdaten}}
{{DEFAULTSORT:ちゆうりんくしすう}}

[[Category:数理論理学]]
[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]
[[Category:アラン・チューリング]]