produce a method by which its elements can be written in some sequence. We
call such a method an enumeration procedure. Since an enumeration procedure is
some kind of mechanical process, we can use a Turing machine model to define
it formally.
Definition 10.4
Let S be a set of strings on some alphabet Σ. Then an enumeration procedure
for S is a Turing machine that can carry out the sequence of steps
with x i ∈ Γ* – {#},s i ∈ S, in such a way that any s in S is produced in a finite
number of steps. The state q s is a state signifying membership in S; that is,
whenever q s is entered, the string following # must be in S.
Not every set is countable. As we will see in the next chapter, there are some
uncountable sets. But any set for which an enumeration procedure exists is
countable because the enumeration gives the required sequence.
Strictly speaking, an enumeration procedure cannot be called an algorithm
since it will not terminate when S is infinite. Nevertheless, it can be considered a
meaningful process, because it produces well-defined and predictable results.
Example 10.3
Let Σ = {a, b, c}. We can show that the S =Σ + is countable if we can find an
enumeration procedure that produces its elements in some order, say in the order
in which they would appear in a dictionary. However, the order used in
dictionaries is not suitable without modification. In a dictionary, all words
beginning with a are listed before the string b. But when there are an infinite
number of a words, we will never reach b, thus violating the condition of
Definition 10.4 that any given string be listed after a finite number of steps.
Instead, we can use a modified order, in which we take the length of the
string as the first criterion, followed by an alphabetic ordering of all equal-length
strings. This is an enumeration procedure that gives the sequence