|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 次 ： [つぎ] 1. (n,adj-no) (1) next 2. following 3. subsequent 4. (2) stage 5. station ・ 次数 ： [じすう] (n) degree ・ 数 ： [すう, かず] 1. (n,n-suf) number 2. figure
チューリング次数（～じすう、）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。 任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。更に、チューリング次数は半順序を成すので、集合 のチューリング次数が集合 のチューリング次数よりも小さいならば、ある数が に含まれるかを正しく判定するあらゆる（計算不可能なものも含む）手続きは、ある数が に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。 チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。 ==チューリング同値== この記事では以後「集合」と言えば「自然数の集合」を指すこととする。ある数が集合 の元かどうかを、オラクル集合 を持つ神託機械を用いて決定できるとき、 は にチューリング還元可能であると言い、 と書く。 二つの集合 と について、 が にチューリング還元可能であり、かつ、 が にチューリング還元可能であるとき、これらの集合は チューリング同値 であると言い、 と書く。 という関係は同値関係と捉えることができる。すなわち任意の集合 、、 について * * ならば * もし かつ ならば、。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「チューリング次数」の詳細全文を読む スポンサード リンク
|