[Overview] [Previous] [Next]

Turing Machines Are Denumerable

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

(q₅, a₂, a₃, R, q₇)

can be represented as

11111011011101101111111

and the set of quintuple

{(q₅, a₂, a₃, R, q₇), (q₂, a₂, a₂, R, q₂)

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, ₀) as there are possible Turing machines.