Question $5$:

Definitions. Let $A,$Bsube${}^{**}$ and assume that $A$ is decidable. Which of the following statements are guaranteed to be true $($whatever $B$ is$)?$ For each of these statements, give either a reference, a proof, or a counterexample.

$($a$)A{?}_{T}B$

$($b$)A{?}_{m}B$

Question $6$:

Accept, Halt, Loop on input $.$ In this problem, we consider the languages

$ACCEP{T}_{}=\{($:$M$:$)|M$ accepts $\}$

$HAL{T}_{}=\{($:$M$:$)|M$ halts $on$ input $\}$

$\frac{L}{O}O{P}_{}=\{($:$M$:$)|M$ loops $on$ input $\}$

It is known from class $($slide $155,$ lecture $22$b$)$ that language $ACCEP{T}_{}$ is undecidable.

$($a$)$ Prove that $HAL{T}_{}$ is undecidable by constructing a mapping reduction $ACCEP{T}_{}{?}_{m}HAL{T}_{}.$

$($b$)$ Prove that $HAL{T}_{}$ is recognizable by describing a recognizer.

$($c$)$ Prove that $\frac{L}{O}O{P}_{}$ is not recognizable.

Question $7$:

Showing that a language is enumerably complete.

Suppose that $A,$Bsube${}^{**}$ are languages such that

$(0)A{?}_{m}B$

$(1)A$ is enumerably complete

$(2)B$ is enumerable

Prove that $B$ is enumerably complete. That is$,$ explain why $B$ satisfies all conditions in the definition of enumerably complete languages.

Question $8$:

Language $L$ such that neither $L$ nor $\frac{?}{\text{b}\text{a}\text{r}}(L)$ is recognizable. Let $=\{0,1\}$ and define the language $L$ by

$L=\{win{}^{**}|$ either $w=0x$ for some $xin{A}_{TM}orw=1y$ for some $yi\frac{n}{b}ar(A_{TM})\}$

$($a$)$ Prove that $\frac{?}{\text{b}\text{a}\text{r}}(A_{TM}){?}_{m}L.$

$($b$)$ Prove that $\frac{?}{\text{b}\text{a}\text{r}}(A_{TM})\frac{?}{b}{?}_{m}ar(L).$

$($c$)$ Prove that neither $L$ nor $\frac{?}{\text{b}\text{a}\text{r}}(L)$ is recognizable.