7
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Perhaps just in the definition of the language recognized by a NTM? An NTM accepts a string $w$ if there exists at least one computation path that ends in the accepting state ... but not necessarily this happens for all input strings (otherwise L(NTM) = \Sigma^* ) $\endgroup$ – Vor Feb 12 '13 at 16:46
  • $\begingroup$ I believe that you would say that the machine "accepts" the language. $\endgroup$ – user6845 Feb 12 '13 at 19:03
  • $\begingroup$ A TM does not "accept" a language, it accepts strings. The set of strings accepted by a TM is the language of that TM, noted L(M). You can say that A TM accepts the string-representation of a language though. $\endgroup$ – Kent Munthe Caspersen Jan 5 '14 at 21:08
  • $\begingroup$ @KentMuntheCaspersen Nope. The language accepted by a Turing machine is the set of input strings for which it reaches an accepting state. If, in addition, the machine halts for all strings it doesn't accept, it's said to decide the language. $\endgroup$ – David Richerby Jan 5 '14 at 23:44
  • $\begingroup$ @DavidRicherby Nope to what? $\endgroup$ – Kent Munthe Caspersen Jan 6 '14 at 12:30
2
$\begingroup$

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).

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Well, clearly an NTM can indeed have branches that are infinitely deep just by virtue of trying to solve an undecidable problem. What do you mean then to say that it can't? Or am I misunderstanding something? $\endgroup$ – agent154 Feb 20 '13 at 20:39
  • $\begingroup$ A deterministic TM will not always answer Yes/No in finite time, it may loop and thus never halt. A DTM simulating a NTM can loop on one of the branches of the NTM, but with a breadth-first simulation, the other branches will still be simulated though. A verifier can never loop on any input, since it is a decider. $\endgroup$ – Kent Munthe Caspersen Jan 5 '14 at 21:17
3
$\begingroup$

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 2*4*2*3*4*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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What does "an integer for which the product of some of the digits sum to 12000" mean? $\endgroup$ – David Richerby Jan 5 '14 at 23:55
  • 1
    $\begingroup$ Sorry, that description was vague, I have changed the "sum" to "equals". What this means is just that L contains all integers made by the digits d1d2...dn, where a multiset A of these digits exists, such that the product of all numbers in A equals 12000. For instance w = 164245455 is in L because 4*4*5*5*5*6 = 12000. But w = 999999999 is not in L. This was just an arbitrary decision problem, used to show what a verifier does and that it is often easier to verify a solution than to find one. $\endgroup$ – Kent Munthe Caspersen Jan 6 '14 at 12:27

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.