\begin{align} EQ_{\mathrm{TM}} &= {\{ \langle M,N\rangle : L(M)=L(N) \}}\\ A_{\mathrm{TM}} &= {\{ \langle M,w\rangle : \textrm{TM $M$ accepts $w$}\}} \end{align}

I can do it using $E_{\mathrm{TM}}$ but I want to know if it is possible using $A_{\mathrm{TM}}$ because I am not able to do it.

I thought the following:

Input to $A_{\mathrm{TM}}$ is $\langle M,w\rangle$

Run $EQ_{\mathrm{TM}}$ on $\langle M_1,N\rangle$ where $M_1$ is a modified version of $M$ that only runs if input is $w$. Hence $L(M_1) = \{w\}$.

$N$ is a simple TM that accepts only $w$.

Is this correct?

  • $\begingroup$ Yes, your approach is correct except that the terms are not appropriate. Fore example, you meant to run the decider for $EQ_{\mathrm{TM}}$ on $\langle M_1,N\rangle$ instead of "Run $EQ_{\mathrm{TM}}$". $M_1$ should still run if the input is not $w$; it just rejects. $\endgroup$ – John L. Apr 16 '19 at 21:59

Your Answer

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

Browse other questions tagged or ask your own question.