Turing's unpublished algorithm for normal numbers

BECHER, VERÓNICA

Oaxaca México, 10 August 2006.

Conferencia; lenary invited talk, XIII Simposio Latinoamericano de Lógica Matemática, Oaxaca México, 10 August 2006.; 2006

UNAM, México

Charla plenaria Titulo: Turing´s unpublished algorithm for normal numbersI will speak about the recustruction we did of an unpublished manuscript of Alan Turing on absolutely normal numbers. In this manuscript Turing states two theorems with insufficient arguments and incomplete proofs. The first theorem is a recursively basedversion of Borel´s theorem saying that almost all real numbersare absolutely normal. The second theorem is an algorithm toproduce absolutely normal numbers, and it is based on the recursiveconstruction of the first theorem. We recreate Turing´s ideasin the most accurate way possible and we fill in the missingproofs giving complete arguments for the two theorems.Our motivation for this work was to make explicit the techniquesused by Turing in relation to normal numbers, especially becausethere are still no known general methods to prove normality ofgiven real numbers nor there are fast algorithms to constructabsolutely normal numbers.