What are recursively enumerable sets?

Question

There seems to be a lot of discussion (and confusion) regarding the Wikipedia article on the topic. Other results Google throws up are not available for free public use.

I would be interested in what you folks have to say. Thanks!

Answer 1

A recursively enumerable set is a set where there is a partially computable algorithm for deciding if an element is contained in the set or not (it can be computed but it isn't necessarily going to terminate)

For example, determining if an item isn't in the mandlebrot set is recursively enumerable.

Answer 2

Here's one definition: A recursively enumerable set is a set where you can write a program that will output each element in the set: E1, E2, E3... it's okay if this program never stops.

People usually talk about this in the context of languages. A recursively enumerable language is a language where you could write a program that writes out every valid string in that language. A language is just a set of strings, so "the set of all prime numbers in base 10" is a valid language.

Imagine, however, that you don't want to generate all the strings in a language or all the elements in a set. You just want to check and see if a given string is in the language. The problem is that you would never know for sure that the string wasn't in your language. If you needed to write a compiler for this language, your compiler would work just fine on valid inputs, but invalid inputs would make your compiler hang forever as it searches through an infinite list for something that isn't there.

The set of "recursive languages" or "recursive sets" are sets where you can write a program that tells you whether the given input is in the set or not. All recursive languages are also recursively enumerable because you can just enumerate every string, and then output it if it's in your set. Recursive languages are also called decidable because you can decide for sure if an element is in it or not. This is not the case with the more general recursively enumerable sets.

In general, it is easier to prove that a set or language is recursively enumerable or is recursive, but harder to prove that it is not recursive but recursively enumerable.