INVESTIGADORES
FIGUEIRA Santiago
artículos
Título:
Turing's unpublished algorithm for normal numbers
Autor/es:
VERÓNICA BECHER; SANTIAGO FIGUEIRA; RAFAEL PICCHI
Revista:
THEORETICAL COMPUTER SCIENCE
Editorial:
Elsevier
Referencias:
Año: 2007 vol. 377 p. 126 - 138
ISSN:
0304-3975
Resumen:
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.
