Re: Recursively enumerable sets

Twoflower <standa.kurik@xxxxxxxxx> writes:

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."

A language L is in RE iff there is a TM, M, that computes:

f(x) = 1 if x is in L, else undefined

(i.e. f is partial -- the TM may not terminate for some input
strings).

We can construct a list of all the possible input strings (they are
countable) x1, x2, x3... The problem you have is then to compute
f(x1), f(x2), f(x3)... without "getting stuck" on any one of the x's.

One way is to make a new machine, M' that simulates:

step 1 of f(x1)
step 2 of f(x1) and step 1 of f(x2)
step 3 of f(x1), step 2 of f(x2) and step 1 of f(x3)

and so on. At each stage, if the simulation of step n of f(xi) accepts
xi, then this algorithm adds xi to its output. Eventually, every
element of L will be produced by this algorithm.

I hope helps and that this memory dump from a long time ago does not
contain any daft errors!

--
Ben.
.

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)
  • brad does the neener neener gambit
    ... a faculty member of the College System in Minnesota. ... He made up some lies that he had some reason ... And it was ALWAYS with the strong support of hundreds of other list members. ... ever got any support from other members of lists. ...
    (sci.psychology.psychotherapy)
  • Re: Distribution List Resolution with new Contact List
    ... ..AddMember method, and you double-click that member, it doesn't open their ... Outlook version number. ... Distribution Lists if you use existing Outlook functionality. ...
    (microsoft.public.outlook.program_vba)
  • Re: help on EZScriptomatic mod
    ... > If strmanagedBy "" Then ... > For Each Item in strmember ... but it pulls the group members and reports>> the member DN to the file.) ... >>>I was trying to just get a list of users for some the groups, since there>>>are bunch of groups with hundreds of users I was using EZADScriptomatic>>>but for the members properties page it lists all of the info the member>>>users, I just wanted to get the name of the users and that's it. ...
    (microsoft.public.windows.server.active_directory)
  • Re: SS Maurice & Lazarus
    ... I'm not a member, so it doesn't ... Guy Coutant de Saissaval matriculated Arms with Supporters, ... As far as lists of members of the Ven Order of St John concerned it is ...
    (rec.heraldry)