Automatic Kolmogorov complexity and
normality revisited
Alexander Shen∗

arXiv:1701.09060v3 [] 28 Aug 2017

August 29, 2017

Abstract
It is well known that normality (all factors of a given length appear in an infinite sequence with the same frequency) can be described as incompressibility via finite automata.
Still the statement and the proof of this result as given by Becher and Heiber [4] in terms of
“lossless finite-state compressors” do not follow the standard scheme of Kolmogorov complexity definition (an automaton is used for compression, not decompression). We modify
this approach to make it more similar to the traditional Kolmogorov complexity theory
(and simpler) by explicitly defining the notion of automatic Kolmogorov complexity and
using its simple properties. Other known notions (Shallit–Wang [16], Calude–Salomaa–
Roblot [8]) of description complexity related to finite automata are discussed (see the last
section).
As a byproduct, this approach provides simple proofs of classical results about normality (equivalence of definitions with aligned occurrences and all occurrences, Wall’s theorem saying that a normal number remains normal when multiplied by a rational number,
and Agafonov’s result saying that normality is preserved by automatic selection rules).

1 Introduction
What is an individual random object? When could we believe, looking at an infinite sequence
α of zeros and ones, that α was obtained by tossing a fair coin? The minimal requirement is
that zeros and ones appear “equally often” in α : both have limit frequency 1/2. Moreover, it
is natural to require that all 2k bit blocks of length k appear equally often. Sequences that have
this property are called normal (see the exact definition in Section 3; a historic account can be
found in [4, 6]).
Intuitively, a reasonable definition of an individual random sequence should require much
more than just normality; the corresponding notions are studied in the algorithmic randomness theory (see [9, 13] for the detailed exposition, [18] for a textbook and [17] for a short
survey). The most popular definition is called Martin-Löf randomness; the classical Schnorr–
Levin theorem says that this notion is equivalent to incompressibility: a sequence α is MartinLöf random if an only if prefixes of α are incompressible (do not have short descriptions). See
again [9, 13, 18, 17] for exact definitions and proofs.
LIRMM, CNRS and University of Montpellier, France. On leave from IITP RAS, Moscow. Supported by
ANR-15-CE40-0016 RaCAF grant. Part of the work was done while visiting National Research University High
School of Economics, Moscow. E-mail: sasha.shen@gmail.com or alexander.shen@lirmm.fr
∗

1

It is natural to expect that normality, being a weak randomness property, corresponds to
some weak incompressibility property. The connection between normality and finite-state computations was noticed long ago, as the title of [1] shows. This connection led to a characterization of normality as “finite-state incompressibility” (see [4]). However, the notion of
incompressibility that was used in [4] does not fit well the general framework of Kolmogorov
complexity (finite automata are considered as compressors, while in the usual definition of Kolmogorov complexity we restrict the class of allowed decompressors).
In this paper we give a definition of automatic Kolmogorov complexity that restricts the
class of allowed decompressors and is suitable for the characterization of normal sequences as
incompressible ones. This definition and its properties are considered in Section 2. In Section 3
we recall the notion of normal sequence. Then in Section 4 we provide a characterization
of normal sequences in terms of automatic Kolmogorov complexity. In Section 5 we show
how this characterization can be used to give simple proofs for classical results about normality,
including Wall’s theorem (normal numbers remain normal when multiplied by a rational factor).
In a similar way one can prove Agafonov’s result [1], but we need to modify the definition of
complexity using pairs as descriptions. This is done in Section 6. Finally, in Section 7 we
compare our definition of automatic complexity with other similar notions.

2 Automatic Kolmogorov complexity
Let us recall the definition of algorithmic (Kolmogorov) complexity. It is usually defined in the
following way: C(x), the complexity of an object x, is the minimal length of its “description”.
(We assume that both objects and descriptions are binary strings; the set of binary strings is
denoted by B∗ , where B = {0, 1}.) Of course, this definition makes sense only after we explain
which type of “descriptions” we consider, but most versions of Kolmogorov complexity can be
described according to this scheme [19]:
Definition 1. Let D ⊂ B∗ × B∗ be a binary relation; we read (p, x) ∈ D as “p is a D-description
of x”. Then complexity function CD is defined as
CD (x) = min{|p| : (p, x) ∈ D},
i.e., as the minimal length of a D-description of x.
Here |p| stands for the length of a binary string p and min(∅) = +∞, as usual. We say that
D is a description mode and CD (x) is the complexity of x with respect to the description mode D.
We get the original version of Kolmogorov complexity (“plain complexity”) if we consider
all computable functions as description modes, i.e., if we consider relations D f = {(p, f (p))}
for arbitrary computable partial functions f as description modes. Equivalently, we may say
that we consider (computably) enumerable relations D that are graphs of functions (for every p
there exists at most one x such that (p, x) ∈ D; each description describes at most one object).
Then the Kolmogorov–Solomonoff optimality theorem says that there exists an optimal D in
this class that makes CD minimal (up to an O(1) additive term). (We assume that the reader
is familiar with basic properties of Kolmogorov complexity, see, e.g., [11, 18]; for a short
introduction see also [17].)
Note that we could get a trivial CD if we take, e.g., the set of all pairs as a description mode
D (in this case all strings have complexity zero, since the empty string describes all of them).
So we should be careful and do not consider description modes where the same string describes
too many objects.
2

