# how to mapping reduce any r.e. language to the diagonal language K?

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?

• What's the diagonal language? What is mapping reducibility?
– Jalex Stark
Mar 30, 2018 at 21:45
• @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!
– D.W.
Apr 4, 2018 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$.
• 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? Apr 4, 2018 at 1:18