Event Detail

Fri Sep 6, 2013
60 Evans Hall, 4–6 PM
Logic Colloquium
Theodore A. Slaman (UC Berkeley)
On Normal Numbers

A real number is simply normal in base b if in its base-b expansion each digit appears with asymptotic frequency 1/b. It is normal in base b if it is simply normal in all powers of b, and absolutely normal if it is simply normal in every integer base. By a theorem of E. Borel, almost every real number is absolutely normal. We will present three main results. We give an efficient algorithm, which runs in nearly quadratic time, to compute the binary expansion of an absolutely normal number. We demonstrate the full logical independence between normality in one base and another. We will give a necessary and sufficient condition on a set of natural numbers M for there to exist a real number X such that X is simply normal to base b if and only if b is an element of M.