チューリング次数（～じすう、）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。更に、チューリング次数は半順序を成すので、集合 formula_1 のチューリング次数が集合 formula_2 のチューリング次数よりも小さいならば、ある数が formula_2 に含まれるかを正しく判定するあらゆる（計算不可能なものも含む）手続きは、ある数が formula_1 に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。この記事では以後「集合」と言えば「自然数の集合」を指すこととする。ある数が集合 formula_1 の元かどうかを、オラクル集合 formula_2 を持つ神託機械を用いて決定できるとき、formula_1 は formula_2 にチューリング還元可能であると言い、formula_9 と書く。二つの集合 formula_1 と formula_2 について、formula_1 が formula_2 にチューリング還元可能であり、かつ、 formula_2 が formula_1 にチューリング還元可能であるとき、これらの集合は チューリング同値 であると言い、formula_16 と書く。formula_17 という関係は同値関係と捉えることができる。すなわち任意の集合 formula_1、formula_2、formula_20 についてチューリング次数は関係 formula_17 の同値類である。formula_28 と書いて集合 formula_1 を含むような同値類を表す。 チューリング次数全体を表す記号として formula_30 と書く。チューリング次数は半順序 formula_31を持つ。定義として、formula_32 である必要十分条件は formula_33である。計算可能集合を全て含む特別なチューリング次数が存在し、この次数は他の如何なる次数よりも小さい。この次数は半順序集合 formula_30 の最小元なので、0（ゼロ）と書く。（チューリング次数を表記する際は、集合と混同しないように太字 (boldface) で書くのが普通である。混同する恐れが無いなら（例えば formula_28 ）太字にせずとも良い。）任意の集合 formula_1 と formula_2 について、formula_1 と formula_2 の結び（ formula_40 と書く）を、集合 formula_41とformula_42の和集合として定義できる。formula_40 のチューリング次数は formula_1 と formula_2 の次数の上限である。従って formula_30 は結びを持つ半束である。次数 a と b の上限を a ∪ b と書く。下限を持たない次数の対が存在するので、formula_30 は束ではないことが知られている。集合 formula_1 について、formula_1 をオラクルに持つときに停止する神託機械を指すインデクスの集合を formula_50 と書く。集合formula_50はformula_1のチューリングジャンプと呼ばれる。次数 formula_28 のチューリングジャンプは次数 formula_54 であると定義される。これはformula_16 であれば必ず formula_56 ことからも妥当な定義である。一つの重要な例として 0′があるが、これは停止問題の次数である。チューリング次数の構造については大変多くの研究がある。以下に示す一覧は、知られている結果のごく一部を示すに過ぎない。一連の研究から得られた一つの一般的な結論は、チューリング次数の構造が極端に複雑だということである。帰納的可算集合を持つ次数は r.e.（recursively enumerable 帰納的可算）または c.e.（computably enumerable 計算可枚挙） と呼ばれる。全ての r.e.次数は 0′よりも小さいか等しい。しかしながら 0′よりも小さい全ての次数が r.e.次数という訳ではない。エミール・ポストは r.e.チューリング次数を研究し、0 と 0′の厳密に中間であるような r.e.次数は存在するか、と問うた。このような次数を構成する問題（または、それが不可能であることの証明）はポストの問題として知られるようになった。この問題は1950年代に Friedberg と Muchnik によって独立に解決され、そのような中間の r.e.次数が実在することが示された。彼らの証明方法は、r.e.次数を構成するための同じ新技法をそれぞれが導入したもので、これは優先度法として知られるようになった。今日、優先度法は r.e.集合について何らかの結果を得る際には主役となるテクニックである。r.e.集合 formula_1 を構成する上で、優先度法のアイディアは、formula_1 が満たさねばならない可算個の「要件」の列を作るというものである。例えば、0 と 0′の中間である r.e.集合を作るには、全ての自然数 formula_71 について要件 formula_72 と formula_73 を満たせば十分である。ここで、formula_72 はインデクス formula_71 が指す神託機械が formula_1 から 0′ を計算できないという要件であり、formula_73 はインデクス formula_71 が指す（オラクルを持たない）チューリングマシンが formula_1 を計算できないという要件である。これらの要件は「優先順序」（要件と自然数との間の明示的な全単射）に従って並べられる。証明は個々の自然数毎に一つずつの「段階」を踏んで帰納法的に進む。ここでいう段階とは、formula_1 の内容を枚挙する過程だと思えばよい。個々の段階では、何らかの数を formula_1 に加えるか、又は formula_1 に加えることを恒久的に禁止して、「要件」を満足させていく（つまり formula_1 の全てが枚挙されたなら全ての要件が成り立つように強いる）。時として、ある数を formula_1 に加えると、一つの要件が満たされる代わりにそれまで満たされていた別の要件が満たされなくなる（「傷付けられる」と言う）ことが起きる。この場合は要件の優先順序を用いてどの要件を満たすべきかを決定する。大まかなアイディアとしては、もし何らかの要件が傷付けられるなら、それより優先度が高い他の要件が何れ全て傷付けられなくなれば、最終的には傷付けられなくなるだろう、ということである。とはいえ全ての優先度論法がこのような性質を持つ訳ではない。出来上がった集合 formula_1 が r.e.であり全ての要件を満たすことを論証する必要がある。優先度論法は r.e.集合に関する様々な証明に使える。所期の集合を生成するには、要件とその満たし方を注意深く選ばねばならない。

出典:wikipedia