Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/StackCompSci/status/685338222495424512
Changed "deterministic TM M1" to "non deterministic TM M1".Sorry for inconvenience but this is the question I wanted to ask originally.
Source Link
Romy
Romy
  • 407
  • 5
  • 11

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?

Consider the following two arguments

"For every 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?

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?

Source Link
Romy
Romy
  • 407
  • 5
  • 11

Equivalence of Turing Machines

Consider the following two arguments

"For every 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?