To define our class of descriptions, let us first recall some basic notions related to finite
automata. Let A and B be two finite alphabets. Consider a directed graph G whose edges are
labeled by pairs (a, b) of letters (from A and B respectively). We also allow pairs of the form
(a, ε ), (ε , b), and (ε , ε ) where ε is a special symbol (not in A or B) that informally means “no
letter”. For such a graph, consider all directed paths in it (no restriction on starting or final
points), and for each path concatenate all the first and all the second components of the pairs; ε
is replaced by an empty word. For each path we get some pair (u, v) where u ∈ A∗ and v ∈ B∗
(i.e., u and v are words over alphabets A and B). Consider all pairs that can be read in this
way along all paths in G. For each labeled graph G we obtain a relation (set of pairs) RG that
is a subset of A∗ × B∗ . For the purposes of this paper, we call the relations obtained in this
way “automatic”. This notion is similar to rational relations defined by transducers [5, Section
III.6]. The difference is that we do not fix initial/finite states (so every subpath of a valid path is
also valid) and that we do not allow arbitrary words as labels, only letters and ε . (This will be
important, e.g., for the statement (j) of Theorem 1.)
Definition 2. A relation R ⊂ A∗ × B∗ is automatic if there exists a labeled graph (automaton) G
such that R = RG .
Now we define automatic description modes as automatic relations where each string describes at most O(1) objects:
Definition 3. A relation D ⊂ B∗ × B∗ is an automatic description mode if
• D is automatic in the sense of Definition 2;
• D is a graph of an O(1)-valued function: there exists some constant c such that for each
p there are at most c values of x such that (p, x) ∈ D.
For every automatic description mode D we consider the corresponding complexity function CD . There is no optimal mode D that makes CD minimal (see Theorem 1 below). So,
stating some properties of complexity, we need to mention D explicitly. Moreover, for a statement that compares the complexities of different strings, we need to say something like “for
every automatic description mode D there exists another automatic description mode D′ such
that. . . ”, and then make a statement that involves both CD and CD′ . (A similar approach is
needed when we try to adapt inequalities for Kolmogorov complexity to the case of resourcebounded complexities.)
Let us first mention some basic properties of automatic description modes.
Proposition 1.
(a) The union of two automatic description modes is an automatic description mode.
(b) The composition of two automatic description modes is an automatic description mode.
(c) If D is a description mode, then {(p, x0) : (p, x) ∈ D} is a description mode (here x0 is the
binary string x with 0 appended); the same is true for x1 instead of x0.
Proof. There are two requirements for an automatic description mode: (1) the relation is automatic and (2) the number of images is bounded. The second one is obvious in all three cases.
The first one can be proven by a standard argument (see, e.g., [5, Theorem 4.4]) that we reproduce for completeness.
(a) The union of two relations RG and R′G for two automata G and G′ corresponds to an
automaton that is a disjoint union of G and G′ .
3

(b) Let S and T be automatic relations that correspond to automata K and L. Consider a new
graph that has set of vertices K × L. (Here we denote an automaton and the set of vertices of its
underlying graph by the same letter.)
• If an edge k → k′ with a label (a, ε ) exists in K, then the new graph has edges (k, l) →
(k′ , l) for all l ∈ L; all these edges have the same label (a, ε ).
• In the same way an edge l → l ′ with a label (ε , c) in L causes edges (k, l) → (k, l ′ ) in the
new graph for all k; all these edges have the same label (ε , c).
• Finally, if K has an edge k → k′ labeled (a, b) and at the same time L has an edge l → l ′
labeled (b, c), where b is the same letter, then we add an edge (k, l) → (k′ , l ′ ) labeled (a, c)
in the new graph.
Any path in the new graph is projected into two paths in K and L. Let (p, q) and (u, v) be the
pairs of words that can be read along these projected paths in K and L respectively, so (p, q) ∈ S
and (u, v) ∈ T . The construction of the graph K × L guarantees that q = u and that we read (p, v)
in the new graph along the path. So every pair (p, v) of strings that can be read in the new graph
belongs to the composition of S and T .
On the other hand, assume that (p, v) belong to the composition, i.e., there exists q such that
(p, q) can be read along some path in K and (q, v) can be read along some path in L. Then the
same word q appears in the second components in the first path and in the first components in
the second path. If we align the two paths in such a way that the letters of q appear at the same
time, we get a valid transition of the third type for each letter of q. Then we complete the path
by adding transitions inbetween the synchronized ones (interleaving them in arbitrary way); all
these transitions exist in the new graph by construction.
(c) We add an additional outgoing edge labeled (ε , 0) for each vertex of the graph; all these
edges go to a special vertex that has no outgoing edges.
Remark. Given a graph, one can check in polynomial time whether the corresponding relation
is O(1)-valued [21, Theorem 5.3, p. 777].
Now we are ready to prove the following simple result about the properties of automatic
Kolmogorov complexity functions, i.e., of functions CR where R is some automatic description
mode.
Theorem 1 (Basic properties of automatic Kolmogorov complexity).
(a) There exists an automatic description mode R such that CR (x) ≤ |x| for all strings x.
(b) For every automatic description mode R there exists some automatic description mode R′
such that CR′ (x0) ≤ CR (x) and CR′ (x1) ≤ CR (x) for all x.
(c) For every automatic description mode R there exists some automatic description mode R′
such that CR′ (x̄) ≤ CR (x), where x̄ stands for the reversed x.
(d) For every automatic description mode R there exists some constant c such that C(x) ≤
CR (x) + c. (Here C stands for the plain Kolmogorov complexity.)
(e) For every c > 0 there exists an automatic description mode R such that
CR (1n ) ≤ n/c for all n.
(f) For every automatic description mode R there exists some c > 0 such that CR (1n ) ≥ n/c − 1
for all n.
4

