DOwNEy | 431
Turing’s work
We recall that Turing was interested in absolute normality. Clearly, a random sequence should
be absolutely normal. Why is this? As we have already seen, if the frequency of 1s is less than
that of the 0s, then we could easily have a betting strategy to allow us to make infinite capital,
in the limit. Now suppose that an infinite binary sequence is not normal in base 10, and (for
example) that the frequency of 5s is higher than expected: then in base 10 we could formulate a
betting strategy to exploit that fact.
Suppose that I told you that every third bit of a sequence was a 1. You could make money as
follows. On the first bit don’t bet, on the second don’t bet, and then put all your capital on 1 for
the third bet, and repeat. Similarly, if I knew that the frequency of 1s was always less than that
of 0s for the sequence, then it is again possible to formulate a strategy to make infinite capital.
There are relatively easy computable translations from one base to another. For example, 0.5
(base 10) corresponds to 0.1 (base 2). In general, you get ‘blocks’. As an illustration: 0.6 (base 10)
can be converted to base 2 as follows. First multiply by 2, to get 1.2. Keep the 1. Now multiply
0.2 by 2 and get 0.4. Keep the 0. Multiply 0.4 by 2 and get 0.8, keeping the 0. Repeat, getting 1.6,
and keep the 1. Thus our binary expansion of 0.6 will begin: 0.1001; and since the next thing to
be processed will be 0.6, the same pattern will repeat forever.
Although this process is a bit more complicated in the case of infinite expansions, there is
always a very tight relationship between an expansion in one base and one in another, and it
is possible to exploit this to prove that randomness in one base translates into randomness in
another. Roughly speaking, for two bases p and q, there is always a computable function f which
converts the first n bits of a sequence in base p into f(n) bits of the sequence in base q. If I have a
way of winning infinite capital in one base, I could use that to bet in the other base.
In his unpublished manuscript ‘A note on normal numbers’, Turing attacked the question
of an explicit construction of an absolutely normal number by interpreting ‘explicit’ to mean
‘computable’, and presented the best answer to date to Borel’s second question: an algorithm
that produces absolutely normal numbers.^7 This early proof of existence of computable normal
numbers remained largely unknown because Turing’s manuscript was not published until 1997,
in his Collected Works, where the editorial notes claimed that Turing’s proof was inadequate and
speculated that the theorem might be false. In 2007, Verónica Becher, Santiago Figueira, and
Rafael Picchi reconstructed and completed Turing’s manuscript, correcting minor errors while
preserving his ideas as accurately as possible.^8
As Verónica Becher has remarked, the very first examples of normal numbers were published
independently by Henri Lebesgue and Wacław Sierpiński in 1917;^9 both appeared in the same
journal issue, but Lebesgue’s example dated back to 1909, immediately after Borel’s question.^10
The examples of Sierpiński and Lebesgue can also be modified to give computable (that is,
explicit) solutions to Borel’s question. This can be done by giving a computable reformulation
of the original constructions of 1917, as shown by Becher and Figueira.^11 Until recently these,
together with Turing’s algorithm, were the only known constructions of computable normal
numbers. Turing was unaware of these earlier constructions, but in any case what is interesting
is the way that Turing solved Borel’s question.
What did Turing’s construction do? His paper claims the following:
Although it is known that almost all numbers are [absolutely] normal no example of [an abso-
lutely] normal number has ever been given. I propose to show how [absolutely] normal numbers
may be constructed and to prove that almost all numbers are [absolutely] normal constructively.