2
$\begingroup$

Does a non deterministic Turing machine which is a decider halt on all branches for all inputs??

I know it must halt on all branches for a string not in language, but for a string in language, NDTM requires only one accepting branch so even if some other branch is infinite, NDTM will still accept the string

$\endgroup$
2
$\begingroup$

You can define it either way. The simple way to define it is to say that every branch must halt for every input. Alternatively, you can say that, if the input is in the language, at least one branch must accept, so you don't care if the others reject or just fail to halt; if the input is not in the language, then every branch must reject.

Both in terms of computability and complexity, you can show that the two definitions are completely equivalent.

$\endgroup$
  • $\begingroup$ I'm not so sure those will be equivalent in terms of complexity. ​ For example, suppose a language is decidable by a NDTM such that, when it accepts, at least one branch does so in 2^(o(n)) steps. ​ Is it known to follow that the language is decidable by a NDTM whose paths all halt in 2^(o(n)) steps? ​ ​ ​ ​ $\endgroup$ – user12859 Mar 15 '16 at 7:53
  • $\begingroup$ @RickyDemer Yes, that's known. As long as the function $f$ giving the bound is time-constructible, you can ensure that every branch halts in the required bound by first computing $f$ and then having every branch that hasn't already halted after $f$ steps halt and reject. $\endgroup$ – David Richerby Mar 15 '16 at 20:24
  • $\begingroup$ Why would there necessarily be a time-constructible function in 2^(o(n)) that bounds the lengths of minimal-length accepting paths? ​ ​ $\endgroup$ – user12859 Mar 15 '16 at 20:50

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.