# Can Atm language be reduced?

I'm familiar with reductions to the language $A_{\mathrm{TM}}=\{\langle M,w\rangle | M \text{ accepts } w \}$, for example $A_{\mathrm{TM}}\le H_{\mathrm{TM}}$. Are there examples for reductions from $A_{\mathrm{TM}}$. By that I mean, a reduction such as: $B\le A_{\mathrm{TM}}$ (many to one reduction).

• The direction $A_{TM}\le_m H_{TM}$ is a reduction from $A_{TM}$. And as for your question - every language in RE can be reduced to $A_{TM}$. Try to prove it! – Shaull Dec 26 '17 at 14:40
• hi shaull. thanx very much for the reply! I could not prove it. can you give me a hint for that? thanx! – Itamar Silverstein Dec 29 '17 at 11:38
• this is my idea for the proof: we want to prove that every language B that is in RE can be reduced to Atm. (so that there is a computable function f such that f: {w from alephbet of B} -> {<M,w> from Atm} such that w belongs to B iff <M,w> is in Atm. SO WE BUILD THIS MACHINE: M(x) { run B(x) - if it returns accept then w=x and accept; } in this way if w belongs to B then we will accept only one input - this w. and if w does not belong to B L(N) is the empty language and in this case it will not belong to Atm as well. Can you please help me fix this proof or write it better? – Itamar Silverstein Dec 29 '17 at 12:22

We can reduce every problem in RE to $A_{TM}$ as follows. Let $L$ be a language in RE, and let $M$ be a TM such that $L(M)=L$.
The reduction then proceeds as follows: given input $x$, the reduction outputs $\langle M,x \rangle$.
It then trivially holds that $x\in L$ iff $M$ accepts $x$, iff $\langle M,x \rangle\in A_{TM}$.