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.

Answer 1

The concept is best illustrated with examples and comparison to recursive sets and comparison of different definitions. So I will do just that: I give you examples first, then give you different (but equivalent) definitions.

First, note that technically we apply the adjective "recursively enumerable" (also known as "semidecidable") to sets of natural numbers. But this adjective can also apply to a set of integers, to a set of pairs of integers, to a set of Unicode strings. Note that any of those things (integers, pairs of integers, Unicode strings) can be stored in computer memory. (Things that cannot be stored in computer memory include arbitrary (infinite precision) real numbers and infinite sequences of 0s or 1s)

Example 1: The set of all prime numbers

You can write an algorithm that takes a natural number as input and returns an answer of yes or no (yes meaning "yes, that input is a prime", no meaning "no, that input isn't a prime."). This algorithm is easy to write. Very easy if you don't bother optimizing for better performance. Because you can write an algorithm that always finishes and gives an answer of yes or no, the set of all prime numbers is called a decidable set (also known as a recursive set). It's called decidable because you can decide whether a natural number is a prime or not. Note that if you want to prove that a set is a decidable set, you just need to come up with an algorithm that always finishes and gives correct answer and you don't need to optimize for performance. Let's not get into why it's called recursive.

Example 2. A prime gap is the difference between two successive prime numbers. For example, 13 is a prime, and the next prime is 17, and so their difference 4 is a prime gap. Our second example is the set of all prime gaps.

Can you write an algorithm to check whether a number is a prime gap or not? How about the following pseudo code?

input: x

set i to 1
loop
  check primeness of i, i+1, ..., i+x
  if only i and i+x among them are primes, return yes.
  otherwise, increment i by 1 and go to start of loop

The algorithm in the pseudo code has some good and some bad.

The bad: It will never finish if the input is not a prime gap. It never returns the answer of no.

The good: If it returns the answer of yes, you know for sure that the input is a prime gap, and vice versa.

This set is an example of a semidecidable set (also known as a recursively enumerable set). The algorithm will always give you a positive confirmation if you input a prime gap and wait long enough, but the algorithm never gives you a negative confirmation if you input a number that is not a prime gap.

Definition: A set is a semidecidable set if there is an algorithm that takes an input and that either returns yes or returns no or never returns (due to infinite loop or error) and if that algorithm returns yes whenever given an input in the set, and if that algorithm never returns yes whenever given an input not in the set.

All circles are ellipses and all decidable sets are semidecidable sets.

With some thought, you may realize that whether the algorithm is allowed to return no sometimes correctly doesn't really matter for the definition in the end. With more thought, you may also realize that whether you allow error or not doesn't matter for the definition either. These realizations allow us to come up with an equivalent, simpler, but slightly less intuitive definition:

The less intuitive definition: A set is a semidecidable set if there is an algorithm that takes an input and if this algorithm returns (i.e. the program terminates) if and only if given an input in the set.

Now let's talk about listable sets. A set is a listable set if there is an algorithm that prints all elements in the set (and nothing else). Of course, that algorithm never finishes if it has to print infinitely many elements. With some thoughts, you may realize that whenever you have an algorithm to print all the numbers in the set, sometimes printing the same number more than once, you can modify the algorithm so that it prints all the numbers just once. Notice that the definition does NOT say that the algorithm must print the smallest element first, and then the second smallest element, and so on. Why am I talking about listable sets?

Theorem: A set is a listable set if and only if it is a semidecidable set.

Let's not go into why that is true (maybe make an SO question for that?), but let me just mention that this is the reason for the phrase "recursively enumerable": you can enumerate the set in the sense that you can list all the elements one by one, and "recursively" just means "with an algorithm".

How about an example that doesn't involve numbers?

Example 3. The set of all ASCII strings that is a Python function definition taking no argument and is guaranteed to return. (For simplicity, let's also exclude Python functions invoking libraries that do some hardware-specific stuff)

This set is a semidecidable set because you can make a semi-deciding algorithm. The algorithm just has to emulate Python to run the Python function and then wait until it finishes. If the Python function ever returns in your emulation, your algorithm returns yes. That's the algorithm. Can we do better than that algorithm? Yes, make an algorithm that detects infinite loop in some cases and return no. Can you come up with an algorithm that never fails to detect infinite loop? If you can come up with such an algorithm, this set would be a decidable set. Sadly, there is no such algorithm and we can prove that.

Example Finale. When Stalin was in power, the set of good Soviet government policies were like a semidecidable set. There was someone who was one of the advisers for the government. Stalin would ask him, "I have an idea for a new policy. The idea is blah blah blah. Is this a good policy?" A simple yes or no question. He would answer yes after a few days of analysis showed that the policy was indeed good. What if the policy was bad? He had the principle of "don't lie ever", but he also knew what happens to those who say no to Stalin. Whenever Stalin said "Have you decided whether the policy is good? It's been months since I asked for your opinion on that." and he would say "Give me more time to think, comrade Stalin."

Answer 2

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 3

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.