Java Reference
In-Depth Information
we cannot analyze. This comes as a result of the fact that the Halting Problem is
unsolvable.
17.3.1
Uncountability
Before proving that the Halting Problem is unsolvable, we first prove that not all
functions can be implemented as a computer program. This must be so because the
number of programs is much smaller than the number of possible functions.
A set is said to be countable (or countably infinite if it is a set with an infinite
number of members) if every member of the set can be uniquely assigned to a
positive integer. A set is said to be uncountable (or uncountably infinite) if it is
not possible to assign every member of the set to its own positive integer.
To understand what is meant when we say “assigned to a positive integer,”
imagine that there is an infinite row of bins, labeled 1, 2, 3, and so on. Take a set
and start placing members of the set into bins, with at most one member per bin. If
we can find a way to assign all of the set members to bins, then the set is countable.
For example, consider the set of positive even integers 2, 4, and so on. We can
assign an integer i to bin i=2 (or, if we don't mind skipping some bins, then we can
assign even number i to bin i). Thus, the set of even integers is countable. This
should be no surprise, because intuitively there are “fewer” positive even integers
than there are positive integers, even though both are infinite sets. But there are not
really any more positive integers than there are positive even integers, because we
can uniquely assign every positive integer to some positive even integer by simply
assigning positive integer i to positive even integer 2i.
On the other hand, the set of all integers is also countable, even though this set
appears to be “bigger” than the set of positive integers. This is true because we can
assign 0 to positive integer 1, 1 to positive integer 2, -1 to positive integer 3, 2 to
positive integer 4, -2 to positive integer 5, and so on. In general, assign positive
integer value i to positive integer value 2i, and assign negative integer value i to
positive integer value 2i + 1. We will never run out of positive integers to assign,
and we know exactly which positive integer every integer is assigned to. Because
every integer gets an assignment, the set of integers is countably infinite.
Are the number of programs countable or uncountable? A program can be
viewed as simply a string of characters (including special punctuation, spaces, and
line breaks). Let us assume that the number of different characters that can appear
in a program is P. (Using the ASCII character set, P must be less than 128, but
the actual number does not matter). If the number of strings is countable, then
surely the number of programs is also countable. We can assign strings to the
bins as follows. Assign the null string to the first bin. Now, take all strings of
one character, and assign them to the next P bins in “alphabetic” or ASCII code
order. Next, take all strings of two characters, and assign them to the next P
2
bins,
again in ASCII code order working from left to right. Strings of three characters
