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.