Cheap and Secure Web Hosting Provider : See Now

[Answers] Turing Machines and Algorithm for Language Acceptance

, , No Comments
Problem Detail: 

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?

Asked By : Victor Brunell

Answered By : Tom Cornebize

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 to 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41684

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback