Normal numbers computable in Exponential time

VERÓNICA BECHER

Wadern

Seminario; Dagstuhl Seminar 12021 Computability Complexity and Randomness; 2012

Dagstuhl Scloss

It is fair to say that Borel's question on providing an example of an absolutely normal number (normal to every integer base) is still unresolved because the few known instances are not completely satisfactory: it is desirable that the number be easily computable, we would like to exhibit the number explicitly. Turing's algorithm and the computable reformulation of Sierpinski's work are the only known constructions of computable normal numbers. Unfortunately, they both require double exponentially many steps to produce a next digit of the expansion of a constructed number. The existence of normal numbers computable in simple exponential time is ensured by a theorem of Martin Strauss in 1997; however, no specific instances have yet been identified.