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

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

チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。
Q844718
計算理論
Concept
Q1166618
数理論理学
Concept
Q21199
自然数
Concept
Q8366
アルゴリズム
Concept
Q7251
アラン・チューリング
PER
Q843829
再帰理論
Concept
Q818930
計算可能性理論
Concept
Q3262192
決定問題
Concept
Q474715
半順序
Concept
Q351366
エミール・ポスト
PER
Q335148
スティーヴン・コール・クリーネ
PER
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
Q1527413
チューリング次数
Concept
2020-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-02-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
2
DATE
2020-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1
DATE
2019-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
19
DATE
2044-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
44
DATE
2019-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
19
DATE
2054-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
54
DATE
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+1944^^http://www.w3.org/2001/XMLSchema#decimal
1944
NUMBER
+1954^^http://www.w3.org/2001/XMLSchema#decimal
1954
NUMBER
named after
subclass of
named after
named after
named after
named after
named after
named after
named after
named after
named after
named after