Hi,

I am having trouble understanding reductions and the connection between Htm and Atm.

In the lecture (7 slide 41) we said that we can show Htm is undecidable by reduction to Atm, isn't it supposed to be by reduction from Atm to Htm?

The way to show it is using an algorithm in which we falsely assume there is a TM R which decided Htm and we build from it a TM which decides Atm, which is a reduction from Atm to Htm (considering what we said in Recitation 8 slide 4). Meaning, we construct a TM which decides the language we **reduce from** (Atm) and not the language we **reduce to** (Htm).

But, in all the reduction examples in the same recitation, we always show TMs which decided the language we reduce to and not the language we reduce from. For example, slides 21-22 we reduce Atm <_m Linf yet we construct a TM M' which accepts x if M accepts w.

I think I am missing something here, but I am not sure what. It seems like there are two ways to do a reduction. One using some sort of a black box algorithm and the other using a specific reduction function, but I am not sure exactly.

Also, could you please specify exactly the reduction function from Atm to Htm (or from Htm to Atm, if I got it wrong)?