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

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

• @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. – David Richerby Mar 15 '16 at 20:24