Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursively enumerable?

  1. Jun 29, 2008 #1

    tgt

    User Avatar

    What does it mean?

    Does it basically mean that the algorithm will give a listing in some order if I feed in elements in the set?

    However elements not in the set will take forever. Sometimes, it is not possible to tell if an element is in the set or not as it might take a very long time (more then the time of the universe) but stop or it may not.
     
  2. jcsd
  3. Jun 29, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    RE means that there is some algorithm A such that if an element is in the set, A will eventually generate it, and that if an element is not in the set A will never generate it. Equivalently, A can be an algorithm that returns "yes", "no", or runs forever when asked if an element is in the set. It can return "no" or run forever if the element is not in the set, but if the element is in the set it must (eventually) return "yes".

    If the algorithm takes a long time to generate an element/return "yes", you can't tell in general whether it's in the set or not -- maybe the algorithm just hasn't gotten there yet, or maybe it's in its infinite loop.
     
  4. Jun 29, 2008 #3

    tgt

    User Avatar


    "If an element is not in the set, A will never generate it." Then how is it that an equivalent algorithm return 'no' for an element not in the set? It should be that an equivalent algorithm returns 'yes' for elements in the set and runs forever for elements not in the set.

    Apart from that, it seems what I posted in the OP is basically correct?

    Is it true that one difference between a recursively enumerable and recursive set is that the former gives a partial listing of the elements of the set (since elements not in the set will take an infinite amount of time to decide but some elements in the set may take an extremely long
    time to decide so at any time, we may be uncertain whether an element is in the set or not) and the latter a full listing?
     
    Last edited: Jun 29, 2008
  5. Jun 29, 2008 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    It can generate a "no", but it may run forever instead. It's not important -- the algorithm doesn't need to even return a "no".

    Yes.

    No. But for any given member, a recursive algorithm can say whether it's in the set or not; for a RE algorithm, no answer may ever come back.
     
  6. Jun 30, 2008 #5

    tgt

    User Avatar

    If it can return a 'no' then wouldn't it be able to decide membership in a set from a set of inputs? Or are you suggesting it's okay for the algorithm to return some 'no' but not all of them.





    The fact that no answer may come back implies that after a finite amount of time has gone, we don't know if those elements which are still undecided is in the set or not hence at that point in time a partial listing of the elements in the set is given. So what is wrong with what I stated?
     
  7. Jun 30, 2008 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    It's okay for the algorithm to return "no" for some but not all of its arguments.

    Being recursively enumerable is a weaker condition than being recursive, so it would even be okay if it did always return "yes" or "no". All recursive functions are recursively enumerable.

    You can't (generally) find give a full listing of a recursive set. Consider the even numbers: for any given number you can decide whether it's in the set or not, but no algorithm can list all the members of the set. This is almost always (in the technical sense of probability 1) the case.
     
  8. Jun 30, 2008 #7

    tgt

    User Avatar

    What is the difference between a set being recursive and recursively enumerable?

    A recursive set means membership in the set could be decided from a larger set.

    A recursively enumerable set means elements in the set could be listed. So there is no decision involved with recursive enumerability.
     
  9. Jul 1, 2008 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    With a recursive set, you can always test for membership in finite time. This is not the case with RE sets.
     
  10. Jul 1, 2008 #9

    tgt

    User Avatar

    So this suggests that with RE sets, if a decision for membership is done, after any finite amount of time has passed, a partial listing of the elements that belong to the set exists?

    However we usually don't think about RE sets that way? We usually think of RE sets having the property that there exists an algorithm that lists all elements in the set (where no decision is made). RE sets just means the set is able to be 'listed'. Correct?
     
  11. Jul 2, 2008 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    That seems to communicate no information. After a googol seconds, perhaps the RE algorithm has returned nothing; but nothing is a partial listing of the elements. But for a given element in the set, if we wait long enough, the RE algorithm will return it.

    I don't know what this "we" thinks. A RE algorithm given 'infinite' time would list all its elements, yes; but unless the set is finite, it will never produce the list in finite time. Further, even for finite sets, the time taken by the algorithm is unbounded. It will eventually list all elements, but:
    * It won't know it's done (it would just keep working)
    * It could take a very long time, like a googol seconds, just to list those elements

    I'll note that there need not be any difference between the "listing" algorithm and the "decision" algorithm. A listing algorithm can be built from a decision algorithm like this:
    Code (Text):
    for n in [0, 1, ..., infinity]
      if n is in the set
        if n has not been printed
          print n
    and a decision algorithm can be built from a listing algorithm like this:
    Code (Text):
    begin loop
      start/continue listing all elements
      if n has been listed
        return "n is in the set"
    end loop
     
  12. Jul 2, 2008 #11

    tgt

    User Avatar

    Nothing is a partial listing of the elements just like the empty set is a subset of any set.

    The big question is how do we know a given element is in the set.
     
  13. Jul 2, 2008 #12

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yes, nothing is a partial listing (as I said): that's why saying that a RE algorithm's output at any time is a partial listing can't be used as a definition of a RE algorithm. An algorithm that does nothing also returns a partial listing, but it isn't a RE algorithm for any nonempty set.

    An element is in a RE set iff it is eventually listed. The whole point of RE instead of R is that you can't necessarily fix the time it will take to tell whether an element is in the set.
     
  14. Jul 3, 2008 #13

    tgt

    User Avatar

    Is that because there is a possibility that the element might not be in the set in which case it would never halt?
     
  15. Jul 3, 2008 #14

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yes, something like that.
     
  16. Jul 9, 2008 #15

    tgt

    User Avatar

    Just found out that that diophantine sets are recursively enumerable. That implies that if there is an integer solution to a polynomial equation (over Z) then we will know. However not all polynomial equations have integer solutions. So for the ones that haven't got any, we will never know as one can keep check for roots, forever. Correct?

    However there is no way (no algorithm) to decide whether a given polynomial (over Z) has a root before an actual root is found.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Recursively enumerable?
  1. Transfinite recursion (Replies: 5)

Loading...