---
tag: P5N2ND3VCG
kind: concept
name: Turing degree
msc: [03D28, 03D30]
sources:
  - url: https://en.wikipedia.org/wiki/Turing_degree
same_as:
  wikidata: Q1527413
  wikipedia: Turing degree
---

## Summary

The Turing degree of a set of natural numbers is the class of all sets that are Turing equivalent to it.
Two sets have the same degree when each is computable from the other, so the degree measures how uncomputable a set is.
The degrees are partially ordered by [[Turing reducibility|PA4PYQ1PZ0]], and the study of this order is a central part of computability theory.

## Explanations

### L1 human

Group sets of numbers by how hard they are to compute, where two sets are equally hard if each can be computed with the help of the other.
Each group is a Turing degree.
The lowest degree, written $\mathbf{0}$, contains all computable sets, such as the even numbers or the primes.
The set of halting programs lies in a higher degree, written $\mathbf{0}'$.
The degrees form a large and intricate ordering, with uncountably many degrees and many incomparable pairs.