(g) For every two automatic description modes R1 and R2 there exists an automatic description
mode R such that CR (x) ≤ CR1 (x) and CR (x) ≤ CR2 (x) for all x.
(h) There is no optimal automatic description mode. (A mode R is called optimal in some class
if for every mode R′ in this class there exists some c such that CR (x) ≤ CR′ (x) + c for all
strings x.)
(i) For every automatic description mode R, if x′ is a substring of x, then CR (x′ ) ≤ CR (x).
(j) Moreover, CR (xy) ≥ CR (x) + CR (y) for every two strings x and y.
(k) For every automatic description mode R and for every constant ε > 0 there exists an automatic description mode R′ such that CR′ (xy) ≤ (1 + ε ) CR (x) + CR (y) for all strings x
and y.
(l) Let S be an automatic description mode. Then for every automatic description mode R there
exists an automatic description mode R′ such that CR′ (y) ≤ CR (x) for every (x, y) ∈ S.
(m) If we allow a bigger alphabet B instead of B as an alphabet for descriptions, we divide the
complexity by log |B|, up to a constant factor that can be chosen arbitrarily close to 1.
Proof. (a) Consider an identity relation as a description mode; it corresponds to an automaton
with one state.
(b) This is a direct corollary of Proposition 1, (c).
(c) The definition of an automaton is symmetric (all edges can be reversed), and the O(1)condition still holds.
(d) Let R be an automatic description mode. An automaton defines a decidable (computable)
relation, so R is decidable. Since R defines a O(1)-valued function, a Kolmogorov description
of some y that consists of its R-description x and the ordinal number of y among all strings that
are in R-relation to x, is only O(1) bits longer than x.
(e) Consider an automaton that consists of a cycle where it reads one input symbol 1 and
then produces c output symbols 1. (Since we consider the relation as an O(1)-multivalued function, we sometimes consider the first components of pairs as “input symbols” and the second
components as “output symbols”.) Recall that there is no restrictions on initial and finite states,
so this automaton produces all pairs (1k , 1l ) where (k − 1)c ≤ l ≤ (k + 1)c.
(f) Consider an arbitrary description mode, i.e., an automaton that defines some O(1)-valued
relation. Then every cycle in the automaton that produces some output letter should also produce some input letter, otherwise an empty input string corresponds to infinitely many output
strings. For any sufficiently long path in the graph we can cut away a minimal cycle, removing
at least one input letter and at most c output letters, where c is the number of states, until we get
a path of length less than c.
(g) This follows from Proposition 1, (a).
(h) This statement is a direct consequence of (e) and (f). Note that for finitely many automatic description modes there is a mode that is better than all of them, as (g) shows, but we
cannot do the same for all description modes (as was the case for Kolmogorov complexity).
(i) If R is a description mode, (p, x) belongs to R and x′ is a substring of x, then there exists
some substring p′ of p such that (p′ , x′ ) ∈ R. Indeed, we may consider the input symbols used
while producing x′ .
(j) Note that in the previous argument we can choose disjoint p′ for disjoint x′ .
(k) Informally, we modify the description mode as follows: a fixed fraction of input symbols
is used to indicate when a description of x ends and a description of y begins. More formally,
5

let R be an automatic description mode; we use the same notation R for the corresponding
automaton. Consider N + 1 copies of R (called 0-, 1-,. . . , Nth layers). The outgoing edges from
the vertices of ith layer that contain an input symbol are redirected to (i + 1)th layer (the new
state remains the same, only the layer changes, so the layer number counts the input length).
The edges with no input symbol are left unchanged (and go to ith layer as before). The edges
from the Nth layer are of two types: for each vertex x there is an edge with label (0, ε ) that
goes to the same vertex in 0th layer, and edges with labels (1, ε ) that connect each vertex of
Nth layer to all vertices of an additional copy of R (so we have N + 2 copies in total). If both x
and y can be read (as outputs) along the edges of R, then xy can be read, too (additional zeros
should be added to the input string after groups of N input symbols). We switch from x to y
using the edge that goes from Nth layer to the additional copy of R (using additional symbol 1
in the input string). The overhead in the description is one symbol per every N input symbols
used to describe x. We get the required bound, since N can be arbitrarily large.
The only thing to check is that the new automaton is O(1)-valued. Indeed, the possible
switch position (when we move to the states of the additional copy of R) is determined by the
positions of the auxiliary bits modulo N + 1: when this position modulo N + 1 is fixed, we look
for the first 1 among the auxiliary bits. This gives only a bounded factor (N + 1) for the number
of possible outputs that correspond to a given input.
(l) The composition S ◦ R is an automatic description mode due to Proposition 1.
(m) Take the composition of a given description mode R with a mode that provides block
encoding of inputs. Note that block encoding can be implemented by an automaton. There is
some overhead when |B| is not a power of 2, but the corresponding factor becomes arbitrarily
close to 1 if we use block code with large block size.
Remark. Not all these results are used in the sequel; we provide them for comparison with the
properties of the standard Kolmogorov complexity function.

