Editing Normal number (section)

== Connection to finite-state machines ==
Agafonov showed an early connection between [[finite-state machine]]s and normal sequences: every infinite subsequence selected from a normal sequence by a [[regular language]] is also normal. In other words, if one runs a finite-state machine on a normal sequence, where each of the finite-state machine's states are labeled either "output" or "no output", and the machine outputs the digit it reads next after entering an "output" state, but does not output the next digit after entering a "no output state", then the sequence it outputs will be normal.{{sfn|Agafonov|1968}}

A deeper connection exists with finite-state gamblers (FSGs) and information lossless finite-state compressors (ILFSCs).

* A '''finite-state gambler''' (a.k.a. '''finite-state [[martingale (probability theory)|martingale]]''') is a finite-state machine over a finite alphabet <math>\Sigma</math>, each of whose states is labelled with percentages of money to bet on each digit in <math>\Sigma</math>. For instance, for an FSG over the binary alphabet <math>\Sigma = \{0,1\}</math>, the current state ''q'' bets some percentage <math>q_0 \in [0,1]</math> of the gambler's money on the bit 0, and the remaining <math>q_1 = 1-q_0</math> fraction of the gambler's money on the bit 1. The money bet on the digit that comes next in the input (total money times percent bet) is multiplied by <math>|\Sigma|</math>, and the rest of the money is lost. After the bit is read, the FSG transitions to the next state according to the input it received. A FSG ''d'' '''succeeds''' on an infinite sequence ''S'' if, starting from $1, it makes unbounded money betting on the sequence; i.e., if<math display="block">\limsup_{n\to\infty} d(S \upharpoonright n) = \infty,</math>where <math>d(S \upharpoonright n)</math> is the amount of money the gambler ''d'' has after reading the first ''n'' digits of ''S'' (see [[limit superior]]).
* A '''finite-state compressor''' is a finite-state machine with output strings labelling its [[state transition table|state transitions]], including possibly the empty string. (Since one digit is read from the input sequence for each state transition, it is necessary to be able to output the empty string in order to achieve any compression at all). An information lossless finite-state compressor is a finite-state compressor whose input can be uniquely recovered from its output and final state. In other words, for a finite-state compressor ''C'' with state set ''Q'', ''C'' is information lossless if the function <math>f: \Sigma^* \to \Sigma^* \times Q</math>, mapping the input string of ''C'' to the output string and final state of ''C'', is [[Injective function|1–1]]. Compression techniques such as [[Huffman coding]] or [[Shannon–Fano coding]] can be implemented with ILFSCs. An ILFSC ''C'' '''compresses''' an infinite sequence ''S'' if<math display="block">\liminf_{n\to\infty} \frac{|C(S \upharpoonright n)|}{n} < 1,</math>where <math>|C(S \upharpoonright n)|</math> is the number of digits output by ''C'' after reading the first ''n'' digits of ''S''. The [[data compression ratio|compression ratio]] (the [[limit inferior]] above) can always be made to equal 1 by the 1-state ILFSC that simply copies its input to the output.

Schnorr and Stimm showed that no FSG can succeed on any normal sequence, and Bourke, Hitchcock and Vinodchandran showed the [[conversion (logic)|converse]]. Therefore:

{{block indent|A sequence is normal if and only if there is no finite-state gambler that succeeds on it.}}

Ziv and Lempel showed:

{{block indent|A sequence is normal if and only if it is incompressible by any information lossless finite-state compressor}}

(they actually showed that the sequence's optimal compression ratio over all ILFSCs is exactly its ''[[information entropy|entropy]] rate'', a quantitative measure of its deviation from normality, which is 1 exactly when the sequence is normal). Since the [[LZ78|LZ compression algorithm]] compresses asymptotically as well as any ILFSC, this means that the LZ compression algorithm can compress any non-normal sequence.{{sfn|Ziv|Lempel|1978}}

These characterizations of normal sequences can be interpreted to mean that "normal" = "finite-state random"; i.e., the normal sequences are precisely those that appear random to any finite-state machine. Compare this with the [[algorithmically random sequence]]s, which are those infinite sequences that appear random to any algorithm (and in fact have similar gambling and compression characterizations with [[Turing machine]]s replacing finite-state machines).