Are there decidable problems that are reducible to undecidable problems?

Question

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?

Answer 1

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$.

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?

I think you're confusing the set of recognizable languages with NP. A recognizable language has a computable verifier but the verifier doesn't necessarily run in polynomial time (and the time hierarchy theorem says that there are languages whose verifiers can't run in polynomial time). It's true that every decidable problem has a computable verifier (because being able to decide the problem essentially means that you can verify a given answer by just computing the correct answer and comparing) but that doesn't give you a reduction. Rather, it proves that every decidable language is itself recognizable.