3 Normal sequences and numbers
Consider an infinite bit sequence α = a0 a1 a2 . . . and some integer k ≥ 1. Split the sequence α
into k-bit blocks: α = A0 A1 . . .. For every k-bit string r consider the limit frequence of r among
the Ai , i.e. the limit of #{i : i < N and Ai = r}/N as N → ∞. This limit may exist or not; if it
exists for some k and for all r, we get a probability distribution on k-bit strings.
Definition 4. A sequence α is normal if for every number k and every string r of length k this
limit exists and is equal to 2−k .
Sometimes sequences with these properties are called strongly normal while the name “normal” is reserved for sequences that have this property for k = 1.
There is a version of the definition of normal sequences that considers all occurences of
some string r in α (while Definition 4 considers only aligned ones, whose starting point is a multiple of k). In this “non-aligned” version we require that the limit of #{i < N : αi αi+1 . . . αi+k−1 =
r}/N equals 2−k for all k and for all strings r of length k. A classical result (see, e.g., [12, Chapter 1, Section 8]) says that this is an equivalent notion, and we give below a simple proof of this
equivalence using automatic complexity. Before this proof is given, we will distinguish the two
definitions by using the name “non-aligned-normal” for the second version.
A real number is called normal if its binary expansion is normal (we ignore the integer
part). If a number has two binary expansions, like 0.0111 . . . = 0.1000 . . ., both expansions are
not normal, so this is not a problem.
6

A classical example of a normal number is the Champernowne number [7]
0.0 1 10 11 100 101 110 111 1000 1001 . . .
(the concatenation of all positive integers in binary). Let us sketch the proof of its normality (not
used in the sequel) using the non-aligned version of normality definition. All N-bit numbers in
the Champernowne sequence form a block that starts with 10N−1 and ends with 1N . Note that
every string of length k ≪ N appears in this block with probability close to 2−k , since each of
2N−1 strings (after the leading 1 for the N-bit numbers in the Champernowne sequence) appears
exactly once. The deviation is caused by the leading 1’s and also by the boundaries between the
consecutive N-bit numbers where the k-bit substrings are out of control. Still the deviation is
small since k ≪ N.
This is not enough to conclude that C is (non-aligned) normal, since the definition speaks
about frequencies in all prefixes; the prefixes that end on a boundary between two blocks are
not enough. The problem appears because the size of a block is comparable to the length of the
prefix before it. To deal with arbitrary prefixes, let us note that if we ignore two leading digits
in each number (first 10 and then 11) instead of one, the rest is periodic in the block (the block
consists of two periods). If we ignore three leading digits, the block consists of four periods,
etc. An arbitrary prefix is then close to the boundary between these sub-blocks, and the distance
can be made small compared to the total length of the prefix. (End of the proof sketch.)
The definition of normality can be given for an arbitrary alphabet (instead of the binary
one), and we get the notion of b-normality of a real number for every base b ≥ 2. It is known
that for different bases we get non-equivalent notions (a rather difficult result). The numbers
in [0, 1] that are normal for every base are called absolutely normal. Their existence can be
proved by a probabilistic argument. Indeed, for every base b, almost all reals are b-normal (the
non-normal numbers have Lebesgue measure 0); this is guaranteed by the Strong Law of Large
Numbers. Therefore the numbers that are not absolutely normal form a null set (a countable
union of the null sets for each b). The constructive version of this argument shows that there
exist computable absolutely normal numbers. This result goes back to an unpublished note of
Turing (1938, see [2]).
In the next section we prove the connection between normality and automatic complexity: a
sequence α is normal if for every automatic description mode D the corresponding complexity
CD of its prefix never becomes much smaller than the length of this prefix.

4 Normality and incompressibility
Theorem 2. A sequence α = a0 a1 a2 . . . is normal if and only if
lim inf
n→∞

CR (a0 a1 . . . an−1 )
≥1
n

