- f be a decidable decision problem.
- g be an undecidable decision problem.
I refered to those rules:
- If $f$ reduces to $g$ and $g$ is decidable $\implies$ $f$ will be decidable.
- If $f$ reduces to $g$ and $f$ is not decidable $\implies$ $g$ will be not decidable.
1) It may be possible to reduce $f$ to $g$. But why?
Reducing $f$ to $g$ means to reduce decidable to undecidable. If I take a look at these rules the outcome of the implication will always be true and the "implier" will always be false because of the end - so $f$ might be reduced to $g$.
2) It is definitely not possible to reduce g to f. Why?
Reducing $g$ to $f$ means to reduce undecidable to decidable. If I take a look at these rules the outcome of the implication will always be false and the second part of the and of the "implier" will be true, therefore the reduction MUST be false.
Are my thoughts correct? Overall: When can you reduce two decidability problems?