Is a language semi-decidable iff it is reducible to ATM?

Question

Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true.

Below is the definition of ATM.

ATM={<M,w>| a TM, M accepts w}

The question from my understanding is that a language needs to be reducible to ATM for it to be considered semi-decidable. What I've tried to do is just understand that if a language is semi-decidable , then it must be reducible to another semi-decidable machine including ATM.

The key challenge I face here is how do I prove that? One thought I had is to disprove it by going the opposite way because ATM is also undecidable, meaning if ATM is also undecidable, the languages that it reduces to can also be undecidable and not semi-decidable.

However, the question is asking to prove why the original statement is true? I can't see a proof that goes both direction to prove that it is true.

Thank you.

Answer 1

The proof contains two main statements:

1. prove that $RE$ (the set of all semi-decidable languages) is closed under $\le_{m}$ reduction (many-one reduction). It means that if we have a reduction $L_{1} \le_{m} L_{2}$ and $L_{2} \in RE$, then $L_{1} \in RE$. (hint: construct a recognizer for $L_{1}$ using TM for a reduction function and a recognizer for $L_{2}$, the easier part)
2. prove that $A_{TM}$ (or ATM) is $RE$-complete problem (wiki)(the harder part). (hint: it's much easier to use the fact that $HALT$ is $RE$-complete, but the direct proof isn't so hard too).

Options 1 (when $L_{2} = A_{TM}$) and 2 will give to you iff in your statement.

Answer 2

It shouldn't be possible as introducing ATM/an ATM decider to the TM decider of your problem should introduce a contradiction to the decider. I am not an expert in decidablity, but it seems that this paper http://www.cs.toronto.edu/~ashe/comp.pdf from the University of Toronto has a good paper on this proof. It might be better to understand their paper as I could be losing things in translation.