a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, .…
As we will have several uses for such an ordering, we will call it the proper
order.
An important consequence of the previous discussion is that Turing
machines are countable.
Theorem 10.3
The set of all Turing machines, although infinite, is countable.
Proof: We can encode each Turing machine using 0 and 1. With this encoding,
we then construct the following enumeration procedure.
1. Generate the next string in {0,1} + in proper order.
2. Check the generated string to see if it defines a Turing machine. If so, write
it on the tape in the form required by Definition 10.4. If not, ignore the
string.
3. Return to Step 1.
Since every Turing machine has a finite description, any specific machine will
eventually be generated by this process.
The particular ordering of Turing machines depends on the encoding we use;
if we use a different encoding, we must expect a different ordering. This is of no
consequence, however, and shows that the ordering itself is unimportant. What
matters is the existence of some ordering.
EXERCISES
1. Sketch an algorithm that examines a string in {0,1} + to determine whether or
not it represents an encoded Turing machine.
2. Give a complete encoding, using the suggested method, for the Turing