# Turing degree

tags
Computability theory

The idea behind Turing degrees is similar to the notion of cardinality of infinite sets ($ℵ_0, ℵ_1, …$) in the world of computation.

A Turing degree is an equivalence class for the Turing equivalence. Being Turing equivalent for two sets $$X$$ and $$Y$$ means that a Turing machine can decide if an element belongs to the set $$X$$ when it has an oracle for membership to $$Y$$ (there is a way to formulate the membership problem for $$X$$ as a problem for $$Y$$) and reciprocally.

The Turing degree $$\mathbf{0}$$ corresponds to all computable sets and is the smallest degree.

Last changed | authored by