The Turing degree of a set is its equivalence class under mutual Turing reducibility. Degrees inherit the partial order induced by Turing reducibility. The Friedberg–Muchnik theorem gives incomparable degrees represented by computably enumerable sets.
In computability theory, a **Turing degree** is a measure of the level of non-computability of sets of natural numbers (or, more generally, of decision problems). It is a way to classify problems based on their inherent difficulty in terms of solutions that can be obtained by a Turing machine.
New to topics? Read the docs here!