Turing machines can be represented in binary notation. For example, the quintuple

(q

_{5}, a_{2}, a_{3}, R, q_{7})

can be represented as

11111011011101101111111

and the set of quintuple

{(q

_{5}, a_{2}, a_{3}, R, q_{7}), (q_{2}, a_{2}, a_{2}, R, q_{2})

can be represented as

11111011011101101111111011011011011011.

Not every binary number represents a Turing machine. For example, a Turing machine can only move in two directions (L and R), so a sequence ...01110... for direction would not be meaningful.

Suppose we count in binary, checking each number in turn to see whether it represents a
valid Turing machine. We assign 1 to the first valid Turing machine we encounter (that is,
the one represented by the smallest binary number), 2 to the second such machine, and so
on. Since *any* Turing machine can be represented in binary, it should be clear that
this establishes a one-to-one correspondence between Turing machines and the natural
numbers. Hence, Turing machines are denumerable.

By the way, C programs are also denumerable. Think of a C program as a number in base 128 (the number of ASCII characters) and use the same proof.

Thus there are the same number of possible C programs (that is, _{0})
as there are possible Turing machines.

Copyright © 1996 by David Matuszek

Last modified Apr 1, 1996