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

Comments


← Back to Notes