1
$\begingroup$

It is often stated that nondeterministic Turing machines cannot recognize any more languages than ordinary Turing machines. In particular, it is stated that there is no NTM that can take as input a DTM/input string and state whether that DTM will halt.

Is this proven, or is this an assumption under the same banner as the Church-Turing thesis?

If it is proven, does anyone have any citations for this in the literature?

$\endgroup$
  • $\begingroup$ You could always simulate the NTM using a TM, though not in polytime. That is, there is no assumption here. (Update: an answer was just posted to this effect.) $\endgroup$ – Omar Sep 20 '17 at 5:43
1
$\begingroup$

A nondeterministic Turing machine can be simulated using a deterministic Turing machine in exponential time (can be shown as a simple exercise). Furthermore, NDTM is a generalization of DTM. So, the computability powers of NDTMs and DTM are equal, in sense of decidability. So, the Halting problem is not decidable by a NDTM. However, their time complexity is different.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.