3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Not relevant, but... the first statement looks trivial. You probably want "non deterministic TM M1" there (?) $\endgroup$
    – chi
    Commented Jan 7, 2016 at 16:43
  • $\begingroup$ Not actually, my doubt was regarding the term "equivalence", based on the two theorems. So "deterministic TM M1" was supposed to be there. :) $\endgroup$
    – Romy
    Commented Jan 7, 2016 at 16:50
  • $\begingroup$ As I said, my comment is indeed not relevant to your question, but the first statement still looks trivial, since taking M2=M1 proves it. It's not a statement you will find in a computability book, for instance. $\endgroup$
    – chi
    Commented Jan 7, 2016 at 16:55
  • $\begingroup$ Omg I made a blunder here!M1 was supposed to be Non-deterministic.Thanks a lot for your concern. $\endgroup$
    – Romy
    Commented Jan 7, 2016 at 17:11

3 Answers 3

Reset to default
9
$\begingroup$

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$).

Improve this answer
$\endgroup$
3
$\begingroup$

"Equivalence is undecidable" means there is no algorithm (always halts after a finite time and correctly answers yes/no), "there is an equivalent" is just existence. I.e., given $M_1$ and $M_2$, no algorithm can tell if they are equivalent for all cases of $M_1$ and $M_2$ (some cases can be answered simply, but not all). The other is that for $M_1$ there is an equivalent $M_2$. It is even easy to construct some, just shuffle the states around, or add a completely useless state.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ However, in this case the existence is actually algorithmic – given a non-deterministic TM, we can construct algorithmically an equivalent deterministic TM. $\endgroup$
    – Yuval Filmus
    Commented Jan 7, 2016 at 18:57
0
$\begingroup$

Argument 1 says that for every non-deterministic Turing machine, we can build a deterministic Turing machine for recognizing the same language.

Argument 2 is not related to argument 1.

Argument 2 says that even though there may be two Turing machines that are equal, can not decide or prove they are equal. so it is undecidable.

Improve this answer
$\endgroup$

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.