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

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.

• Hi! I just also added the definition of ATM. Thank you very much! Dec 9, 2022 at 6:31
• This result is false if you consider a Turing reduction. I dunno for many-one reduction. Dec 9, 2022 at 15:57

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.