for every automatic description mode R.
Proof. First, let us show that a sequence that is not normal is compressible. Assume that for
some bit sequence α and for some k the requirement for aligned k-bit blocks is not satisfied.
Using a compactness argument, we can find a sequence of lengths Ni such that for the prefixes
of these lengths the frequencies of k-bit blocks do converge to some probability distribution A
on Bk , but this distribution is not uniform. Then its Shannon entropy H(A) is less than k.
The Shannon theorem can then be used to construct a block code of average length close
to H(A), namely, of length at most H(A) + 1 (this “+1” overhead is due to rounding if the
7

frequencies are not powers of 2). Since this code can be easily converted into an automatic
description mode, it will give the desired result if H(A) < k − 1. It remains to show that it is the
case for long enough blocks.
Selecting a subsequence, we may assume without loss of generality that the limit frequencies
exist also for (aligned) 2k-bit blocks, so we get a random variable A1 A2 whose values are 2kbit blocks (and A1 and A2 are their first and second halves of length k). The variables A1
and A2 may be dependent, and their distributions may differ from the initial distribution A for
k-bit blocks. Still we know that A is the average of A1 and A2 (since A is computed for all
blocks, and A1 [resp. A2 ] corresponds to odd [resp. even] blocks). A convexity argument (the
function p 7→ −p log p used in the definition of entropy has negative second derivative) shows
that H(A) ≥ [H(A1) + H(A2 )]/2. Then
H(A1 A2 ) ≤ H(A1 ) + H(A2 ) ≤ 2H(A),
so A1 A2 has twice bigger difference between entropy and length (at least). Repeating this argument, we can find k such that the difference between length and entropy is greater than 1. This
finishes the proof in one direction.
Now we need to prove that normal sequence α is incompressible. Let R be an arbitrary
automatic description mode. Consider some k and split the sequence into k-bit blocks α =
A0 A1 A2 . . .. (Now Ai are just the blocks in α , not random variables). We will show that
lim infCR (A0 A1 . . . An−1 )/nk
cannot be much smaller than 1. More precisely, we will show that
lim inf

O(1)
CR (A0 A1 . . . An−1 )
≥ 1−
,
nk
k

where the constant in O(1) does not depend on k. This is enough, because (i) adding the last
incomplete block can only increase the complexity and the change in length is negligible, and
(ii) the value of k may be arbitrarily large.
Now let us prove this bound for some fixed k. Recall that
CR (A0 A1 . . . An−1 ) ≥ CR (A0 ) + CR (A1 ) + . . . + CR (An−1 )
and that C(x) ≤ CR (x) + O(1) for all x and some O(1)-constant that depends only on R (Theorem 1). By assumption, all k-bit strings appear with the same limit frequency among A0 , A1 ,. . . ,
An−1 . It remains to note that the average Kolmogorov complexity C(x) of all k-bit strings
is k − O(1); indeed, the fraction of k-bit strings that can be compressed by more than d bits
(C(x) < k − d) is at most 2−d , and the series ∑ d2−d (the upper bound for the average number
of bits saved by compression) has finite sum.
A small modification of this proof adapts it to the non-aligned definition of normality. Let
α be a sequence that is not normal in the non-aligned version. This means that for some k the
k-bit blocks do not have a correct limit distribution (non-aligned). These blocks can be split
into k groups according to their starting positions modulo k. In one of the groups blocks do
not have a correct limit distribution (otherwise the average distribution would be correct, too).
So we can delete some prefix (less than k symbols) of our sequence and get a sequence that is
not normal in the aligned sense. Its prefixes are compressible (as we have seen). The same is
true for the original sequence since adding a fixed finite prefix (or suffix) changes complexity
at most by O(1).
8

In the other direction: let us assume that the sequence is normal in the non-aligned sense.
The aligned frequency of some compressible-by-d-bits block (as well as any other block) can
be only k times bigger than its non-aligned frequency, which is exponentially small in d (the
number of saved bits), so we can choose the parameters to get the required bound.
Indeed, let us consider blocks of length k whose CR -complexity is smaller than k − d. Their
Kolmogorov complexity is then smaller than k − d + O(1), and the fraction of these blocks
(among all k-bit strings) is at most 2−d+O(1) . So their frequency among aligned blocks is at
most 2−d+O(1) · k. For all other blocks R-compression saves at most d bits, and for compressible
blocks it saves at most k bits, so the average number of saved bits (per k-bit block) is bounded
by
d + k2−d+O(1) · k = d + O(k2 2−d ).
We need this bound to be o(k), i.e., we need that
d
+ O(k2−d ) = o(1)
k
as k → ∞. This can be achieved, for example, if d = 2 log k.
In this way we get the following corollary:
Corollary. The aligned and non-aligned definitions of normality are equivalent.
Note also that adding/deleting a finite prefix does not change the compressibility, and, therefore, normality. (For the non-aligned version of the normality definition it is obvious anyway,
but for the aligned version it is not so easy to see directly.)
Another corollary is a result proven by Piatetski-Shapiro in [14]: if for some c and for all k
every k-bits block appears in a sequence with lim sup-frequency at most c2−k , then the sequence
is normal. Indeed, in the argument above we had a constant factor in O(k2−d ) anyway. (We can
even allow the constant c to depend on k if its growth as a function of k is not too fast.)

5 Wall’s theorem
Now we obtain a known result about normal numbers (Wall’s theorem) as an easy corollary.
Recall that a real number is normal if its binary expansion is normal. We agreed to ignore
the integer part (since it has only finitely many digits, adding it as a prefix would not matter
anyway).
Theorem 3 (Wall [20]). If p and q are rational numbers and α is normal, then α p+q is normal.
Proof. It is enough to show that multiplication and division by an integer c preserve normality (note that adding an integer preserves it by definition, since the integer part is ignored).
This fact follows from the incompressibility characterization (Theorem 2), the non-increase of
complexity under automatic O(1) mappings (Theorem 1, (l)) and the following lemma:
Lemma. Let c be an integer. Consider the relation Rc that consists of pairs of strings x and
y such that x and y have the same length and can be prefixes of the binary expansions of the
fractional parts of γ and cγ for some real γ . This relation, as well as its inverse, is contained in
an automatic description mode.
Assuming Lemma 5, we conclude that the prefixes of γ and cγ have the same automatic complexity. More precisely, for every automatic description mode R there exists another automatic
description mode R′ such that CR′ (y) ≤ CR (x) if x and y are prefixes of γ and cγ respectively.
9

