428 | 39 TURING AND RANDOmNESS
1/4 = 0.020202. . . . From now on we will drop the decimal point and concern ourselves with
infinite sequences of digits.
Normal numbers
In 1909 the French mathematician Émile Borel (1871–1956) was interested in number
sequences that satisfy the ‘law of large numbers’ (Fig. 39.1).^1 This law says that if we repeat an
experiment many times, then the average number of successes should be the expected value;
for example, if we toss a fair coin many times we would expect to get a head approximately half
of the time, and if we toss a fair die we would expect to throw a six in about one-sixth of the
tosses. In base 10 this law says that the frequency of choosing a digit from 0 to 9 is exactly what
we would expect in the limit—namely, 1/10. But what do we mean by ‘in the limit’?
Base 2 corresponds to tossing a coin. Over time, we would expect as many heads as tails, but
this is only the eventual long-term behaviour. If we toss a head, the next toss will be independ-
ent of this toss, so with probability 1/2 we would again get a head. The law of large numbers tells
us that if the coin is fair it will all ‘even out in the long run’.
Now suppose that we continue to toss coins for ever—that is, we consider an infinite sequence
of coin tosses. At any stage we can see how we are getting on by comparing the number of
heads obtained so far with the total number of times we have tossed the coin—that is, after k
tosses we divide the number of heads obtained by k; for example, if we toss a coin 100 times
and get 47 heads, then the ratio of heads obtained is 47/100. If the coin were fair, then this
ratio should become increasingly closer to 1/2 as we increase the number of tosses indefinitely;
figure 39.1 Émile Borel.
Emile Borel, 1932 by Agence de Presse Mondial
Photo-Presse, Bibliothèque Nationale de France.
Licensed under public domain via Wikimedia
Commons.