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

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.

The strings accepted by a NTM M is the language of M, noted L(M)

Let us say that M for any input is not guaranteed to halt on all branches.
Then M clearly cannot be a decider, and is thus only a recognizer. M recognizes the language of all strings, for which any branch of M ends in an accepting state.

Since M is a recognizer, it is only guaranteed to accept a string if the string is in L(M).
Given a string, that is not in L(M), it may reject the string, or loop forever.
Any NTM can be simulated by a DTM, but if NTM only recognizes a language L, its equivalent DTM will also only recognize L.

If the NTM halts on all branches for any input it is a decider, then the equivalent DTM will do the same and thus be a decider as well.

A verifier is not the thing you are looking for. In Sipsers book, Introduction to the Theory of Computation, the verifier is introduced when talking about complexity of algorithms and complexity classes, because any language L is in NP if and only if it has a polynomial time verifier.

A verifier for a language L will take as input a string w in L and a certificate c (think of the certificate as a solution to the problem w) and verify that the certificate is in fact a correct solution, which makes w lie in L.

Example:

For the language

L = { w | w is an integer for which the product of some of the digits equals 12000 }

You can make a verifier V, that takes a string w in L, a certificate c, and verifies that w is in fact in L using the certificate c. c could be a binary string indicating the integers in w for which the product of equals 12000.

For example, V must reject the input 1923423343, 0010111011, because 24234*3 = 576 != 12000

For many problems, we only know an algorithm that can solve them running in exponential time of the input size. This is why verifiers are interesting, because it is often the case, that we given a solution quickly can determine if that solution is correct or wrong.

StackExchange Computer Science Q#9706, answer score: 3