This follows from Theorem 1, (l). So if γ is compressible, then cγ is also compressible. The
same is true if we consider the inverse relation; if cγ is compressible, then γ is also compressible.
It remains to prove Lemma 5. Indeed, the school division algorithm can be represented by
an automaton; integer parts can be different, but this creates O(1) different possible remainders. We have to take care of two representations of the same number (note that while dividing
0.29999 . . . by 3, we obtain only 0.09999 . . ., not 0.10000 . . .), but at most two representations
are possible and the relation between them is automatic, so we still get an automatic description
mode.

6 Pairs as descriptions and Agafonov’s theorem
In this section we derive another classical result about normal numbers, Agafonov’s theorem [1],
from the incompressibility characterization. (However, we will need to modify this characterization, see below).
Agafonov’s result is motivated by the von Mises’ approach to randomness (see, e.g., [18,
Chapter 9] for a historic account). As von Mises mentioned, a “random sequence” (he used the
German term “Kollektiv”) should remain random after using a reasonable selection rule. More
precisely, assume that there is some set S of binary strings. This set determines a “selection rule”
that selects a subsequence from every binary sequence α . The selection works as follows: we
observe a binary sequence α = a0 a1 a2 . . . and select terms an such that a0 a1 . . . an−1 ∈ S (without
reordering the selected terms). We get a subsequence; if an initial sequence is “random” (is
plausible as an outcome of a fair coin tossing), said von Mises, this subsequence should also be
random in the same sense. The Agafonov’s theorem says that for regular (automatic) selection
rules and normality as randomness this property is indeed true.
Theorem 4 (Agafonov). Let α = a0 a1 a2 . . . be a normal sequence. Let S be a regular (=recognizable by a finite automaton) set of binary strings. Consider a subsequence σ made of terms
an such that a0 a1 . . . an−1 ∈ S (in the same order as in the original sequence). Then σ is normal
or finite.
Proof. This proof adapts the arguments from [4] to our definition of compressibility. Using the
incompressibility criterion, we need to prove that if the sequence σ is compressible, then α is
compressible, too. The idea is simple: the selection rule splits α into two subsequences: the
selected terms (σ ) and the rest (the non-selected terms). We do not know anything about the
second subsequence, but we assume that σ is compressible, and want to prove that the entire
sequence α is compressible.
The key observation: knowing both subsequences (and the selection rule S, of course), we
can reconstruct the original sequence. Indeed, we know whether a0 is selected or not: it depends
on whether the empty string belongs to S or not. So we know where we should look for the first
term when reconstructing α from its two parts. Knowing a0 , we can check whether one-letter
word a0 belongs to S or not. So we know whether a1 is selected, so we know from which
subsequence it should be taken, etc.
So, we know that our sequence can be reconstructed from two its parts, and one part is
compressible. Then the entire sequence is compressible: a compressed description consist of a
compressed description of a compressible subsequence, and the trivial description of the other
one (for which we do not know whether it is compressible or not). To make this argument
precise, we need two things:
• prove that the selected subsequence has positive density (otherwise its compression gives
only a negligible improvement);
10

• modify the definition of complexity and the criterion of compressibility allowing pairs as
descriptions.
We start with the first part.
Lemma. If the selected subsequence is infinite, then it has a positive density, i.e., the lim inf of
the density of the selected terms is positive.
Proof of the lemma. Consider a deterministic finite automaton that recognizes the set S. We
denote this automaton by the same letter S. Let X be the set of states of S that appear infinitely
many times when S is applied to α . Starting from some time, the automaton is in X , and X
is strongly connected (when speaking about strong connectivity, we ignore the labeling of the
transition edges). Let us show that vertices in X have no outgoing edges that leave X . If these
edges exist, let us construct a string u that forces S to leave X when started from any vertex of
X . This will lead to a contradiction: a normal sequence has infinitely many occurences of u,
and one of them appears when S already is in X . How to construct this u? Take some q ∈ X
and construct a string u1 that forces S to leave X when started from q. Such a string u1 exists,
since X is strongly connected, so we can bring S to any vertex and then use the letter that forces
S to leave X . Now consider some other vertex q′ ∈ X . It may happen that u1 already forces S to
leave X when started from q′ . If not and S remains in X (being in some vertex v), we can find
some string u2 that forces S out of X when started at v. Then the string u1 u2 forces S to leave
X when started in any of the vertices q, q′ . Then we consider some other vertex q′′ and append
(if needed) some string u3 that forces S to leave X when started at q, q′ or q′′ (in the same way).
Doing this for all vertices of X , we get the desired u (and the desired contradiction).
So X has no outgoing edges (and therefore is a strongly connected component of S’s graph).
Now the same argument shows that there exists a string u that forces S to visit all vertices of X
when started from any vertex in X . This string u appears with positive density in α . So either
the selected subsequence is finite (if X has no accepting vertices) or the selected subsequence
has positive density (since every occurence of u means that at least one term is selected when S
visits the accepting vertex). Lemma is proven.
To finish the proof, we need to modify the notion of a description mode and consider pairs as
descriptions. Let A, B,C be three alphabets. We define the notion of automatic ternary relation
R ⊂ A∗ × B∗ × C∗ in the same way as for binary relations: now the edge labels are triples
(a, b, c), where each of the letters (or even all three) can be replaced by ε -symbol. This relation
can be considered as multivalued function of type A × B → C. If it is O(1)-valued, we call it
pair description mode, and a pair (u, v) is called a description of w if (u, v, w) ∈ R. We assume,
as before, that all the alphabets are binary (A = B = C = B), and the length of description is
measured as the sum of lengths:
CR (w) = min{|u| + |v| : (u, v, w) ∈ R}.
The automatic description modes are special cases of pair description modes (if we use only one
component of the pair as a description, and the other one is empty), but this generalization may
lead to smaller complexity function. (It would be interesting to find out how much the decrease
could be.) Still this modified version of automatic complexity can be used to characterize
normality:
Proposition 2. (a) For every pair description mode
C(x) ≤ CR (x) + c log CR (x) + c
for some c and all x, where C(x) stands for the Kolmogorov complexity of x.
11

