Re: Co-re set with no infinite r.e. subset

From: Keith Ramsay (kramsay_at_aol.com)
Date: 09/08/04 

Date: 7 Sep 2004 17:57:41 -0700

"r.e.s." <r.s@ZZmindspring.com> wrote in message news:<CXm%c.9716$w%6.9034@newsread1.news.pas.earthlink.net>...
| "Daryl McCullough" <daryl@atc-nycorp.com> wrote ...
| > Is there an easy example of an infinite set of naturals that has no
| > infinite
| > r.e. subset? It would be better if it were co-r.e., but any example would
| > be nice. Thanks.
|
| The set of indices of the TMs that do not halt on a blank tape?

No, there are lots of infinite r.e. subsets of that. That's known
as a complete co-r.e. set and they always do. For example, take the
machines that have no transitions to the halt state, or ones that
always move to the right and output 1s, and so on.

What Daryl wants is known as an immune set. If it's the complement
of an r.e. set, then it's the complement of what's called a simple
set. Post proved there exists such a thing in 1944.

http://www.cs.cornell.edu/Courses/cs682/2004sp/Lectures/l37-post.pdf

Keith Ramsay

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: Example for a non-rec.enum. language whose complement isnt rec.enum., too.
    ... whose complement isn't rekursive enumerable, ... The conceptual heuristic to this is to find a hard to decide language ... 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)