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

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?

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.

StackExchange Computer Science Q#1586, answer score: 4