Re: Example for a non-rec.enum. language whose complement isn't rec.enum., too.

On 11 Jul., 21:58, Mitch <maha...@xxxxxxxxx> wrote:
On Jul 11, 2:10 pm, sanchopanch...@xxxxxx wrote:

Hello,

I am searching for an example of a non-recursively enumerable language
whose complement isn't rekursive enumerable, too.

An example for a non-recursively enumerable language whose complement -

is<- recursively enumerable should be the diagonal language, right?

Hmm...studying for exams, eh?

The conceptual heuristic to this is to find a hard to decide language
whose complement is even harder, essentially by going up higher in the
arithmetical hierarchy.

The halting problem (<M,w> such that w in L(M) ) is in Sigma_1, and
its complement is non-r.e. and is in Pi_1.

We're looking for a problem in Sigma_2 (a problem that is r.e. when
given a Sigma_1 oracle) and so it's complement will be in Pi_2, which
will also be non-r.e. (non-r.e. = all languages - the r.e. languages
(r.e. languages = Sigma_1)).

I think a good candidate for this would be "M such that L(M) is
total"...without working out the details, that seems to be in Sigma_2
(and not Sigma_1). And its complement (M where L(M) is infinite) must
be in Pi_2.

Thinking about the details though...checking that L(M) is -not- total
is easier (it's easy to have a -single- witness/example w with which
(with Sigma_1 oracle) one can check that L(M) does not halt). So maybe
'total' is in Pi_2, and 'not total' is in Sigma_2. Either way, you got
a pair where both the langauge and its complement are non-r.e. (sorry,
maybe that should be co-r.e.)

There's enough here so that even if I'm wrong in particulars, you can
figure out what's right. Other possibilities include the properties:
empty, finite, infinite, cofinite (the complement is finite (the
complement of an infinite set can still be infinite (e.g. evens/
odds))).

Mitch

Thank you.
.

Relevant Pages

  • Re: Enumerable sets
    ... Countable sets come in two flavors, finite and infinite. ... naturals themselves, or the set of all strings over an alphabet, ... IS one, in this context] are r.e., then it is recursive, or decidable. ... recursively enumerable but has a complement that is NOT recursively ...
    (sci.logic)
  • Re: Finite measure
    ... >defined on a measurable space. ... >every set of infinite measure has finite measure. ... a set of infinite measure whose complement also has ... Prev by Date: ...
    (sci.math)
  • Re: Example for a non-rec.enum. language whose complement isnt rec.enum., too.
    ... An example for a non-recursively enumerable language whose complement - ... And its complement is infinite) must ... (with Sigma_1 oracle) ...
    (comp.theory)
  • Re: Co-re set with no infinite r.e. subset
    ... |> Is there an easy example of an infinite set of naturals that has no ... machines that have no transitions to the halt state, ... then it's the complement of what's called a simple ...
    (sci.logic)
  • Re: Co-re set with no infinite r.e. subset
    ... |> Is there an easy example of an infinite set of naturals that has no ... machines that have no transitions to the halt state, ... then it's the complement of what's called a simple ...
    (sci.math)