0
$\begingroup$

Is there an algorithm to decide if any two Turing machines accept the same language? I can't find a definite answer to this. My guess is that there isn't, because then we would be able to decide if a Turing machine accepts a given language and halts, which is undecidable. Is there a better explanation for why this is or is not the case?

$\endgroup$
2
$\begingroup$

Your guess is correct: deciding whether two Turing machines are equivalent (i.e. accept the same language) is an undedicable problem.

To prove this, it should be possible to reduce this problem to the halting problem.

You can also use Rice's theorem.

The theorem states the following:

Let P be any non-trivial property of languages of Turing machines. Then, the following language is undecidable, $LP=\{\langle M\rangle : L(M) \text{ satisfies } P\}$.

Note that $L \text{ satisfies } P$ means $L \in P$.

Note also that a “trivial property” is a property that is either satisfied by all languages, or a property that is not satisfied by any language.

Now, if you consider two machines $M_1$ and $M_2$, deciding whether $L(M_1) = L(M_2)$ is deciding whether $M_2 \in \{\langle M \rangle : L(M) \text{ satisfies } \{L(M_1)\}\}$.

Since $\{L(M_1)\}$ is non trivial (there exist machines which recognize it and there exist machines which do not recognize it), this problem is undecidable.

$\endgroup$
  • $\begingroup$ Ah, thank you. Is there a list of the trivial properties of languages of Turing machines? $\endgroup$ – Victor Brunell Apr 22 '15 at 19:28
  • 1
    $\begingroup$ A “trivial property” is a property that is either satisfied by all languages, or a property that is not satisfied by any language. I edited my answer to add this definition. $\endgroup$ – Tom Cornebize Apr 22 '15 at 20:55
  • $\begingroup$ One can also reduce to, say, universality of context-free languages. $\endgroup$ – Raphael Apr 22 '15 at 23:21

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.