zbMATH — the first resource for mathematics

Turing’s unpublished algorithm for normal numbers. (English) Zbl 1117.03051
Summary: In an unpublished manuscript, Alan Turing gave a computable construction to show that absolutely normal real numbers between 0 and 1 have Lebesgue measure 1; furthermore, he gave an algorithm for computing instances in this set. We complete his manuscript by giving full proofs and correcting minor errors. While doing this, we recreate Turing’s ideas as accurately as possible. One of his original lemmas remained unproved, but we have replaced it with a weaker lemma that still allows us to maintain Turing’s proof idea and obtain his result.

03D80 Applications of computability and recursion theory
11K16 Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.
11Y16 Number-theoretic algorithms; complexity
03-03 History of mathematical logic and foundations
11-03 History of number theory
Biographic References:
Turing, Alan
Full Text: DOI
[1] Ambos-Spies, Klaus; Mayordomo, Elvira, Resource-bounded measure and randomness, (), 1-47 · Zbl 0877.68055
[2] Ambos-Spies, Klaus; Terwijn, Sebastiaan; Zheng, Xizhong, Resource bounded randomness and weakly complete problems, Theoretical computer science, 172, 195-207, (1997) · Zbl 0912.68069
[3] Bailey, David H.; Crandall, Richard E., Random generators and normal numbers, Experimental mathematics, 11, 4, 527-546, (2004) · Zbl 1165.11328
[4] Becher, Verónica; Figueira, Santiago, An example of a computable absolutely normal number, Theoretical computer science, 270, 947-958, (2002) · Zbl 1002.11064
[5] Borel, Émile, LES probabilités dénombrables et leurs applications arithmétiques, Rendiconti del circolo matematico di Palermo, 27, 247-271, (1909) · JFM 40.0283.01
[6] Borel, Émile, Leçons sur la thèorie des fonctions, (1914), Gauthier Villars · Zbl 0035.33701
[7] Borel, Émile, La définition en mathématiques, () · Zbl 0024.42501
[8] Champernowne, David G., The construction of decimals in the scale of ten, Journal of the London mathematical society, 8, 254-260, (1933) · JFM 59.0214.01
[9] Copeland, Arthur H.; Erdös, Paul, Note on normal numbers, Bulletin American mathematical society, 52, 857-860, (1946) · Zbl 0063.00962
[10] Santiago Figueira, Aspects of randomness, Ph.D. Thesis, Universidad de Buenos Aires, May 2006
[11] Harman, Glyn, ()
[12] Harman, Glyn, One hundred years of normal numbers, (), 149-166 · Zbl 1062.11052
[13] Kuipers, Lauwerens; Niederreiter, Harald, Uniform distribution of sequences, (1974), Wiley Interscience New York · Zbl 0301.10031
[14] Sierpiński, Wacław, 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, 127-132, (1917) · JFM 46.0276.02
[15] Turing, Alan M., A note on normal numbers, (), 117-119
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.