  We study the class of languages that have membership proofs which can be
verified by real-time finite-state machines using only a constant number of
random bits, regardless of the size of their inputs. Since any further
restriction on the verifiers would preclude the verification of nonregular
languages, this is the tightest computational budget which allows the checking
of externally provided proofs to have meaningful use. We show that all
languages that can be recognized by two-head one-way deterministic finite
automata have such membership proofs. For any $k>0$, there exist languages that
cannot be recognized by any $k$-head one-way nondeterministic finite automaton,
but that are nonetheless real-time verifiable in this sense. The set of
nonpalindromes, which cannot be recognized by any one-way multihead
deterministic finite automaton, is also demonstrated to be verifiable within
these restrictions.
