2
$\begingroup$

We know that Extended Church-Turing Thesis (or Cobham's thesis) states that any 'reasonable' model of computation can be equivalent to Turing Machine model in at most polynomial time overhead.

People always believe that this ECTT is not true and a candidate counterexample is quantum computation. But, why they don't see Nondeterministic Turing machine as a counterexample? Is it because it didn't correspond to any real-world computing device?

Note: I don't know what is good tag for this question, so if you know one, please let me know.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

No, because nondeterministic Turing machines are not "reasonable" in the sense used here. In this context, the ECT talks about realistic models of computation, i.e., models that can be implemented on physical devices. Nondeterminism cannot be implemented directly given our current understanding of physics (we can simulate it on a deterministic machine, but that incurs an exponential slowdown).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The exponential slowdown comes from the reduction of a nondeterministic to a deterministic. It doesn't mean we can implement a nondeterministic machine, but rather we can implement a deterministic one emulating the behavior of a nondeterministic one, with an exponential slowdown caused by this emulation. $\endgroup$
    – nir shahar
    Commented Jul 12, 2021 at 17:09

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.