Re: Recursively enumerable sets

On Monday 29 October 2007 18:23, Twoflower wrote:
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.

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.

There are different meanings of "runs forever".

The even naturals is R.E.: 2, 4, 6, 8, ... But any algorithm to print
them runs forever because there is an infinite number of them to
print. But notice that no (reasonable) algorithm would "halt and thus
can't proceed to next number".

What about evens plus "3"? One algorithm might be "print all the
evens, then print '3'". This particular algorithm never gets around
to printing 3. that is, if I asked you, "is printed printed after 10
steps?" or "after 50 steps?" or "after a billion steps?", you always
have to answer, no.
With the first algorithm (evens), I can ask any number, and you
could report when it would be printed. "Is 8427 printed after 10,000
steps?" "Yes"
Does this mean evens-plus-"3" is not R.E.? No. A different
algorithm, "print '3', then print all the evens" works fine. If I ask
about any number, you can tell me when it will be printed.

This informal explanation is intended to help you get a intuition for
what's going on. One should not depend on intuition or informal
arguments for proof; that's why we have "math". I compliment you for
asking clarification when you intuition doesn't match the math.

The interleaved-computation algorithm that Ben Bacarisse cited is a
neat way to side step problems of coming up with a generator or a
recognizer which only takes finite time for *all* inputs.

-paul-
.

Relevant Pages

  • 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 ... this algorithm may run forever." ... I know you already wrote me that the algorithm may run forever. ...
    (comp.theory)
  • Re: sparse polynomial arithmetic
    ... fastest algorithm for doing this computation? ... The classical algorithm ... is going to take forever. ... There is no attempt to optimise that for big ...
    (sci.math.symbolic)
  • Re: Sophism: Halting problem is decidable - relaunched
    ... How do you know one of the two outcomes will be produced? ... don't, then the "algorithm" will run forever, and hence not be an ... That seems odd to me because it means we can't decide ...
    (sci.math)
  • 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)