[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


and the set of quintuple

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

can be represented as


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