1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ What's the diagonal language? What is mapping reducibility? $\endgroup$
    – Jalex Stark
    Commented Mar 30, 2018 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. ♦
    Commented Apr 4, 2018 at 0:40

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 4, 2018 at 1:18
  • $\begingroup$ @user352102 Yes, exactly, by using snm, we obtain a constant function. $\endgroup$
    – Xoff
    Commented Apr 4, 2018 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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