DOwNEy | 435
quickly. In a celebrated result, first announced in 2002, Manindra Agrawal, Neeraj Kayal, and
Nitin Saxena gave a non-randomized polynomial-time algorithm for primality testing.^20
where does this all lead?
There is much ongoing work on absolute normality, since it is a natural number-theoretical
notion. In terms of its relationship with randomness, one can show that normality is really a
precise calibration of randomness. Normality corresponds to a kind of randomness property
called the ‘finite-state Hausdorff dimension’, where we look at the behaviour of betting strat-
egies that are controlled by ‘finite state gamblers’. These are strategies controlled by ‘finite state
machines’. Finite state machines are widely used in computer science: these, the most basic of all
machines, can be thought of as memory-less machines that plod from one internal state to the
next, processing the bits of the input purely on the basis of the bit being read and the internal
state. In the early 1970s Schnorr and Stimm proved that a sequence of numbers in base b is
normal to base b if and only if the finite-state Hausdorff dimension of the sequence is 1: this is
a statement about the complexity of the initial segments of the sequence.^21 Meanwhile, Elvira
Mayordomo and Jack Lutz, and independently, Verónica Becher, Pablo Heiber, and Theodore
Slaman, have shown that it is possible to construct such sequences that are quite simple, in that
we can compute each bit of the sequence in polynomial time.^22 There has been a great amount
of work on algorithmic randomness and its applications to such areas as algorithm design,
understanding analysis in mathematics, Brownian motion, ergodic theory, Markov chain the-
ory, and physics.^23