patternMinor
Equivalence of Turing Machines
Viewed 0 times
turingmachinesequivalence
Problem
Consider the following two arguments
"For every non deterministic TM M1 there exists an equivalent
deterministic machine M2 recognizing the same language."
"Equivalence of two Turing Machines is undecidable"
These two arguments seem a bit contradicting to me.
What should I conclude from these two arguments?
"For every non deterministic TM M1 there exists an equivalent
deterministic machine M2 recognizing the same language."
"Equivalence of two Turing Machines is undecidable"
These two arguments seem a bit contradicting to me.
What should I conclude from these two arguments?
Solution
These arguments are not really related, on several levels.
The first is that existence and computability are not the same thing. That is, even if there exists some object (e.g. a TM), it does not mean that finding (or computing) such an object can be done using a TM.
However, there is a more basic difference between the two statements. The first says that for every TM $M_1$, there exists some equivalent machine $M_2$. The second statement is that deciding, given $M_1$ and $M_2$, whether these two specific machines are equivalent, is undecidable.
Just to emphasize the difference, consider the following problem: given a TM $M_1$, is there some TM $M_2$, that is different from $M_1$, which is equivalent to $M_1$? This problem is trivial - the answer is always "yes" (e.g. just add a redundant state to $M_1$).
The first is that existence and computability are not the same thing. That is, even if there exists some object (e.g. a TM), it does not mean that finding (or computing) such an object can be done using a TM.
However, there is a more basic difference between the two statements. The first says that for every TM $M_1$, there exists some equivalent machine $M_2$. The second statement is that deciding, given $M_1$ and $M_2$, whether these two specific machines are equivalent, is undecidable.
Just to emphasize the difference, consider the following problem: given a TM $M_1$, is there some TM $M_2$, that is different from $M_1$, which is equivalent to $M_1$? This problem is trivial - the answer is always "yes" (e.g. just add a redundant state to $M_1$).
Context
StackExchange Computer Science Q#51584, answer score: 9
Revisions (0)
No revisions yet.