---
tag: T6V685TY1Y
kind: definition
name: Turing reduction
msc: [03D30]
defines: PA4PYQ1PZ0
uses: [Z5CCVBME2V, PPGD5KW8JC]
sources:
  - url: https://en.wikipedia.org/wiki/Turing_reduction
---

## Definition

Let $A$ and $B$ be subsets of $\N$.
A *Turing reduction* from $A$ to $B$ is an [[oracle machine|Z5CCVBME2V]] $M$ such that $M$ with oracle $B$ halts on every input $x \in \N$.
Moreover, the output is $1$ if $x \in A$ and $0$ if $x \notin A$.
The set $A$ is *Turing reducible* to $B$, written $A \le_T B$, if such an $M$ exists.
The sets $A$ and $B$ are *Turing equivalent*, written $A \equiv_T B$, if $A \le_T B$ and $B \le_T A$.

## Remarks

Example: for every $B \subseteq \N$, the complement $\N \setminus B$ satisfies $\N \setminus B \le_T B$.
The machine asks the oracle whether $x \in B$ and outputs the opposite answer.

Non-example: the [[halting problem|Z7TN2B35B0]] $K$ satisfies $K \not\le_T \emptyset$.
An oracle machine with the empty oracle computes only what an ordinary Turing machine computes, and $K$ is not a [[computable set|PPGD5KW8JC]].

The relation $\le_T$ is reflexive and transitive.
A set $A$ satisfies $A \le_T \emptyset$ exactly when $A$ is computable.
Every [[many-one reduction|JTAH37JTHD]] gives a Turing reduction.
The converse fails: $\N \setminus K \le_T K$, but $\N \setminus K \not\le_m K$, since $K$ is computably enumerable and $\N \setminus K$ is not.