Example for a non-rec.enum. language whose complement isn't rec.enum., too.
in [Theory]
|
Prev: Extended counter-example for extended M.Diaby Linear Model
Next: Integer factorization reduction to SAT
From: sanchopancho80 on 11 Jul 2008 14:10 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? Thanks, S.
From: Mitch on 11 Jul 2008 15:58 On Jul 11, 2:10 pm, sanchopanch...(a)web.de 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
From: tchow on 11 Jul 2008 16:00 In article <9a0502b4-b722-4771-9646-35f92133ad3e(a)l42g2000hsc.googlegroups.com>, <sanchopancho80(a)web.de> wrote: >I am searching for an example of a non-recursively enumerable language >whose complement isn't rekursive enumerable, too. Any r.e. set that is not recursive qualifies. If a set is both r.e. and co-r.e., then to decide whether a given x is in the set, just run both enumerations in parallel until x pops out of one of them. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: tchow on 11 Jul 2008 16:01 In article <4877bbcc$0$299$b45e6eb0(a)senator-bedfellow.mit.edu>, I wrote: >In article <9a0502b4-b722-4771-9646-35f92133ad3e(a)l42g2000hsc.googlegroups.com>, > <sanchopancho80(a)web.de> wrote: >>I am searching for an example of a non-recursively enumerable language >>whose complement isn't rekursive enumerable, too. > >Any r.e. set that is not recursive qualifies. Whoops! Sorry, I misread your question. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: sanchopancho80 on 11 Jul 2008 16:05
On 11 Jul., 21:58, Mitch <maha...(a)gmail.com> wrote: > On Jul 11, 2:10 pm, sanchopanch...(a)web.de 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. |