(b) If R is a pair description mode and α = a0 a1 . . . is a normal sequence, then
lim

CR (a0 a1 . . . an−1 )
≥ 1.
n

(c) If a ternary relation R(u, v, w) is a pair description mode and a binary relation Q(u′ , u) is
an automatic description mode, then their joint
R′ (u′ , v, w) = ∃u [Q(u′ , u) and R(u, v, w)]
is a pair description mode.
(d) Let S be a regular set of binary strings (recognized by a finite automaton) used as a selection
rule. Then the relation
{(u, v, w) : u and v are strings of selected and non-selected bits when S is applied to w}
is a pair description mode.
Proof of the Proposition. (a) Fix some pair description mode R. If (u, v, w) ∈ R, the string w
is determined by the pair (u, v) and the ordinal number of x among the outputs of O(1)-valued
function for input (u, v). So the Kolmogorov complexity of w exceeds the Kolmogorov complexity of a pair (u, v) at most by O(1), and complexity of a pair (u, v) is bounded by l +O(log l)
where l is the total length of u and v.
(b) As before, we cut α into blocks of some large length k. Now the R-complexity of a block
can be smaller than its Kolmogorov complexity, and the decrease can be O(log k), but this does
not matter: for large k this change is negligible compared to k.
(c) The joint of two automatic relations is automatic, for the same reasons; the corresponding
function is O(1)-valued since for each values of u′ we have O(1) different values of u, and each
of them leads to O(1) values of w (for a fixed v).
(d) The process of splitting w into u and v is automatic for obvious reasons. The notion
of automatic relation does not distinguish between input and output, so this ternary relation is
automatic. As we have discussed, for a given u and v there exists at most one w that can be
obtained by merging u and v; to determine whether we take the next letter from u or v, we check
whether the string of symbols already added to w belongs to the selection rule S. (Now the
initial state is not fixed anymore, still we can at most O(1) values for given u and v.)
Now we can finish the proof of Agafonov’s theorem. Assume that some selection rule S is
applied to a normal sequence α and selects some its subsequence σ that is not normal. After
finitely many steps S splits a prefix a of α into sequence of selected terms s (it is a prefix of σ )
and the sequence u of non-selected terms. Then (s, u, a) belongs to the pair description mode
from part (d) of the proposition; let us denote it by U . Now recall that σ is not normal, so
Theorem 2 says that there exists some description mode Q such that CQ (s) < (1 − ε )|s| for
some ε > 0 and for infinitely many prefixes s of σ . Then use part (c) of the proposition and
consider the joint J of Q and U . The
CJ (a) ≤ CQ (s) + |u| ≤ (1 − ε )|s| + |u| ≤ |s| + |u| − ε |s|.
for infinitely many prefixes a of α that correspond to compressible prefixes s of σ . Lemma
guarantees that ε |s| is Ω(|a|), so we use Theorem 2 in the other direction and get a contradiction
with the normality of a.
12

7 Discussion
The connection between normality and finite-state computations was noticed long ago, as the
title of [1] shows; see also [15] where normality was related to martingales arising from finite
automata. This connection led to a characterization of normality as incompressibility (see [4]
for a direct proof). On the other hand, it was also clear that the notion of Kolmogorov complexity is not directly practical since it considers arbitrary algorithms as decompressors, and this
makes it non-computable. So restricted classes of decompressors are of interest, and finite-state
computations are a natural candidate for such a class.
Shallit and Wang [16] suggested to consider, for a given string x, the minimal number of
states in an automaton that accepts x but not other strings of the same length. Later Hyde and
Kjos-Hanssen [10] considered a similar notion using nondeterministic automata. The intrinsic
problem of this approach is that it is not naturally “calibrated” in the following sense: measuring
the information in bits, we would like to have about 2n objects of complexity at most n.
Another (and “calibrated”) approach was suggested by Calude, Salomaa and Roblot [8]: in
their definition a deterministic transducer maps a description string to a string to be described,
and the complexity of y is measured as the combination of the sizes of a transducer and an input
string needed to produce y (the minimum over all transducers and all input strings producing y
is taken). The size of the transducer is measured via some encoding, so the complexity function
depends on the choice of this encoding. The open question posed in [8, Section 6] asks whether
this notion of complexity can be used to characterize normality.
The incompressibility notion used in [4] provides such a characterization for a different definition. It uses deterministic transducers and requires additionally that for every output string
y and every final state s there exists at most one input string that produces y and brings the automaton into the state s. Our approach is a refinement of this one: we consider non-deterministic
automata without initial/final states and require only that decompressor is an O(1)-valued function. The proofs then become simpler, mainly for two reasons: (1) we use the comparison of the
automatic complexity and the plain Kolmogorov complexity and apply standard results about
Kolmogorov complexity; (2) we explicitly state and prove the property CR (xy) ≥ CR (x) +CR (y)
that is crucial for the proofs.

