Understanding Recursively Enumerable Sets in Algorithms

[tgt]

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.

 

[CRGreathouse]

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.

 

[tgt]

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.

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

 

[CRGreathouse]

"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 can generate a "no", but it may run forever instead. It's not important -- the algorithm doesn't need to even return a "no".

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

Yes.

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?

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.

 

[tgt]

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

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.

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.

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?

 

[CRGreathouse]

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.

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.

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?

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.

 

[tgt]

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.

 

[CRGreathouse]

With a recursive set, you can always test for membership in finite time. This is not the case with RE sets.

 

[tgt]

With a recursive set, you can always test for membership in finite time. This is not the case with RE sets.

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?

 

[CRGreathouse]

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?

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.

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?

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:

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:

begin loop
  start/continue listing all elements
  if n has been listed
    return "n is in the set"
end loop

 

[tgt]

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.

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.

 

[CRGreathouse]

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.

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.

 

[tgt]

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.

Is that because there is a possibility that the element might not be in the set in which case it would never halt?

 

[CRGreathouse]

Is that because there is a possibility that the element might not be in the set in which case it would never halt?

Yes, something like that.

 

[tgt]

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.