We know that the halting problem $A_{TM}$= $\{(e,x) \mid M_e(x)$ accepts$\}$ and the diagonal language K= $\{e \mid M_e(e)$ accepts$\}$ are mapping reducible to each other. Recall that A mapping reducible to B means there exists a computable function from A to B s.t. for all x in A, x in A iff f(x) in B. Furthermore both are complete with respect to this mapping reduction relation.

I would like to prove that any r.e. language is mapping reducible to K directly without reducing to ATM. How can this be done?

  • $\begingroup$ What's the diagonal language? What is mapping reducibility? $\endgroup$
    – Jalex Stark
    Mar 30 '18 at 21:45
  • $\begingroup$ @Math1000, may I make a request for the future? In the future, if you suggest another site, can you let the poster know not to cross-post on multiple sites? You can suggest they delete the copy here before posting elsewhere. Hopefully this will provide a better experience for all. Thanks for listening! $\endgroup$
    – D.W.
    Apr 4 '18 at 0:40

For any r.e. language $L$, it is the domain of some M_l.

Consider the machine $M_n(x,y)=M_l(x)$, and now let $f(x)=s_1^1(n,x)$ (obtained from snm theorem). Hence for any $y$, $M_{f(x)}(y)=M_l(x)$

Then $L$ can be reduced to $K$ by $f$ :

if $x\in L$ iff M_l(x) halts iff $M_{f(x)}(f(x))$ halts iff $f(x)\in K$.

  • $\begingroup$ if $M_{f(x)}(f(x))$ halts why should $M_l(x)$ halt? Is it because $M_{f(x)}(y)$ is the constant function wrt to y? $\endgroup$
    – user352102
    Apr 4 '18 at 1:18
  • $\begingroup$ @user352102 Yes, exactly, by using snm, we obtain a constant function. $\endgroup$
    – Xoff
    Apr 4 '18 at 5:01

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.