The Turing Guide

NOTES TO PAGES 431–438 | 525

10. H. Lebesgue, ‘Sur certaines démonstrations d’existence’, Bulletin de la Société Mathématique de
    France, 45 (1917), 132–44; W. Sierpiński, ‘Démonstration élémentaire du théorème de M. Borel sur
    les nombres absolument normaux et détermination effective d’un tel nombre’, Bulletin de la Société
    Mathématique de France, 45 (1917), 127–32.


11. V. Becher and S. Figueira. ‘An example of a computable absolutely normal number’, Theoretical
    Computer Science, 270 (2002), 947–58.


12. Turing (1936).


13. See the chapters by R. Soare, A. Nerode, and W. Sieg in Downey, R. (ed.), Turing’s Legacy, Cambridge
    University Press (2015).


14. Turing (1950).


15. Turing (1950).


16. This is easily seen for polynomials of one variable. For example, a non-zero cubic polynomial expres-
    sion such as ax^3 + bx^2 + cx + d can have at most three roots, so it can take the value zero at no more
    than three values of x. It is unlikely that a random choice would select one of these three values!


17. B. J. Copeland and O. Shagrir, ‘Turing versus Gödel on computability and the mind’, in B. J. Copeland,
    C. Posy, and O. Shagrir (eds), Computability: Gödel, Turing, Church and Beyond, MIT Press (2013),
    1–33.


18. Turing (c.1951).


19. R. Impagliazzo and A. Wigderson, ‘P = BPP if E requires exponential circuits: derandomizing the
    XOR lemma’, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC
    ’97), ACM (1997), 220–9.


20. M. Agrawal, N. Kayal, and N. Saxena, ‘PRIMES is in P’, Annals of Mathematics, 160 (2004), 781–93.


21. C. Schnorr and H. Stimm, ‘Endliche Automaten und Zufallsfolgen’, Acta Informatica, 1 (1972),
    345–59.


22. E. Mayordomo, ‘Construction of an absolutely normal real number in polynomial time’, Preprint
    (November 2012); V. Becher, P. Heiber, and T. A. Slaman, ‘A polynomial-time algorithm for comput-
    ing absolutely normal numbers’, Information and Computation, 232 (2013), 1–9.


23. For general introductions to the area of randomness and its relation to computability, see R. Downey
    and D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag (2010); A. Nies,
    Computability and Randomness, Oxford University Press (2009). For a more informal discussion as
    to the general theory of randomness, see H. Zenil (ed.), Randomness Through Computation: Some
    Answers, More Questions, World Scientific (2011); this has essays by leading experts in the area. For
    more on the mathematical (particularly, logical) developments stemming from Turing’s work, see
    R. Downey (ed.), Turing’s Legacy, Cambridge University Press (2014).

CHAPTER 40 TURING’S mENTOR, mAX NEwmAN (GRATTAN-GUINNESS)

1. The history of modern mathematical analysis is well covered; see, for example, N. H. Jahnke (ed.),
   A History of Analysis, American Mathematical Society (2003). A similar story obtains for complex-
   variable analysis; see U. Bottazzini, The Higher Calculus. A History of Real and Complex Analysis from
   Euler to Weierstrass, Springer (1986).


2. See G. H. Moore, Zermelo’s Axiom of Choice, Springer (1982).


3. See C. S. Roero and E. Luciano, ‘La scuola di Giuseppe Peano’, in C. S. Roero (ed.), Peano e la sua
   Scuola. Fra Matematica, Logica e Interlingua. Atti del Congresso Internazionale di Studi (Torino, 2008),
   Deputazione Subalpina di Storia Patria (2010), 1–212.


4. See I. Grattan-Guinness, The Search For Mathematical Roots, 1870–1940. Logics, Set Theories and the
   Foundations of Mathematics from Cantor through Russell to Gödel, Princeton University Press (2000),
   Chapters 8 and 9.


5. See V. Peckhaus, ‘Hilbert, Zermelo und die Institutionalisierung der mathematischen Logik in
   Deutschland’, Berichte zur Wissenschaftsgeschichte, 15 (1992), 27–38; W. Sieg, ‘Hilbert’s programs:
   1917–1922’, Bulletin of Symbolic Logic, 5 (1999), 1–44.