##  [Turing Reducibility](/turing-reducibility-0) 

 Definition

A relation between decision problems (sets) A and B where A is Turing reducible to B if there exists a Turing machine that decides membership in A given an oracle for B; equivalently, A is computable relative to B.

 

 

 

 

 

 





## Principle

Principle

The organizing idea is access to B as an oracle: the machine may pose adaptive queries about membership in B and use the answers to decide A, so relative computability allows interaction rather than a single uniform translation.

 

 

 

 

 





## Demonstration

Demonstration

A standard demonstration is that the halting problem H is Turing reducible to the halting problem for machines with oracle O if an oracle for O answers certain crafted membership queries enabling simulation; more concretely, many undecidable sets reduce to H via oracle machines that adapt queries based on earlier answers.

 

 

 

 

## Misapplication

Misapplication

Using the term to imply a single computable transformation (many-one) or failing to allow adaptive queries — claiming Turing reducibility where only nonadaptive reductions exist — or ignoring resource bounds implicit in specific models.

 

 

 

 

 





## Consequence

Consequence

If A ≤_T B, then any oracle procedure for B yields an oracle procedure for A; the relation induces Turing degrees that classify sets by relative computability and underpins relativization results in computability and complexity theory.

 

 

 

 

## Reversal

Reversal

Reversing the reduction (B ≤_T A) alters which problem serves as an oracle; mutual Turing reducibility yields Turing equivalence and shared degree, while a single-direction reduction only shows relative computability of A from B.

 

 

 

 

 





## Boundary

Boundary

Applies to classical models of computation with oracle access; it excludes reductions that are nonuniform in unbounded ways, and distinctions arise when imposing polynomial-time or other resource restrictions that refine the notion (e.g., p-Turing reducibility).

 

 

 

 

 





## Semantic Tension

Semantic Tension

Turing reducibility sits between many-one reducibility (stronger, nonadaptive) and weaker notions like truth-table reducibility; it also contrasts with logical interpretability notions since Turing reducibility is computational rather than syntactic or model-theoretic.

 

 

 

 

 





## Synthesis

Synthesis

Turing reducibility captures relative computability via oracle access: a decision procedure for A can be implemented by a machine that adaptively queries an oracle for B, producing an equivalence class (Turing degree) representing mutual computability relationships.