Non-deterministic Turing machine that halts on at least one branches of computation

Problem Detail: 

I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing somewhere what you'd call a nondeterministic Turing machine that halts on at least one branch for all inputs, but may loop on others. Is there a name for such a thing? I see later in this chapter the word verifier, but that doesn't seem to fit... I think that refers to an algorithm.

A verifier for a language $A$ is an algorithm $V$, where $$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$ We measure the time of a verifier only in terms of the length of $w$, so a polynomial time verifier runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier.

Asked By : agent154

Answered By : vonbrand

The idea is that a deterministic TM will always answer Yes/No in finite time (else the whole idea makes no sense). And to do that, the deterministic simulation of the NTM can't just go off into lala-land on some branches, i.e., every branch must end in yes/no at a finite depth. It decides (gives you a definite answer). If not all branches halt, it can verify (i.e., given a word in the language it is guaranteed to answer Yes; if not, perhaps it anwers No, perhaps it loops).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9706