Is the statement $A \leq_{\operatorname{mo}}^{\operatorname{poly}}B \land A\in \operatorname{REC}\implies B\in\operatorname{REC}$ true?

33 Views Asked by At

Is the statement $A \leq_{\operatorname{mo}}^{\operatorname{poly}}B \land A\in \operatorname{REC}\implies B\in\operatorname{REC}$ true?

I know, that $A \leq_{\operatorname{mo}}^{\operatorname{poly}}B$ means that we have a computable function $f:\Sigma^*\to \Sigma^*$ with $x\in A \iff f(x)\in B$, which means we have $\exists \operatorname{TM} M_f$ that computes $f$. $A\in \operatorname{REC}$ means, that we have $\exists \operatorname{TM} M_A$ which terminates everytime and either outputs $1$ if $w\in A$ or $0$ if $w\notin A$. I don't know how to go on... The statement is probably not true, because if $A$ can be reduced to $B$ means it only maps all elements in $A$ on parts of $B$. So $B$ could probably still be undecidable.

1

There are 1 best solutions below

2
On BEST ANSWER

No this is not true. An example of a many-one reduction from, say, $\text{SAT}$ to the halting problem is as follows: map a formula $\phi$ to the tuple $(M,\phi)$ where $M$ is a Turing machine which, on input $\phi$, tests all potential satisfying assignments to $\phi$ and then halts or infinite loops based on whether $\phi \in \mbox{SAT}$. We have $\mbox{SAT} \in \mbox{REC}$ and $\mbox{SAT} \le_{\mbox{mo}}^{\mbox{poly}} \mbox{HALT}$ but $\mbox{HALT} \not\in \mbox{REC}$.