10
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ what is c.e. (did you mean r.e.?) $\endgroup$ – Ran G. Apr 30 '12 at 5:40
  • $\begingroup$ I can't think of a situation where this is useful for proving a language is not CE. I expect you could easily replace $V$ with $A$ in a many-one reduction. If you came up with some other reduction, I would expect that "negative outputs" $\langle x,y \rangle \not \in V$ wouldn't mean much as $y$ is existentially quantified. $\endgroup$ – Lucas Cook Apr 30 '12 at 12:19
  • $\begingroup$ @RanG., r.e. is the old terminology, these days it is typically referred to as c.e. by people working in computability theory. (If you are interested about the reason for the change in the terminology I suggest checking Robert Soare's homepage.) $\endgroup$ – Kaveh Apr 30 '12 at 14:16
  • $\begingroup$ @Kaveh thanks. Every day one learns new things... $\endgroup$ – Ran G. Apr 30 '12 at 16:02
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ There's a flaw in your language. A language can be not semi-decidable and not co-semidecidable. Undecidable languages are such languages. $\endgroup$ – Dave Clarke Apr 30 '12 at 8:33
  • $\begingroup$ @DaveClarke: I added some terminology definitions. Is it correct now? $\endgroup$ – Alex ten Brink Apr 30 '12 at 8:48
  • $\begingroup$ Not (semi-decidable) $\neq$ not (decidable) $\wedge$ co-semidecidable. $\endgroup$ – Dave Clarke Apr 30 '12 at 8:51
  • $\begingroup$ @DaveClarke: I added a note saying it only works in one direction. $\endgroup$ – Alex ten Brink Apr 30 '12 at 8:56
  • 2
    $\begingroup$ I'm not convinced that this is a technique anyone would use. Why not reduce the problem to a known "not semi-decidable" problem. $\endgroup$ – Dave Clarke Apr 30 '12 at 9:02

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.