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).

  • $\begingroup$ 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! $\endgroup$ – Shaull Dec 26 '17 at 14:40
  • $\begingroup$ hi shaull. thanx very much for the reply! I could not prove it. can you give me a hint for that? thanx! $\endgroup$ – Itamar Silverstein Dec 29 '17 at 11:38
  • $\begingroup$ 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? $\endgroup$ – Itamar Silverstein Dec 29 '17 at 12:22

I'm fairly certain this has been asked before, but I couldn't find it, so here goes:

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}$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.