CHAPTER 39
Turing and randomness
rod downey
I
n an unpublished manuscript Turing anticipated by nearly thirty years the basic ideas
behind the theory of algorithmic randomness, using a computationally constrained ver-
sion of ‘measure theory’ to answer a question posed by Émile Borel in number theory:
this question concerned constructing what are called ‘absolutely normal’ numbers. In this
chapter we explain what these mysterious terms mean, and what Turing did.
Repeated decimals in fractions
Mathematicians have always been fascinated with patterns in numbers. At an early stage in
our education we learn about the special nature of decimal expansions of ‘rational numbers’,
fractions that we can write in the form m/n, for some whole numbers m and n with n ≠ 0. The
Greeks proved that some numbers, such as √2,^3 √7 and √2 + √3 are not rational—indeed, it can
be shown that ‘most’ numbers (in a precise mathematical sense) are irrational.
It can be shown that a real number is rational if and only if it has a finite decimal expan-
sion, or a decimal expansion that repeats from some point onwards; for example, 1/4 = 0.25
and 3/7 = 0.428571 428571 428571.... Note that we can also think of 1/4 as a repeating deci-
mal, 0.25000000. . . ; we can also write it as 0.24999999 ... , but for simplicity we ignore such
ambiguities.
We can also count using bases different from 10. The binary system uses base 2, where each
place in the representation corresponds to a power of 2; for example, just as 2301 in the decimal
system refers to (2 × 10^3 ) + (3 × 10^2 ) + (0 × 10^1 ) + (1 × 10^0 ), so in base 2 the decimal number 13 =
(1 × 2^3 ) + (1 × 2^2 ) + (0 × 2^1 ) + (1 × 2^0 ) is represented by 1101. In base 3 we use only the numbers
0, 1, 2 and express numbers using powers of 3, so the decimal number 25 = (2 × 3^2 ) + (2 × 3^1 )
+ (1 × 3^0 ) is represented by 221. Note that when we use bases larger than 10 we have to invent
extra symbols to represent the larger ‘digits’; for example, in base 12 we might use the digits 0,
1, 2, . . . , 9, T, E, with T and E representing ‘ten’ and ‘eleven’.
The above result about repeating patterns in the decimal representation of rational numbers
remains true if we change the base from base 10 to any other base. For instance, in base 3,