Problem $6(20$ points$)$

We formalized the intuitive notion of a reduction that we saw in lecture with the definition of a mapping

reduction. However, there are other ways to formalize the idea of reductions. One formalization, called a

Turing reduction, captures the intuition that in a reduction from $A$ to $B,$ a decider for A can be implemented

by calling, possibly more than once, a decider for $B$ as a subroutine. An algorithm with access to a subroutine

for deciding $B$ is formalized by the definition of an oracle Turing machine.

Definition $($Oracle Turing Machine$).$ Given language $B,$ a $B-$oracle Turing machine $M$ is a multi$-$tape

Turing machine with a special tape called the query tape, a special tape called the oracle tape, and a special

state called the query state. If $M$ enters the query state, then the output of the question $\text{'}$is the string on

the query tape in $B?\text{'}$ is written on the oracle tape $($e$.$g$.1$ for yes, $0$ for no$).$

Note that $M$ doesn't compute the answer to the query: in a single computational step, the answer to the

query is output to the oracle tape. You can think of the query and oracle tapes as input and output ports

to an external device that decides $B$ for $M.M$ doesn't know or care how the external device answers the

query, it just makes use of the result. High$-$level descriptions of $B-$oracle Turing machines are exactly like

high$-$level descriptions of Turing machines, except that when descibing a $B-$oracle Turing machine you can

additionally say 'query the oracle on input $x\text{'},$ and then condition on the output.

Definition $($Turing Reduction$).$ Given languages $A,B$ we say that $A$ is Turing reducible to $B,$ denoted

$A{?}_{T}B,$ if there is a $B-$oracle Turing machine that decides $A.$ We also say that $A$ is decidable relative to $B.$

$($a$)(5$ points$)$

Prove that if there is a mapping reduction from $A$ to $B,$ then there is a Turing reduction from $A$ to $B.$

$($b$)(5$ points$)$

Give a Turing reduction from $HAL{T}_{TM}$ to $\frac{L}{O}O{P}_{TM}.$

$($c$)(10$ points$)$

Prove or disprove the following claim.

Claim $1.$ If there is a Turing reduction from $A$ to $B,$ then there is a mapping reduction from $A$ to $B.$