DOwNEy | 429
mathe matically, we say that this ratio ‘tends to the limit 1/2’. Similarly, if we change tack and
count tails instead of heads, then the ratio of tails also tends to the limit 1/2 as the number of
tosses increases indefinitely. Since we get the same limit whether we choose heads or tails, we
say that the sequence of tosses is normal to base 2.
The same situation holds for other bases. When we toss a fair die, then the ratio of sixes
obtained tends to the limit 1/6 as the number of tosses increases indefinitely. But we get the
same limit when we count the number of threes, or fives, or any other number, so the sequence
of tosses is normal to base 6. More generally, if we are tossing a fair n-sided die, then in the limit
each number should appear 1/n times and the sequence of tosses is normal to base n.
In his 1909 paper, Borel defined a real number (represented as an infinite sequence of digits)
to be ‘absolutely normal’ if it is normal when written in any base. This means that, whatever
base we are using, no digit, or combination of digits, can occur more frequently than any other.
It follows that no rational number can be absolutely normal since, when written in any base,
it must contain a repeating pattern of digits. But, as Borel observed, ‘almost every’ irrational
number is absolutely normal. This means (in a way that can be made mathematically precise)
that if we throw a dart at the line it would, with probability 1, land on an irrational normal
number.^2
Turing’s work on normal numbers was motivated by the following two questions asked by
Borel:
• Can there be an irrational number that is normal to one base but not to another?
• Can one give an explicit construction of an absolutely normal number?We are more concerned here with the second question.
We might guess that certain irrational numbers, such as π, e, and log 2, are absolutely normal:
they are certainly explicit, in our sense, since their constructions are well known—and in the
case of π a construction has been known since ancient times: the Babylonians already had a
method for estimating π four thousand years earlier. There are also irrational numbers, such as
√2,^3 √7 and √2 + √3, which are called ‘algebraic irrational numbers’, since they are solutions of
algebraic equations involving only whole numbers: for example, √2 is a solution of the algebraic
equation x^2 = 2,^3 √7 is a solution of x^3 = 7, and √2 + √3 is a solution of x^4 + 1 = 10x^2. It has been
conjectured that every algebraic irrational number is absolutely normal, but any attempts to
prove this have been as pitiful as they could possibly be: no explicit example has ever been
proved to be normal, even to a single base!
From a modern point of view, we can think of a number as being explicit if we can give an
algorithm that—when told a desired degree of precision—will compute the number to that
degree of precision. This is called ‘rapid convergence’. Actually, this modern point of view stems
directly from Turing’s 1936 paper. This is Turing’s definition of a computable real number.
Another way of constructing normal numbers was discovered in 1933 by Turing’s friend
David Champernowne (1912–2000), while still an undergraduate (he later held chairs
in statistics and economics at both Cambridge and Oxford). What you do is simply to
write the digits in increasing order; for example, in base 10 the Champernowne number is
0.123456789101112131415. . . . This can be done to any base, and the resulting numbers are
easily proved to be normal in the base in which they are written—and we believe, but have no
idea to how to prove, that they are normal when expressed in terms of any other base.
In place of the numbers 1, 2, 3, . . . we could have taken some other increasing sequence and
used it to define a similar number; for example, if we take the prime numbers 2, 3, 5, 7, 11, . . .