Re: Recursively enumerable sets

The definition of recursive enumerability does not require that the list
operation be completed in a finite number of steps. All that is required
is that if a given n is a member of the set, then n must appear as an
output within some finite number of steps. If n is not a member of the
set, then there is no requirement that we be able to learn that fact in
any finite number of steps.

If an r.e. set happens to have the property that its complement is also
r.e., then the set is recursive, because we can then alternate between
the two lists, knowing that any given n will eventually turn up on
exactly one of the two lists.

Thank you for your reply Dave.

What confuses me is this statement (I've taken it from Wikipedia)
about recursively enumerable sets:

"There is an algorithm that enumerates the members of S. That means
that its output is simply a list of the members of S: s1, s2,
s3, ... . If necessary, this algorithm may run forever."

I know you already wrote me that the algorithm may run forever.
Hovewer, if it runs forever, we don't get the enumeration, do we? I
guess I've a problem with understanding the concept of "running
forever". As I see it, the algorithm at some point, for some natural
number n, doesn't halt and thus can't proceed to next number to test
it. So it will never test any other numbers. What's wrong about these
considerations?

.

Relevant Pages

  • Re: Recursively enumerable sets
    ... If n is not a member of the ... this algorithm may run forever." ... I know you already wrote me that the algorithm may run forever. ... What about evens plus "3"? ...
    (comp.theory)
  • Re: Recursively enumerable sets
    ... If n is not a member of the ... If an r.e. set happens to have the property that its complement is also ... exactly one of the two lists. ... this algorithm may run forever." ...
    (comp.theory)
  • Re: decidable
    ... a proof of A, then the algorithm verifies that there is a proof of A, ... axiomatized by itself, i.e., every member of the theory is an axiom for ... The only theory that has as members only valid sentences is indeed the ...
    (sci.logic)
  • Re: MY LIST of the subsets of N
    ... I haven't gone through all the details of your algorithm, ... but I wonder of it's odd or even. ... S is the number fitself a member of S? ... Very curious function this f. ...
    (sci.math)
  • Re: MTDesk
    ... I have been a member there forever too, but for some reason, they lost my ID ...
    (sci.med.transcription)