Acknowledgement
I am grateful to Veronica Becher, Olivier Carton and Paul Heiber for many discussions of their
paper [3] and the relations between incompressibility and normality, and for the permission
to use the observations made during these discussions in the current paper. I am also grateful
to my colleagues in LIRMM (ESCAPE team) and Moscow (Kolmogorov seminar, Computer
Science Department of the HSE). I am grateful to the anonymous reviewers of STACS and FCS
conferences; many of their remarks are taken into account in the current version.

13

References
[1] V.N. Agafonov. Normal sequences and finite automata, Doklady AN SSSR, 179, 255–256
(1968). See also the paper of V.N. Agafonov with the same name in the collection: Problemy
Kibernetiki (Cybernetics problems). Volume 20. Moscow: Nauka, 1968, p. 123–129.
[2] V. Becher, Turing’s normal numbers: towards randomness, How the World Computes, Proceedings of the Turing Centenary Conference and the 8th Conference in Computability in
Europe, CiE2012, Cambridge, UK, June 18–23, 2012. Lecture notes in computer science,
7318, 35–45. Springer-Verlag, 2012.
[3] V. Becher, O. Carton, P. Heiber, Finite-state independence, 12 November 2016,
https://arxiv.org/pdf/1611.03921.pdf
[4] V. Becher, P. Heiber, Normal number and finite automata, Theoretical Computer Science,
477, 109–116 (2013).
[5] J. Berstel, Transductions and Context-Free Languages Vieweg+Teubner Verlag, 1969.
ISBN: 978-3-519-02340-1. (For a revised 2006–2009 version see the author’s homepage,
http://www-igm.univ-mlv.fr/~berstel)
[6] Y. Bugeaud, Distribution modulo one and Diophantine approximation, Cambridge Tracts
in Mathematics, 193, Cambridge University Press, 2012.
[7] D. Champernowne, The construction of decimals normal in the scale of ten, Journal of the
London Mathematical Society, volume s1-8, issue 4 (October 1933; Received 19 April, read
27 April,1933), 254–260.
[8] C.S. Calude, K. Salomaa, T.K. Roblot, Finite state complexity, Theoretical Computer Science, 412, 5668–5677 (2011).
[9] R.G. Downey, D.R. Hirschfeldt, Algorithimic randomness and complexity, Springer, 2010,
ISBN 978-0-387-68441-3, xxviii+855 p.
[10] K.K. Hyde, B. Kjos-Hanssen, Nondeterministic complexity of overlap-free and almost
square-free words, The Electronic Journal of Combinatorics, 22:3, 2015.
[11] M. Li, P. Vitányi, An Introduction to Kolmogorov complexity and its applications, 3rd ed.,
Springer, 2008 (1 ed., 1993; 2 ed., 1997), 792 pp. ISBN 978-0-387-49820-1.
[12] L. Kuipers, H. Niederreiter, Uniform distribution of sequences. John Wiley & Sons, 1974.
[13] A. Nies, Computability and randomness, Oxford Logic Guides, Oxford University Press,
2009, ISBN 978-0199652600, 435 p.
[14] I.I. Piatetski-Shapiro, On the laws of distribution of the fractional parts of an exponential
function, Izvestia Akademii Nauk SSSR, Ser. Matem., 15(1), 47–52 (1951). In Russian.
[15] C. Schnorr, H. Stimm, Endliche Automaten und Zufallsfolgen, Acta Informatica, 1(4),
345–39 (1972).
[16] J. Shallit, M.-W. Wang, Automatic complexity of strings, Journal of Automata, Languages
and Combinatorics, 6:4. 537-554 (April 2001)
14

[17] A. Shen, Around Kolmogorov complexity: basic notions and results. Measures of Complexity. Festschrift for Alexey Chervonenkis, edited by V. Vovk, H. Papadoupoulos, A. Gammerman, Springer, 2015, p. 75–116, see also http://arxiv.org/abs/1504.04955
(2015)
[18] A. Shen, V.A. Uspensky, N. Vereshchagin, Kolmogorov complexity and algorithmic randomness, Moscow, MCCME, 2013 (In Russian). English version accepted for publication
by AMS, see www.lirmm.fr/~ ashen/kolmbook-eng.pdf
[19] V.A. Uspensky, A. Shen, Relations between varieties of Kolmogorov complexities, Mathematical Systems Theory, 29, 271–292 (1996).
[20] D.D. Wall, Normal numbers, Thesis, University of California, 1949.
[21] A. Weber, On the valuedness of finite transducers, Acta Informatica, 27(8), 749–780
(1990).

15

