Let (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$)
show that the language L={<M1,M2,w> | M1 and M2 both accept or reject w} is undecidable by reducing
ATM to L
Not really sure how to approach this. Any hints or pointers

  • $\begingroup$ What happens when $M_1$ is the Turing Machine that immediately accepts? $\endgroup$
    – Steven
    Apr 7, 2021 at 18:06
  • $\begingroup$ Give a computable function $f$ from $\langle M,w \rangle$ to $\langle M_1,M_2,w \rangle$ such that $\langle M,w \rangle$ accepts if and only if $f(\langle M,w \rangle)$ accepts $\endgroup$
    – awillia91
    Apr 8, 2021 at 19:26

1 Answer 1


Try to define $M'$ that would accept $\iff$ both $M_1$ and $M_2$ accepted or rejected (together)


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.