Can we show a language is not computably enumerable by showing there is no verifier for it?

Question

One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following:

$A \subseteq \Sigma^*$ is c.e. iff there is a decidable language $V\subseteq \Sigma^*$ (called verifier) s.t. for all $x\in \Sigma^*$,

$x\in A$ iff there exists a $y\in\Sigma^*$ s.t. $\langle x, y \rangle \in V$.

So one way to show that a language is not c.e. is to show that there is no decidable verifier $V$ for it. Is this method useful to show that languages are not c.e. in practice?

Answer 1

In practice, we don't usually prove just that a language is r.e. or not r.e.. If the language is r.e., we want to know whether it is recursive. If it is not r.e., we want to know what sort of Turing degree it has, not just that the Turing degree is not r.e..

For example, if $P$ is a problem with $P' \equiv_T 0'''$ then $P$ is not r.e., but that fact about the Turing jump is more informative than just knowing $P$ is not r.e.

So while, in principle, you could show that a language is not r.e. by proving there is no verifier, in practice it is more informative to prove that the language is not r.e. by showing that it computes something that no r.e. set can compute; the nature of that 'something" typically gives useful information about the problem being studied.

Answer 2

To make the terminology I use clear: decidable = recursive = computable, semidecidable = recursively enumerable = computably enumerable, co-semidecidable = co-recursively enumerable = co-computably enumerable.

In practice, a common method to show that a language is not semidecidable is to show it is not decidable and that it is co-semidecidable. You then make use of the fact that any language that is both semidecidable and co-semidecidable is also decidable to conclude that your language is not semidecidable. (note that this only works in one direction: a language can be neither semidecidable nor co-semidecidable, in which case you need some other method)

As an example: we know that deciding whether a $\mathrm{CFG}$ is ambiguous is undecidable, but it is easy to co-semidecide: you just give a string that has two different parses. This implies that it is not semidecidable whether a $\mathrm{CFG}$ is ambiguous.

Another method is to show that the language is complete for some higher level of the arithmetic hierarchy.

It is of course possible to directly prove there is no verifier, but this is often tedious, as it usually repeats the proof that the halting problem is undecidable. Note though that the above argument essentially implicitly proves there can be no verifier, so I guess that you could say it is a method to prove there is no verifier, but then you could consider any proof of non-semidecidability as a proof that there is no verfier.