Recursively Enumerable

http://en.wikipedia.org/wiki/Recursively_enumerable

A set is recursively enumerable if either hold:

• There exists an algorithm for determining whether an element e is a member of the set that returns true for all members (and returns false or diverges for non-members);

• There exists an algorithm for constructing the set (one element at a time), such that:
  • Were the algorithm to run forever, each element of the set would be eventually enumerated
  • Each indiviual element is computed in bounded (finite) time.

Note that:

• All finite sets are recursively enumerable (they are also decideable, a stronger property). Many countably infinite sets are also recursively enumerable, though not all are. Sets with a cardinality greater than that of the natural numbers (such as the set of real numbers) are not recursively enumerable. While we can trivially verify whether any given number is a real number, the set of real numbers is not constructable.
  • The first part of that is badly worded, for any given real number, you've already said that it's a real, there's nothing to determine. I'm not sure what question was actually intended...whether a real is transcendental? Proving that either way is non-trivial, in general.
  • On the second part, absolutely, reals are not in general constructible. A constructible number is one that "can be represented by a finite number of additions, subtractions, multiplications, divisions, and finite square root extractions of integers". Rationals are therefore obviously constructible, some (but not all) algebraic irrationals are obviously constructible, and transcendentals are obviously not constructible.
  • Put another way, a simple explanation for the un-countability of the reals is by considering the transcendental numbers pi and the square root of two. Both would have to be generated in bounded time by some candidate algorithm, yet both have an infinite number of base-10 digits. Similarly, there is no way to specify both numbers in some special encoding to avoid the problem.
    • I think that's incorrect with respect to PI and 2^(1/2). Although a decimal representation of PI, being infinite, cannot be computed in finite time, I see no problem with adding PI to an enumeration by specifying its definition. I think, therefor, it's prerfectly reasonable to have an enumeration that includes PI and 2^(1/2). Of course, there are also an infinite number of real numbers that cannot be represented by a finite definition, these 2 just aren't among them.
      • So what the above paragraph means is that the set of computable numbers is recursively enumerable? -LasseHp

• Any set/language for which a PhraseStructuredGrammar? (or a less powerful grammar) exists is RecursivelyEnumerable.

• There are infinite sets which are recursively enumerable that have subsets which aren't; the trivial example is the set of all strings over an alphabet A, which is fully decideable; for example, the language described by the regular expression [ab]* is decideable (and thus RecursivelyEnumerable). There are subsets of [ab]* which are not.

• Any infinite set whose inverse is finite is RecursivelyEnumerable (and decideable); as comparing any element with the finite set will always terminate.

Sets which are infinite but RecursivelyEnumerable can be effectively dealt with using LazyEvaluation. Sets which aren't RecursivelyEnumerable cannot be.