Suggest edit — Oracle Reduction

Title

Name

Note

---
title: "Oracle Reduction"
type: concept
related: [Mapping Reduction]
source: https://www.jemoka.com/posts/kbhoracle_reduction/
confidence: high
status: active
---

Oracle Turing Machine An Oracle Turing Machine $M$ is a machine that can ask membership queries in a set $B \subseteq \Gamma^{*}$ on a special &ldquo;oracle tape&rdquo;. This Turing machine will receive an answer in one step: in particular, if the string written on the oracle tape is in $B$, then the state will be set to $q_{yes}$, and otherwise, we move to $q_{no}$
Importantly, $B$ does not have to be decidable. We think of them as subroutines.
Recognizing and Deciding We say that $A$ is recognizable with $B$ if there is an oracle TM $M$ with oracle $B$ that recognizes $A$ We say that $A$ is decidable with $B$ if there is an oracle TM $M$ with oracle $B$ that decides $A$ When $A$ is decidable with $B$, we call $A$ Turing Reduces to $B$; that is, $A \leq_{T} B$.
Some example $A_{TM} \leq_{T} HALT_{TM}$, $A_{TM} \leq_{T} HALT_{TM}$ On input $(M,w)$, if $(M,w)$ is in $HALT_{TM}$, then run $M(w)$ sound output the answer; otherwise, reject.
On input $(M,w)$, we want to decide if $M$ halts on $w$, so we just check that $(M, w) \in A_{TM}$ or swap accept and reject of $M$ to get $M&rsquo;$, and if $(M&rsquo;,w) \in A_{TM}$, then we also accept. Otherwise, we reject.
mapping reductions and turing reductions mapping reduction is weaker than turing reduction if $A \leq_{M} B$, then $A \leq_{T} B$
if $A \leq_{M} B$, then there is a computable function $f$ for every $w$. So, to decide $A$ on string $w$, we compute $f(w)$ and check if $f(w) \in L(B)$ by calling the oracle.
for instance&hellip; notice:
\begin{equation} \neg HALT_{TM} \leq_{T} HALT_{TM} \end{equation}
(because we just look it up and return the opposite)
and
\begin{equation} \neg HALT_{TM} \not \leq_{M} HALT_{TM} \end{equation}
because if this were to be true than $\neg HALT_{TM}$ should be recognizable since $HALT_{TM}$ is recognizable.
SUPERHALT \begin{equation} SUPERHALT = \qty {(M,x) | M, \text{ with an oracle for the halting problem, halts on $x$ } } \end{equation}
We show that this problem can&rsquo;t be decided through diagonalization. For contradiction suppose $H$ decides $SUPERHALT$. Let us define now a $D(X)$ for which if $H(X,X)$ accepts we loop, and otherwise accept. Now, consider $D(D)$. Suppose $D(D)$ accepts, this means that $H(D,D)$ rejected, meaning $D$ didn&rsquo;t halt on $D$, but that contradicts that $D(D)$ accepts. Suppose $D(D)$ rejects, that means that $H(D,D)$ accepts, but that means $D(D)$ is supposed to loop. Contradiction.
Given any oracle O, there&rsquo;s always a harder problem that cannot be decided with that oracle O SUPERHALT0 = HALT = for (M,x), M halts on x SUPERTHALT1 = for (M,x), M with an oracle for HALTtm, halts on x SUPERTHALTn = for (M,x), M with an oracle for SUPERHALTn-1, halts on x