# Are there decidable problems that are reducible to undecidable problems?

I've seen a question asking if $A \le_m B$, then if $A$ is decidable, $B$ is also decidable. My initial intuition is that this is not the case, and that there are decidable problems that are reducible to undecidable problems. While I am not sure if this is completely correct, or even how to prove this if it is correct, I am thinking a decidable problem could be reduced to a recognizable, undecidable problem because a polynomial time verifier would work on a decidable problem. Is this a correct idea?

• Every question of the form "does this program halt" is an instance of the undecidable halting problem. – orlp Apr 11 '17 at 0:07

Any decidable problem can be reduced to the halting problem. Take a machine $M$ that decides some language $L$. Now produce a new Turing machine $M'$ that behaves identically to $M$ except that, if $M$ rejects, $M'$ loops forever. Now, $M'$ halts on input $x$ if, and only if, $x\in L$.
More generally, every decidable problem can be reduced to every undecidable problem. Let $Z$ be some undecidable language. We know that $Z\neq\emptyset$ and $Z\neq\Sigma^*$, since both of those languages are trivially decidable. Therefore, there are strings $z^+\in Z$ and $z^-\notin Z$. Now take any decidable language $L$. Since $L$ is decidable, the function $$f(x) = \begin{cases}z^+&\text{if }x\in L\\z^-&\text{if }x\notin L\end{cases}$$ is computable, and it is a reduction from $L$ to $Z$.