Turing degree

≤ T A {\displaystyle B\leq _{T}A} が共に成り立つ。チューリング同値な集合の同値類をチューリング次数（Turing degree）と呼ぶ。集合 X {\displaystyle X} のチューリング次数を deg ( X ) {\displaystyle {\textbf

Computers and Communications Award Recipients”. IEEE. 2011年2月15日閲覧。 ^ “A. M. Turing Award”. Association for Computing Machinery. 2011年2月5日閲覧。 ^ “Israel Prize

チューリング次数（～じすう、英: Turing degree, degree of unsolvability）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次

Lamb Estate に赴いた。ジョン・マッカーシーは彼にスパイと警備員とパスワードに関するパズルを提示。ラビンはそれを研究して論文 "Degree of Difficulty of Computing a Function and Hierarchy of Recursive

the Possible Dream. CACM, May 96, 39, 5, 105-112. http://www.jdl.ac.cn/turing/pdf/p105-reddy.pdf 2011年9月8日閲覧。  - チューリング賞受賞講演 ^ a b “CMU Computer Science