[Overview] [Previous] [Next]

Turing Machines Are Denumerable

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

(q5, a2, a3, R, q7)

can be represented as

11111011011101101111111

and the set of quintuple

{(q5, a2, a3, R, q7), (q2, a2, a2, R, q2)

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


Copyright 1996 by David Matuszek
Last modified Apr 1, 1996