A stronger version of countable (unless you only believe in constructive mathematics).
A set is countable if it has a numbering (a one-to-one correspondence with the natural numbers).
A set is recursively enumerable if there exist instructions for numbering them.
Huh, wait - what's the difference? An example:
Consider some notational convention for Turing machines that uses only ASCII symbols and supports at least two states and at least two tape symbols, and supports
Any textbook notation will do, as long as you specify exactly how to denote it with ASCII (even whitespace matters, if you're going to allow that).
You can probably normalize by removing all whitespace and putting the elements of all sets in lexicographical order.
- mechanical validation: instructions to verify, given any sequence of ASCII symbols, whether it denotes a Turing machine;
- normalization: instructions to rewrite any denotation of a Turing machine into a unique form (e.g. such that any two denotations of the same machine produce the same result).
There are 128 (or 256, whatever) ASCII characters, pre-numbered for your convenience; this gives us a way to effectively number all ASCII strings in lexicographical order, which proves that they are recursively enumerable.
The set of normalized notations of Turing machines according to your convention is also recursively enumerable: for instance, generate all ASCII strings in lexicographical order, but number only those that denote Turing machines and normalize to themselves. This numbering effectively numbers the Turing machines themselves (over your chosen alphabet) because there is a one-to-one correspondence between the machines and their normalized notations.
Now consider the numbering that numbers, in the same order, the normalized notations of all Turing machines that do not halt on the empty input. It defines a one-to-one correspondence between the natural numbers and this set of notations, and because they are normalized, with the set of such machines itself, proving that these sets are both countable - while (as ariels correctly writes) the latter set is not recursively enumerable. We've found a numbering that is well-defined (according to standard mathematics) but cannot be effectively executed, nor can any other numbering of the same set.
Don't worry: Kronecker and Brouwer are dead. Do feel a little guilty.