I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown' that two Turing machines which accept the same language is undecidable. This is not a homework question!


3 Answers 3


Let's restrict ourselves to Turing machines that ignore their input. Now suppose you have two Turing machines:

  1. Some given one T.
  2. Another that loops forever.

If you could decide if they accept the same language, you'd be able to decide if T halts or not. This is impossible - see the halting problem.

This applies to SW/HW as well. It's undecidable if two programs perform the same computation or not.

  • $\begingroup$ You've just repeated the interviewer's question back to them as a fact. OP (and the interviewer) are asking for a proof, not a link to Wikipedia. $\endgroup$
    – JeffE
    May 10, 2013 at 15:05
  • 4
    $\begingroup$ @JeffE No, I claim that the decidability of the OP's question implies decidability of the halting problem, which is widely known to be impossible. I believe it's reasonable to expect that if an interviewer ask such a question, (s)he knows about the undecidability of the halting problem. Why the halting problem is undecidable is another question. $\endgroup$
    – Petr
    May 10, 2013 at 18:48
  • $\begingroup$ If I were an interviewer, I would want a stand-alone proof. It is also widely known that deciding whether two TM's accept the same language is undecidable, but saying "That's well known", while perfectly true, says absolutely nothing about the interviewee's level of understanding. $\endgroup$
    – JeffE
    May 10, 2013 at 20:55
  • $\begingroup$ @JeffE Would you consider a reduction to the halting problem together with a proof of the halting problem's undecidability a stand-alone proof? $\endgroup$ May 12, 2013 at 17:59
  • $\begingroup$ Yes, I'd accept that, but a direct proof would be even better. $\endgroup$
    – JeffE
    May 12, 2013 at 23:05

If there were such an algorithm, then we could write another algorithm $P$ that, given a program $Q$ as input, first uses the supposed algorithm to decide if $Q$ accepts all strings. If Q does accept all, $P$ outputs some (fixed arbitrary) program $P(Q)$ that does not accept all strings. If $Q$ does not accept all, $P$ outputs some (fixed arbitrary) program $P(Q)$ that does accept all strings. So $P$ is a total program such that $P(Q)$ always functions differently than $Q$, contrary to the recursion theorem.

  • 2
    $\begingroup$ Remark: this is essentially the proof of Rice's theorem, which can also be used to answer the OP's question. $\endgroup$ May 12, 2013 at 20:27

I think this is an alternative answer: give a mapping reduction from HALT to L, where L is the language consisting of all Turing machine pairs that accept exactly the same inputs. Let f(<M,w>) = <A,B> where

A is defined on input x to simulate M on w, and if M halts, then accept x. B is defined on input x to accept x.

Then <A,B> is an instance of L iff M halts on w, since A only accepts x when M halts on w, while B accepts x regardless.


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.