5
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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 '13 at 15:05
  • 3
    $\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 Pudlák May 10 '13 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 '13 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$ – Quinn Culver May 12 '13 at 17:59
  • $\begingroup$ Yes, I'd accept that, but a direct proof would be even better. $\endgroup$ – JeffE May 12 '13 at 23:05
3
$\begingroup$

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.

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

Your Answer

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

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