Normal number

In mathematics, a real number is said to be simply normal in an integer base b if its infinite sequence of digits is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b. A number is said to be normal in base b if, for every positive integer n, all possible strings n digits long have density b−n. Intuitively, a number being simply normal means that no digit occurs more frequently than any other. If a number is normal, no finite combination of digits of a given length occurs more frequently than any other combination of the same length. A normal number can be thought of as an infinite sequence of coin flips (binary) or rolls of a die (base 6). Even though there will be sequences such as 10, 100, or more consecutive tails (binary) or fives (base 6) or even 10, 100, or more repetitions of a sequence such as tail-head (two consecutive coin flips) or 6-1 (two consecutive rolls of a die), there will also be equally many of any other sequence of equal length. No digit or sequence is "favored". A number is said to be normal (sometimes called absolutely normal) if it is normal in all integer bases greater than or equal to 2. While a general proof can be given that almost all real numbers are normal (meaning that the set of non-normal numbers has Lebesgue measure zero), this proof is not constructive, and only a few specific numbers have been shown to be normal. For example, any Chaitin's constant is normal (and uncomputable). It is widely believed that the (computable) numbers , pi, and e are normal, but a proof remains elusive. Let Σ be a finite alphabet of b-digits, ^ω the set of all infinite sequences that may be drawn from that alphabet, and ^∗ the set of finite sequences, or strings. Let ∈ ^ω be such a sequence. For each a in Σ let _(, ) denote the number of times the digit a appears in the first n digits of the sequence S. We say that S is simply normal if the limit for each a. Now let w be any finite string in ^∗ and let _(, ) be the number of times the string w appears as a substring in the first n digits of the sequence S.