-reductions are tricky for students to wrap their heads around at first. To show a given relation is undecidable, it suffices to show that the (diagonal) Halting Problem reduces to it. The relation is denoted

This is converse to what you need to do when you prove that is decidable given that is decidable. In this case, we need to show a reduction from to , that is

It’s pretty obvious why the order reverses when you say it out loud: if is decidable, then if deciding can be (computably) reduced to deciding , we can obviously decide . In a sense, we want to show that deciding is an easier problem that .

When showing undecidability, we reverse this relationship. To show that is undecidable from , it does not suffice to reduce to , since this only shows that deciding halting also decides , so is easier than in the same sense as earlier. However, this doesn’t mean that is undecidable, as could very well be sufficiently easier than to be decidable. Therefore, we need to actually show a reduction from to : deciding would allow you to decide , so is easier than . But is already undecidable, so a harder problem would still be undecidable.