Symbolic dynamics: entropy = dimension = complexity

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson simpson@math.psu.edu

First draft: March 17, 2010 This draft: February 21, 2017

Abstract

Let d be a positive integer. Let G be the additive monoid ℕ^{d} or the additive group ℤ^{d}. Let A be a finite set of symbols. The shift action of G on A^{G} is given by S^{g}(x)(h) = x(g + h) for all g, h ∈ G and all x ∈ A^{G}. A G-subshift is defined to be a nonempty closed set X ⊆ A^{G} such that S^{g}(x) ∈ X for all g ∈ G and all x ∈ X. Given a G-subshift X, the topological entropy ent(X) is defined as usual [31]. The standard metric on A^{G} is defined by ρ(x, y) = 2^{−|F_{n}|} where n is as large as possible such that x↾F_{n} = y↾F_{n}. Here F_{n} = {0, 1, …, n}^{d} if G = ℕ^{d}, and F_{n} = {−n, …, −1, 0, 1, …, n}^{d} if G = ℤ^{d}. For any X ⊆ A^{G} the Hausdorff dimension dim(X) and the effective Hausdorff dimension effdim(X) are defined as usual [15, 26, 27] with respect to the standard metric. It is well known that effdim(X) = sup_{x∈X} lim inf_{n} K(x↾F_{n})/|F_{n}| where K denotes Kolmogorov complexity [10]. If X is a G-subshift, we prove that ent(X) = dim(X) = effdim(X), and ent(X) ≥ lim sup_{n} K(x↾F_{n})/|F_{n}| for all x ∈ X, and ent(X) = lim_{n} K(x↾F_{n})/|F_{n}| for some x ∈ X.

Keywords: symbolic dynamics, entropy, Hausdorff dimension, Kolmogorov complexity.

MSC2010 Subject Classification: Primary 37B10, Secondary 37B40, 94A17, 68Q30.

We thank the anonymous referees for comments which led to improvements in this paper. In particular, the proof of Lemma 5.1 given below was suggested by the first referee and is much simpler than our original proof.

This paper has been published in Theory of Computing Systems, 56(3):2015, 527–543.

Contents

Abstract 1

1 Introduction 2

2 How this paper came about 3

3 Background 4 3.1 Topological entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 Symbolic dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Hausdorff dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Kolmogorov complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.5 Effective Hausdorff dimension . . . . . . . . . . . . . . . . . . . . . . . 9 3.6 Measure-theoretic entropy . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Entropy = dimension 12

5 Dimension = complexity 14

References 16

1 Introduction

The purpose of this paper is to elucidate a close relationship among three disparate concepts which are known to play a large role in three diverse branches of contemporary mathematics. The concepts are:

entropy, Hausdorff dimension, Kolmogorov complexity.

Some relationships among these concepts are well known; see for instance [5, 25, 39]. Nevertheless, it seems to us that the full depth of the relationships has been insufficiently appreciated. Below we prove that, in an important special case, all three concepts coincide.

Here is a brief overview of the above-mentioned concepts.

1. Hausdorff dimension is a basic concept in metric geometry. See for instance the original paper by Hausdorff [15] and the classic treatise by C. A. Rogers [29]. To any set X in a metric space one assigns a nonnegative real number dim(X) = the Hausdorff dimension of X. In the case of smooth sets such as algebraic curves and surfaces, the Hausdorff dimension is a nonnegative integer and coincides with other familiar notions of dimension from algebra, differential geometry, etc. For example, the Hausdorff dimension of a smooth surface in n-dimensional space is 2. On the other hand, Hausdorff dimension applies also to non-smooth sets with nonintegral dimension, e.g., fractals and Julia sets [11].

2. Kolmogorov complexity plays an important role in information theory [8, 32], theoretical computer science [19, 37], and recursion/computability theory [10, 22]. To each finite mathematical object τ one assigns a nonnegative integer K(τ) = the complexity of τ. Roughly speaking, K(τ) is the length in bits of the shortest computer program which describes τ. In this sense K(τ) measures the “amount of information” which is inherent in τ.

3. Entropy is an important concept in dynamical systems theory [9]. Classically, a dynamical system consists of a set X together with a mapping T : X → X and one studies the long-term behavior of the orbits ⟨T^{n}(x) | n = 0, 1, 2, …⟩ for each x ∈ X. More generally, one considers an action T of a group or semigroup G on a set X, and then the orbit of x ∈ X is ⟨T^{g}(x) | g ∈ G⟩. The entropy of the system X, T is a nonnegative real number which has a rather complicated definition but is intended to quantify the “exponential growth rate” of the system.

An especially useful class of dynamical systems are the symbolic systems, a.k.a., subshifts [16, 20, 33, 34]. Given a finite set of symbols A, one defines the shift action of G on A^{G} as usual. A subshift is then defined to be a closed, shift-invariant subset of A^{G}. These symbolic systems play a large role in general dynamical systems theory, because for any dynamical system X, T one can consider partitions π : X → A and then the behavior of an orbit ⟨T^{g}(x) | g ∈ G⟩ is reflected by the behavior of its “symbolic trace,” ⟨π(T^{g}(x)) | g ∈ G⟩, which is a point in A^{G}.

Our main results in this paper are Theorems 4.2 and 5.3 below. They say the following. Let d be a positive integer, let G be the additive monoid ℕ^{d} or the additive group ℤ^{d}, let A be a finite set of symbols, and let X ⊆ A^{G} be a subshift. Then, the entropy of X is equal to the Hausdorff dimension of X with respect to the standard metric on A^{G}. Moreover, the entropy of X has a sharp characterization in terms of the Kolmogorov complexity of the finite configurations which occur in the orbits of X.

In connection with the characterization of entropy in terms of Kolmogorov complexity, it is interesting to note that both of these concepts originated with A. N. Kolmogorov, but in different contexts [35, 18].

2 How this paper came about

This paper is an outcome of my reading and collaboration over the past several years. Here are some personal comments on that process.

It began with my study of Bowen’s alternative definition of topological entropy [3, pages 125–126]. Obviously Bowen’s definition resembles the standard definition of Hausdorff dimension in a metric space, and this led me to consider the following question:

Given a subshift X, what is the precise relationship between the topological entropy of X and the Hausdorff dimension of X?

Specifically, let A be a finite set of symbols. From [3, Proposition 1] it was clear to me that the topological entropy of a one-sided subshift X ⊆ A^{ℕ} is equal to the Hausdorff dimension of X with respect to the standard metric. And eventually I learned that this result appears explicitly in Furstenberg 1967 [12, Proposition III.1]. But what about other kinds of subshifts on A? For instance, what about the two-sided case, i.e., subshifts in A^{ℤ} or A^{ℤ^{d}} or more generally A^{G} where G is a countable amenable group [38]? And what about the general one-sided case, i.e., subshifts in A^{ℕ^{d}} or more generally A^{G} where G is countable amenable semigroup, whatever that may mean?

During February, March and April of 2010 I discussed these issues with several colleagues: John Clemens, Vaughn Climenhaga [7, Example 4.1], Manfred Denker [9], Michael Hochman [16], Anatole Katok [17], Daniel Mauldin, Yakov Pesin [25], Jan Reimann [26], Alexander Shen [37], Daniel Thompson, Jean-Paul Thouvenot [17]. All of these discussions were extremely helpful. In particular, Hochman and Mauldin provided several ideas which play an essential role in this paper.

3 Background

In this section we present some background material concerning symbolic dynamics, entropy, Hausdorff dimension, and Kolmogorov complexity. All of the concepts and results in this section are well known.

We write

ℕ = {0, 1, 2, …} = {the nonnegative integers}

and

ℤ = {…, −2, −1, 0, 1, 2, …} = {the integers}.

Throughout this paper, let G be the additive monoid ℕ^{d} or the additive group ℤ^{d} where d is a fixed positive integer. An action of G on a set X is a mapping T : G × X → X such that T^{e}(x) = x and T^{g}(T^{h}(x)) = T^{g+h}(x) for all g, h ∈ G and all x ∈ X. Here e is the identity element of G. It is useful to write G in a specific^{1} way as the union of a sequence of finite sets, namely G = ⋃_{n=0}^{∞} F_{n} where F_{n} = {0, 1, …, n}^{d} if G = ℕ^{d}, and F_{n} = {−n, …, −1, 0, 1, …, n}^{d} if G = ℤ^{d}. In particular we have F_{0} = {0}^{d} = {e}. We also write F_{−1} = ∅ = the empty set. For any finite set F we write |F | = the cardinality of F. For any function Φ we write dom(Φ) = the domain of Φ, and rng(Φ) = the range of Φ, and

Φ : ⊆ X → Y

meaning that Φ is a function with dom(Φ) ⊆ X and rng(Φ) ⊆ Y. Apart from this, all of our set-theoretic notation is standard.

1In particular, the sequence F_{n} with n = 0, 1, 2, … is a Følner sequence for G.

3.1 Topological entropy

We endow G with the discrete topology. Let X be a nonempty compact set in a topological space, and let T : G × X → X be a continuous action of G on X. The ordered pair X, T is called a compact dynamical system. We now define the topological entropy of X, T.

An open cover of X is a set U of open sets such that X ⊆ ⋃ U. In this case we write

C(X, U) = min{|F| | F ⊆ U, X ⊆ ⋃ F}.

Note that C(X, U) is a positive integer. If U and V are open covers of X, then

sup(U, V) = {U ∩ V | U ∈ U, V ∈ V}

is again an open cover of X, and

C(X, sup(U, V)) ≤ C(X, U)C(X, V).

For each g ∈ G and each open cover U of X, we have another open cover U^{g} = (T^{g})^{−1}(U) = {(T^{g})^{−1}(U) | U ∈ U}. Hence, for each finite set F ⊂ G we have an open cover U^{F} = sup{U^{g} | g ∈ F }. Let us write C(X, T, U, F) = C(X, U^{F}). Note that C(X, U^{g}) ≤ C(X, U), hence C(X, U^{F}) ≤ C(X, U)^{|F |}, hence log_{2} C(X, T, U, F) ≤ |F | log_{2} C(X, U). We define

ent(X, T, U) = lim_{n→∞} \frac{log_{2} C(X, T, U, F_{n})}{|F_{n}|}  (1)

and

ent(X, T) = sup{ent(X, T, U) | U is an open cover of X} .

The nonnegative real number ent(X, T) is known as the topological entropy^{2} of X, T. It measures what might be called the “asymptotic exponential growth rate” of X, T. See for instance [9, 21, 31].

Lemma 3.1. The limit in equation (1) exists.

Proof. Let us write C_{n} = C(X, T, U, F_{n}). Clearly C_{m} ≤ C_{n} whenever m ≤ n. Moreover, it is easy to see that C_{nk} ≤ C_{n}^{k^{d}} for all positive integers k. We are trying to prove that log_{2} C_{n}/|F_{n}| approaches a limit as n → ∞. Assume G = ℤ^{d}, so that |F_{n}| = (2n + 1)^{d}. (The case G = ℕ^{d} is similar, with |F_{n}| = (n + 1)^{d}.)

Fix a positive integer m. Given n ≥ m, let k be a positive integer such that mk ≤ n < m(k + 1). We have |F_{n}| ≥ |F_{mk}| and

\frac{|F_{mk}|}{k^{d}|F_{m}|} = (\frac{2mk + 1}{2mk + k} )^{d} > (\frac{2m}{2m + 1})^{d}

2Instead of log_{2} we could use log_{b} for any fixed b > 1, for instance b = e or b = 10. The base b = 2 is convenient for information theory, where entropy is measured in bits.

and log_{2} C_{n} ≤ log_{2} C_{m(k+1)} ≤ (k + 1)^{d} log_{2} C_{m}, hence

\frac{log_{2} C_{n}}{|F_{n}|} ≤ \frac{(k + 1)^{d} log_{2} C_{m}}{|F_{mk}|} ≤ \frac{(k + 1)^{d} log_{2} C_{m}}{k^{d}|F_{m}|} (\frac{2m + 1}{2m})^{d} .

As n → ∞ we have k → ∞, hence

lim sup_{n→∞} \frac{log_{2} C_{n}}{|F_{n}|} ≤ \frac{log_{2} C_{m}}{|F_{m}|} (\frac{2m + 1}{2m})^{d} ,

and this holds for all m, hence

lim sup_{n→∞} \frac{log_{2} C_{n}}{|F_{n}|} ≤ lim inf_{m→∞} \frac{log_{2} C_{m}}{|F_{m}|} .

In other words, lim_{n→∞} log_{2} C_{n}/|F_{n}| exists, Q.E.D.

Let U and V be open covers of X. We say that U refines V if each U ∈ U is included in some V ∈ V. Obviously this implies C(X, U) ≥ C(X, V), and it is also easy to see that ent(X, T, U) ≥ ent(X, T, V).

Lemma 3.2. For each m we have ent(X, T, U^{F_{m}}) = ent(X, T, U).

Proof. Clearly U^{F_{m}} refines U, hence ent(X, T, U^{F_{m}}) ≥ ent(X, T, U). For all n we have F_{m+n} = F_{m} + F_{n}, hence U^{F_{m+n}} ⊆ (U^{F_{m}})^{F_{n}}, hence U^{F_{m+n}} refines (U^{F_{m}})^{F_{n}}, hence C(X, U^{F_{m+n}}) ≥ C(X, (U^{F_{m}})^{F_{n}}), hence C(X, T, U, F_{m+n}) ≥ C(X, T, U^{F_{m}}, F_{n}), hence

\frac{log_{2} C(X, T, U, F_{m+n})}{|F_{n}|} ≥ \frac{log_{2} C(X, T, U^{F_{m}}, F_{n})}{|F_{n}|} ,

hence

\frac{log_{2} C(X, T, U, F_{m+n})}{|F_{m+n}|} · \frac{|F_{m+n}|}{|F_{n}|} ≥ \frac{log_{2} C(X, T, U^{F_{m}}, F_{n})}{|F_{n}|} .

Taking the limit as n → ∞ and noting that

lim_{n→∞} \frac{|F_{m+n}|}{|F_{n}|} = 1 ,

we see that ent(X, T, U) ≥ ent(X, T, U^{F_{m}}). This completes the proof.

Let U be an open cover of X. We say that U is a topological generator if for each open cover V of X there exists m such that U^{F_{m}} refines V. The following theorem says that we can use a topological generator to compute ent(X, T).

Theorem 3.3. If U is a topological generator, then ent(X, T) = ent(X, T, U).

Proof. Let V be an open cover of X. Since U is a topological generator, let m be such that U^{F_{m}} refines V. Then ent(X, T, U^{F_{m}}) ≥ ent(X, T, V), so by Lemma 3.2 we have ent(X, T, U) ≥ ent(X, T, V). Thus ent(X, T, U) = ent(X, T).

3.2 Symbolic dynamics

An important class of dynamical systems are the symbolic dynamical systems, also known as subshifts. We now present some background material on subshifts. See also [20, §13.10] and [4, 16, 33, 34].

As before, let d be a positive integer, and let G be the additive monoid ℕ^{d} or the additive group ℤ^{d}. Let A be a nonempty finite set of symbols. We endow A with the discrete topology. Let A^{G} = {x | x : G → A}. We endow A^{G} with the product topology. Note that each x ∈ A^{G} is a function from G to A. For each finite set F ⊂ G and each x ∈ A^{G} let x↾F be the restriction of x to F. Thus A^{F} = {x↾F | x ∈ A^{G}}. For each σ ∈ A^{F} we write dom(σ) = F and |σ| = |F | and ⟦σ⟧ = {x ∈ A^{G} | x↾F = σ}. Note that ⟦σ⟧ is a nonempty clopen set in A^{G}, and {⟦σ⟧ | σ ∈ A^{F} } is a pairwise disjoint covering of A^{G}. Let A^{∗} = ⋃_{n=0}^{∞} A^{F_{n}} and note that {⟦σ⟧ | σ ∈ A^{∗}} is a basis for the topology of A^{G}. For any T ⊆ A^{∗} we write ⟦T ⟧ = ⋃_{σ∈T} ⟦σ⟧. Thus ⟦T ⟧ is an open set in A^{G}.

The shift action of G on A^{G} is the mapping S : G × A^{G} → A^{G} given by S^{g}(x)(h) = x(g + h) for all g, h ∈ G and all x ∈ A^{G}. Thus A^{G}, S is a compact dynamical system, known as the full shift. Since F_{0} = {0}^{d} is a singleton set, there is an obvious one-to-one correspondence between A^{F_{0}} and A, so we identify A^{F_{0}} with A. The canonical open covering of A^{G} is U = U(A, G) = {⟦a⟧ | a ∈ A}. For each finite set F ⊂ G we have U^{F} = {⟦σ⟧ | σ ∈ A^{F} }. By compactness of A^{G} it follows that U is a topological generator. Moreover C(A^{G}, S, U, F) = C(A^{G}, U^{F}) = |U^{F} | = |A^{F} | = |A|^{|F |}, so by Theorem 3.3 we have ent(A^{G}, S) = ent(A^{G}, S, U) = log_{2} |A|.

A set X ⊆ A^{G} is said to be shift-invariant if S^{g}(x) ∈ X for all g ∈ G and all x ∈ X. A subshift is a nonempty, closed, shift-invariant subset of A^{G}. Each subshift X ⊆ A^{G} gives rise to a compact dynamical system X, S↾G × X. We write ent(X) = ent(X, S↾G × X), etc. Since U^{F} is a pairwise disjoint covering of A^{G}, we have C(X, U, F) = C(X, U^{F}) = |X↾F | where X↾F = {x↾F | x ∈ X}. Since U is a topological generator, it follows by Theorem 3.3 that

ent(X) = lim_{n→∞} \frac{log_{2} |X↾F_{n}|}{|F_{n}|} .  (2)

Lemma 3.4. We have

lim_{n→∞} |X↾F_{n}|2^{−s|F_{n}|} = \{ \begin{matrix}0 & if s > ent(X) , \\ ∞ & if s < ent(X) . \end{matrix}

Proof. First suppose s > ent(X). Fix ϵ > 0 such that s − ϵ > ent(X). Equation (2) implies that for all sufficiently large n we have (s − ϵ)|F_{n}| > log_{2} |X↾F_{n}|, hence |X↾F_{n}|2^{−|F_{n}|s} < 2^{−ϵ|F_{n}|}. Letting n → ∞ we have |F_{n}| → ∞, hence lim_{n→∞} |X↾F_{n}|2^{−s|F_{n}|} = 0.

Next, suppose s < ent(X). Fix ϵ > 0 such that s + ϵ < ent(X). Equation (2) implies that for all sufficiently large n we have (s + ϵ)|F_{n}| < log_{2} |X↾F_{n}|, hence |X↾F_{n}|2^{−|F_{n}|s} > 2^{ϵ|F_{n}|}. Letting n → ∞ we have |F_{n}| → ∞, hence lim_{n→∞} |X↾F_{n}|2^{−s|F_{n}|} = ∞.

3.3 Hausdorff dimension

Let X be a set in a metric space. The s-dimensional Hausdorff measure of X is defined as

μ_{s}(X) = lim_{ϵ→0} inf_{E} ∑_{E∈E} diam(E)^{s}

where diam(E) is the diameter of E. Here E ranges over coverings of X with the property that diam(E) ≤ ϵ for all E ∈ E. The Hausdorff dimension of X is

dim(X) = inf{s | μ_{s}(X) = 0}.

Hausdorff measures and Hausdorff dimension have been widely studied, e.g., in connection with the geometry of fractals [11, 15, 29].

We now define what we mean by the Hausdorff dimension of a subshift. The standard metric on A^{G} is given by ρ(x, y) = 2^{−|F_{n}|} where n = −1, 0, 1, 2, … is as large as possible such that x↾F_{n} = y↾F_{n}. (Recall that F_{−1} = ∅.) Clearly the standard metric on A^{G} induces the product topology on A^{G}. Moreover, the standard metric is an ultrametric, i.e., ρ(x, y) ≤ max(ρ(x, z), ρ(y, z)) for all x, y, z. For any set X ⊆ A^{G} we define dim(X) = the Hausdorff dimension of X with respect to the standard metric on A^{G}.

Lemma 3.5. For all subshifts X ⊆ A^{G} we have ent(X) ≥ dim(X).

Proof. For each E ⊆ A^{G} we have diam(E) ≤ 2^{−|F_{n}|} if and only if E ⊆ ⟦σ⟧ for some σ ∈ A^{F_{n}}. Therefore, in the definition of μ_{s}(X) and dim(X) for an arbitrary set X ⊆ A^{G}, we may safely assume that each E is a basic open set, i.e., E = ⟦σ⟧ for some σ ∈ A^{∗}. Moreover, for each σ ∈ A^{∗} we have diam(⟦σ⟧) = 2^{−|σ|}.

Assume now that X is a subshift, and suppose s > ent(X). By Lemma 3.4 we have

lim_{n→∞} |X↾F_{n}|2^{−|F_{n}|s} = 0 .  (3)

But for each n we have X ⊆ ⋃_{x∈X}⟦x↾F_{n}⟧ and diam(⟦x↾F_{n}⟧) = 2^{−|F_{n}|}, so (3) implies that μ_{s}(X) = 0, hence s ≥ dim(X). Since this holds for all s > ent(X), it follows that ent(X) ≥ dim(X).

Remark 3.6. In §4 we shall prove that for all subshifts X ⊆ A^{G}, ent(X) = dim(X). In other words, the topological entropy of a subshift is equal to its Hausdorff dimension with respect to the standard metric. While the special case G = ℕ is due to Furstenberg [12, Proposition III.1], the general result for G = ℕ^{d} or G = ℤ^{d} appears to be new.

3.4 Kolmogorov complexity

We now present some background material on Kolmogorov complexity.

As in §3.2 let A^{∗} = ⋃_{n=0}^{∞} A^{F_{n}}. In addition let {0, 1}^{∗} be the set of finite sequences of 0’s and 1’s. For each Turing machine M and each finite sequence α ∈ {0, 1}^{∗}, let M(α) be the run of M with input α. A function

Φ : ⊆ {0, 1}^{∗} → A^{∗}

is said to be partial computable if there exists a Turing machine M such that for all α ∈ {0, 1}^{∗}, α ∈ dom(Φ) if and only if M(α) eventually halts, in which case it halts with output Φ(α). For each such Φ and each ξ ∈ A^{∗} let

K_{Φ}(ξ) = min({|α| | Φ(α) = ξ} ∪ {∞}) .

A partial computable function Ψ : ⊆ {0, 1}^{∗} → A^{∗} is said to be universal if for each partial computable function Φ : ⊆ {0, 1}^{∗} → A^{∗} there exists a constant c such that for all ξ ∈ A^{∗} we have K_{Ψ}(ξ) ≤ K_{Φ}(ξ) + c. The existence of such a universal function is easily proved. Fix such a universal function Ψ. For each ξ ∈ A^{∗} we define the Kolmogorov complexity of ξ to be K(ξ) = K_{Ψ}(ξ). Note that K(ξ) is well defined up to an additive constant, i.e., up to ± O(1). Here “well defined” means that K(ξ) is independent of the choice of Ψ.

Remark 3.7. Actually the complexity notion K defined above is only one of several variant notions, denoted in [37] as KP, KS, KM, KA, KD. These variants are useful in many contexts [10]. However, for our purposes in this paper, the differences among them are immaterial.

3.5 Effective Hausdorff dimension

We now present some background material concerning the effective or computable variant of Hausdorff dimension. Throughout this paper the words “effective” and “computable” refer to Turing’s theory of computability and unsolvability [30, 36].

A Polish space is a complete separable metric space. An effectively presented Polish space consists of a Polish space Z, ρ together with a mapping Φ : ℕ → Z such that rng(Φ) is dense in Z, ρ and the real-valued function (m, n) ↦ ρ(Φ(m), Φ(n)) : ℕ × ℕ → [0, ∞) is computable. In this case we define the basic open sets of Z, ρ, Φ to be those of the form

B(n, r) = {x ∈ Z | ρ(Φ(n), x) < r}

where r is a positive rational number and n ∈ ℕ. A sequence of basic open sets B_{i}, i = 1, 2, … is said to be computable if there exist computable sequences n_{i}, r_{i}, i = 1, 2, … such that B_{i} = B(n_{i}, r_{i}) for all i. A set X ⊆ Z is said to be effectively closed if its complement Z \ X is effectively open, i.e., Z \ X = ∅ or Z \ X = ⋃_{i=1}^{∞} B_{i} where B_{i}, i = 1, 2, … is a computable sequence of basic open sets. We say that X is effectively compact if it is effectively closed and effectively totally bounded, i.e., there exists a computable function f : ℕ → ℕ such that X ⊆ ⋃_{n=1}^{f(i)} B(n, 2^{−i}) for each i.

Let s be a positive real number. We say that X is effectively s-null if there exists a computable double sequence of basic open sets B_{ij}, i, j = 1, 2, …, such that X ⊆ ⋃_{j=1}^{∞} B_{ij} and ∑_{j=1}^{∞} diam(B_{ij})^{s} ≤ 2^{−i} for each i. The effective Hausdorff dimension of X is defined as

effdim(X) = inf{s | X is effectively s-null} .

Note that, although the Hausdorff dimension of a singleton point {x} is always 0, there may be no computable way to “observe” this, so the effective Hausdorff dimension of a noncomputable point may be > 0. In fact, for any set X one has

effdim(X) = sup_{x∈X} effdim({x}) .  (4)

On the other hand, it is known that effdim(X) = dim(X) provided X is effectively compact. See for instance [10, Chapter 13] and [26, 27, 28].

The above definitions and remarks apply to the effectively compact, effectively presented^{3} Polish space A^{G} with the standard metric as defined in §3.3. In particular we have effdim(X) = dim(X) for all effectively closed sets X ⊆ A^{G}. In §5 below we shall prove that effdim(X) = dim(X) for all subshifts X ⊆ A^{G}. This result holds even if X is not effectively closed.

For arbitrary subsets of A^{G}, the following theorem exhibits a relationship between effective Hausdorff dimension and Kolmogorov complexity. We shall see in Theorem 5.3 that the relationship is even closer when X is a subshift.

Theorem 3.8 (Mayordomo’s Theorem). For any set X ⊆ A^{G} we have

effdim(X) = sup_{x∈X} lim inf_{n→∞} \frac{K(x↾F_{n})}{|F_{n}|} .

Proof. This follows from (4) together with [10, Theorem 13.3.4].

3.6 Measure-theoretic entropy

We now present some background material on measure-theoretic entropy. We state two important theorems without proof but with references to the literature.

Let X, μ be a probability space. An action T : G × X → X is said to be measure-preserving if μ((T^{g})^{−1}(P)) = μ(P) for each g ∈ G and each μmeasurable set P ⊆ X. In this case the ordered triple X, T, μ is called a measuretheoretic dynamical system. We now proceed to define the measure-theoretic entropy of X, T, μ.

A measurable partition of X is a finite set P of pairwise disjoint μ-measurable subsets of X such that X = ⋃ P. In this case we write

H(X, μ, P) = − ∑_{P ∈P} μ(P) log_{2} μ(P) .

If P and Q are measurable partitions of X, then

sup(P, Q) = {P ∩ Q | P ∈ P, Q ∈ Q}

3Our Φ for A^{G} is obtained as follows. Let # : A^{∗} → ℕ be a standard Gödel numbering of A^{∗}. In other words, for each σ ∈ A^{∗} let #(σ) be a numerical code for σ from which σ can be effectively recovered. Let a be a fixed symbol in A. Define Φ : ℕ → A^{G} by letting Φ(#(σ)) = x_{σ} ∈ A^{G} where x_{σ} ∈ ⟦σ⟧ and x_{σ}(g) = a for all g ∈ G \ dom(σ).

is again a measurable partition of X, and it can be shown [9, 10.4(d)] that

H(X, μ, sup(P, Q)) ≤ H(X, μ, P) + H(X, μ, Q) .  (5)

For each g ∈ G and each measurable partition P of X, we have another measurable partition P^{g} = (T^{g})^{−1}(P) = {(T^{g})^{−1}(P) | P ∈ P}. Hence, for each finite set F ⊂ G we have a measurable partition P^{F} = sup{P^{g} | g ∈ F }. Let us write H(X, T, μ, P, F) = H(X, μ, P^{F}). It follows from (5) that H(X, T, μ, P, F) ≤ |F |H(X, μ, P). We define

ent(X, T, μ, P) = lim_{n→∞} \frac{H(X, T, μ, P, F_{n})}{|F_{n}|}  (6)

and

ent(X, T, μ) = sup{ent(X, T, μ, P) | P is a measurable partition of X}.

It can be proved that the limit in (6) exists. The nonnegative real number ent(X, T, μ) is known as the measure-theoretic entropy of X, T, μ. It plays an important role in ergodic theory. See for instance [9, 21, 24].

Let X, T, μ be a measure-theoretic dynamical system. A set P ⊆ X is said to be G-invariant if (T^{g})^{−1}(P) ⊆ P for all g ∈ G. The system X, T, μ is said to be ergodic if for every G-invariant μ-measurable set P ⊆ X we have μ(P) = 0 or μ(P) = 1.

Now let d be a positive integer, let G = ℕ^{d} or ℤ^{d}, let A be a nonempty finite set of symbols, and let X ⊆ A^{G} be a subshift. A Borel probability measure μ on X is said to be shift-invariant if μ((S^{g})^{−1}(P)) = μ(P) for each g ∈ G and each Borel set P ⊆ X. In this case X, S, μ is a measure-theoretic dynamical system, and we write H(X, μ, P) = H(X, S, μ, P), ent(X, μ) = ent(X, S, μ), etc. As in §3.2 it can be shown that ent(X, μ) = ent(X, μ, P) where P is the canonical measurable partition of X, namely P = {⟦a⟧ ∩ X | a ∈ A}.

In the case of an ergodic subshift, there is the following suggestive characterization of measure-theoretic entropy.

Theorem 3.9 (Shannon/McMillan/Breiman). Let X ⊆ A^{G} be a subshift, and let μ be an ergodic, shift-invariant, probability measure on X. Then for μ-almost all x ∈ X we have

ent(X, μ) = lim_{n→∞} \frac{log_{2} μ(⟦x↾F_{n}⟧)}{−|F_{n}|} .

Proof. See [23].

We end this section by noting a significant relationship between topological entropy and measure-theoretic entropy.

Theorem 3.10 (Variational Principle). For any subshift X ⊆ A^{G} we have

ent(X) = max_{μ} ent(X, μ)

where μ ranges over ergodic, shift-invariant, probability measures on X.

Proof. See [21] and [9, §§16–20].

4 Entropy = dimension

As in §3 let d be a positive integer, let G = ℕ^{d} or G = ℤ^{d}, let A be a finite set of symbols, and let X ⊆ A^{G} be a subshift. The purpose of this section is to prove that ent(X) = dim(X). The special case G = ℕ is due to Furstenberg [12, Proposition III.1]. However, the general result for G = ℕ^{d} or G = ℤ^{d} appears to be new.

As a warm-up for our proof of the general result, we first present Furstenberg’s proof of the special case G = ℕ.

Theorem 4.1 (Furstenberg 1967). Let X ⊆ A^{ℕ} be a one-sided subshift. Then ent(X) = dim(X).

Proof. By Lemma 3.5 we have ent(X) ≥ dim(X). To prove ent(X) ≤ dim(X) it suffices to prove ent(X) ≤ s for all s such that μ_{s}(X) = 0. Since μ_{s}(X) = 0 let E be such that X ⊆ ⋃ E and ∑_{E∈E} diam(E)^{s} < 1. As noted in §3.3, we may safely assume that each E ∈ E is of the form E = ⟦σ⟧ where σ ∈ A^{∗}, so that diam(E) = 2^{−|σ|}. By compactness we may assume that E is finite. Let us write E = {⟦σ⟧ | σ ∈ I} where I ⊂ A^{∗} is finite. Let m = max{|σ| | σ ∈ I}. From

∑_{σ∈I} 2^{−|σ|s} = ∑_{E∈E} diam(E)^{s} < 1

it follows that

∑_{σ_{1},...,σ_{k}} 2^{−(|σ_{1}|+···+|σ_{k}|)s} = ∑_{k=1}^{∞} (∑_{σ∈I} 2^{−|σ|s})^{k} = M < ∞

where the first sum is taken over all nonempty finite sequences σ_{1}, …, σ_{k} ∈ I.

The previous paragraph applies to any subshift. We now bring in the special assumption G = ℕ. Because G = ℕ and F_{n} = {0, 1, …, n}, each x ∈ A^{G} is an infinite sequence of symbols in A, and each σ ∈ A^{∗} = ⋃_{n=0}^{∞} A^{F_{n}} is a nonempty finite sequence of symbols in A. Thus, given x ∈ X, we can recursively define an infinite sequence σ_{1}, …, σ_{k}, … ∈ I such that S^{|σ_{1}|+···+|σ_{k−1}|}(x) ∈ ⟦σ_{k}⟧ for all k, and then x = σ_{1}^{⌢} ⋯^{⌢}σ_{k}^{⌢} ⋯ where^{⌢} denotes concatenation of finite sequences. Now, given n ≥ 0, let k be as small as possible such that x↾F_{n} ⊆ σ_{1}^{⌢} ⋯^{⌢}σ_{k}. We then have

|F_{n}| ≤ |σ_{1}| + ⋯ + |σ_{k}| < |F_{n}| + m  (7)

and ⟦x↾F_{n}⟧ ⊇ ⟦σ_{1}^{⌢} ⋯^{⌢}σ_{k}⟧. Since the sets ⟦ξ⟧ for ξ ∈ X↾F_{n} are pairwise disjoint, it follows that |X↾F_{n}| is less than or equal to the number of finite sequences σ_{1}, …, σ_{k} ∈ I such that (7) holds. For each such finite sequence we have 2^{−|F_{n}|s} < 2^{ms}2^{−(|σ_{1}|+···+|σ_{k}|)s}, so by summing over all such finite sequences we obtain |X↾F_{n}|2^{−|F_{n}|s} < 2^{ms}M. Thus |X↾F_{n}|2^{−|F_{n}|s} is bounded as n → ∞. It follows by Lemma 3.4 that ent(X) ≤ s, Q.E.D.

We now generalize Furstenberg’s result.

Theorem 4.2. Let G = ℕ^{d} or G = ℤ^{d} where d is a positive integer. Let A be a finite nonempty set of symbols, and let X ⊆ A^{G} be a subshift. Then ent(X) = dim(X).

Proof. By Lemma 3.5 we have ent(X) ≥ dim(X). To prove ent(X) ≤ dim(X) it suffices to prove ent(X) ≤ s for all s such that μ_{s}(X) = 0. Using μ_{s}(X) = 0 and the compactness of X, we can find finite sets I_{l} ⊂ A^{∗} for l = 1, 2, … such that X ⊆ ⋃_{σ∈I_{l}}⟦σ⟧ and ∑_{σ∈I_{l}} 2^{−|σ|s} < 2^{−l} and |σ| << |τ| for all σ ∈ I_{l} and all τ ∈ I_{l+1}. Let I_{∞} = ⋃_{l=1}^{∞} I_{l}. We have

∑_{σ∈I_{∞}} 2^{−|σ|s} < ∑_{l=1}^{∞} 2^{−l} = 1

hence

∑_{σ_{1},...,σ_{k}} 2^{−(|σ_{1}|+···+|σ_{k}|)s} = ∑_{k=1}^{∞} ( ∑_{σ∈I_{∞}} 2^{−|σ|s})^{k} = M < ∞

where the first sum is taken over all nonempty finite sequences σ_{1}, …, σ_{k} ∈ I_{∞}.

For all σ ∈ A^{∗} and all g ∈ G, let σ^{g} = the g-translate of σ, i.e., dom(σ^{g}) = {g +h | h ∈ dom(σ)} and σ^{g}(g +h) = σ(h) for all h ∈ dom(σ). Note that |σ^{g}| = |σ| and ⟦σ^{g}⟧ = ⟦σ⟧^{g} = (S^{g})^{−1}(⟦σ⟧). Since X is a subshift and X ⊆ ⋃_{σ∈I_{l}}⟦σ⟧ for all l, we have

∀l (∀g ∈ G) (∀x ∈ X) (∃σ ∈ I_{l}) (x ∈ ⟦σ^{g}⟧).

Let J_{∞} = ⋃_{l=1}^{∞} J_{l} where J_{l} = {σ^{g} | σ ∈ I_{l}, g ∈ G}.

Lemma 4.3. Let ϵ > 0 be given. For all sufficiently large n and each x ∈ X, we can find a pairwise disjoint set L ⊂ J_{∞} such that ⋃ L ⊆ x↾F_{n} and | ⋃ L| > (1 − ϵ)|F_{n}| and |L| < ϵ|F_{n}|.

Proof. The proof may be viewed as a discrete analog of the classical proof of the Vitali Covering Lemma. Given an “extremely large” configuration x↾F_{n}, we begin by filling in as much of x↾F_{n} as possible with pairwise disjoint “very very large” configurations from J_{∞}. After that, we fill in the gaps with pairwise disjoint “very large” configurations from J_{∞}. After that, we fill in the remaining gaps with pairwise disjoint “large” configurations from J_{∞}. Et cetera.

Specifically, let l be so large that (1−(1/4)^{d})^{l} < ϵ and 1 < ϵ|σ| for all σ ∈ I_{l}, and let n be so large that n >> |σ| for all σ ∈ I_{2l−1}. Given x ∈ X, let ξ = x↾F_{n} and let K_{1} = {τ ∈ J_{2l−1} | τ ⊂ ξ}. Note that | ⋃ K_{1}| ≥ (3/4)^{d}|ξ|, because |τ| << n for all τ ∈ J_{2l−1}. Let L_{1} ⊆ K_{1} be pairwise disjoint^{4} such that | ⋃ L_{1}| ≥ | ⋃ K_{1}|/3^{d}. It follows that | ⋃ L_{1}| ≥ |ξ|/4^{d}, hence |ξ \ ⋃ L_{1}| ≤ (1 − (1/4)^{d})|ξ|. If |ξ \ ⋃ L_{1}| ≤ (1 − (1/4)^{d})^{2}|ξ|, let L_{2} = K_{2} = ∅. Otherwise, let K_{2} = {τ ∈ J_{2l−2} | τ ⊂ ξ \⋃ L_{1}} and note that | ⋃ K_{2}| ≥ (3/4)^{d}|ξ \⋃ L_{1}|, because |τ| << |υ| for all τ ∈ J_{2l−2} and all υ ∈ L_{1}. As before let L_{2} ⊆ K_{2} be pairwise disjoint such that | ⋃ L_{2}| ≥ | ⋃ K_{2}|/3^{d}. It follows as before that |ξ \⋃(L_{1} ∪L_{2})| ≤ (1−(1/4)^{d})^{2}|ξ|. Continuing in this fashion for l steps, we obtain L_{1} ⊆ J_{2l−1} and L_{2} ⊆ J_{2l−2} and … and L_{l} ⊆ J_{l} such that |ξ \ ⋃(L_{1} ∪ ⋯ ∪ L_{l})| ≤ (1 − (1/4)^{d})^{l}|ξ|. Finally let L = L_{1} ∪⋯∪L_{l}. By construction L is pairwise disjoint and ⋃ L ⊆ ξ. Moreover |ξ \ ⋃ L| ≤ (1 − (1/4)^{d})^{l}|ξ| < ϵ|ξ| = ϵ|F_{n}|, hence | ⋃ L| > (1 − ϵ)|ξ| = (1 − ϵ)|F_{n}|. For each τ ∈ L we have 1 < ϵ|τ|, hence |L| < ϵ| ⋃ L| ≤ ϵ|F_{n}|. This proves Lemma 4.3.

4Here are the details. Define L_{1} = {υ_{j} | j = 1, 2, …} where υ_{j} ∈ K_{1} is chosen inductively so that υ_{i} ∩ υ_{j} = ∅ for all i < j and |υ_{j}| is as large as possible. Then for all τ ∈ K_{1} there exists υ ∈ L_{1} such that τ ∩ υ ≠ ∅ and |τ| ≤ |υ|. From this it follows that | ⋃ L_{1}| ≥ | ⋃ K_{1}|/3^{d}.

Lemma 4.4. Let ϵ and n be as in Lemma 4.3. Then |X↾F_{n}| is less than or equal to (|A|+1)^{2ϵ|F_{n}|} times the number of sequences σ_{1}, …, σ_{k} ∈ I_{∞} such that |σ_{1}| + ⋯ + |σ_{k}| ≤ |F_{n}|.

Proof. The idea of the proof is that, by Lemma 4.3, each x↾F_{n} ∈ X↾F_{n} is almost entirely covered by a finite sequence of pairwise disjoint translates of elements of I_{∞}. These elements of I_{∞} can be used to give a concise description of x↾F_{n}.

Given x ∈ X let L = {τ_{1}, …, τ_{k}} be as in the conclusion of Lemma 4.3. For each i = 1, …, k let σ_{i} ∈ I_{∞} be such that τ_{i} = σ_{i}^{g} for some g ∈ G. Since τ_{1}, …, τ_{k} are pairwise disjoint and ⋃_{i=1}^{k} τ_{i} = ⋃ L ⊆ x↾F_{n}, we have |σ_{1}| + ⋯ + |σ_{k}| = |τ_{1}|+⋯+|τ_{k}| ≤ |F_{n}|. Let <_{lex} be the lexicographical ordering of F_{n}. For each i = 1, …, k let g_{i} = the least element of dom(τ_{i}) ⊆ F_{n} with respect to <_{lex}. Reordering τ_{1}, …, τ_{k} as necessary, we may assume that g_{1} <_{lex} ⋯ <_{lex} g_{k}. Let U = F_{n} \ ⋃_{i=1}^{k} dom(τ_{i}), and let V = U ∪ {g_{1}, …, g_{k}}. By Lemma 4.3 we have |U| = |F_{n}| − | ⋃ L| < ϵ|F_{n}| and k = |L| < ϵ|F_{n}|, hence |V | = |U| + k ≤ m where m = 2⌊ϵ|F_{n}|⌋. For each j = 1, …, m define a_{j} ∈ A ∪ {0} as follows. If j ≤ |V | let g be the jth element of V with respect to <_{lex}. If g ∈ U, let a_{j} = x(g). Otherwise, let a_{j} = 0. Clearly x↾F_{n} can be recovered from the pair of sequences a_{1}, …, a_{m} and σ_{1}, …, σ_{k}. This proves Lemma 4.4.

To prove Theorem 4.2, let ϵ and n be as in Lemmas 4.3 and 4.4. Because |σ_{1}|+⋯+|σ_{k}| ≤ |F_{n}| implies 2^{−|F_{n}|s} ≤ 2^{−(|σ_{1}|+···+|σ_{k}|)s}, it follows from Lemma 4.4 and the definition of M that

|X↾F_{n}|2^{−|F_{n}|s} < (|A| + 1)^{2ϵ|F_{n}|}M ,

i.e.,

|X↾F_{n}|2^{−|F_{n}|(s+2ϵ log_{2}(|A|+1))} < M .

Thus |X↾F_{n}|2^{−|F_{n}|(s+2ϵ log_{2}(|A|+1))} is bounded as n goes to infinity, so by Lemma 3.4 we have ent(X) ≤ s + 2ϵ log_{2}(|A| + 1). And this holds for all ϵ > 0, so ent(X) ≤ s. The proof of Theorem 4.2 is now complete.

5 Dimension = complexity

As before let d be a positive integer, let G = ℕ^{d} or G = ℤ^{d}, let A be a finite set of symbols, and let X ⊆ A^{G} be a subshift. In this section we prove that the Hausdorff dimension of X is equal to the effective Hausdorff dimension of X. In addition we obtain a sharp characterization of dim(X) in terms of the Kolmogorov complexity of finite pieces of the individual orbits of X, i.e., in terms of K(x↾F_{n}) for x ∈ X and n = 1, 2, . . .. Our results apply even when X is not effectively closed.

Lemma 5.1. For all x ∈ X we have

lim sup_{n→∞} \frac{K(x↾F_{n})}{|F_{n}|} ≤ ent(X) .  (8)

Proof. Fix a positive integer m. Given n ≥ m, let k be a positive integer such that mk ≤ n < m(k + 1). Partitioning F_{m(k+1)} into (k + 1)^{d} blocks of size |F_{m}|, we see that |X↾F_{n}| ≤ (k + 1)^{d}|X↾F_{m}| and there is a constant c independent of n such that K(x↾F_{n}) ≤ (k + 1)^{d} log_{2} |X↾F_{m}| + 2 log_{2} n + c for all x ∈ X. Thus

\frac{K(x↾F_{n})}{|F_{n}|} ≤ \frac{(k + 1)^{d} log_{2} |X↾F_{m}| + 2 log_{2} n + c}{k^{d}|F_{m}|} → \frac{log_{2} |X↾F_{m}|}{|F_{m}|}

as n → ∞. Since this holds for all m, we now see that (8) follows from (2).

Lemma 5.2. For some x ∈ X we have

lim_{n→∞} \frac{K(x↾F_{n})}{|F_{n}|} = ent(X) .  (9)

Proof. By the Variational Principle 3.10 let μ be an ergodic, shift-invariant, probability measure on X such that ent(X, μ) = ent(X). Fix s < ent(X). Let

D_{n} = {ξ ∈ A^{F_{n}} | K(ξ) < |F_{n}|s} .

Clearly |D_{n}| ≤ 2^{|F_{n}|s}. Fix ϵ > 0 such that s + ϵ < ent(X), and let

T_{n} = {ξ ∈ A^{F_{n}} | μ(⟦ξ⟧) < 2^{−|F_{n}|(s+ϵ)}} .

The Shannon/McMillan/Breiman Theorem 3.9 tell us that for μ-almost all x ∈ X and all sufficiently large n we have

\frac{log_{2} μ(⟦x↾F_{n}⟧)}{−|F_{n}|} > s + ϵ ,

i.e., x↾F_{n} ∈ T_{n}, i.e., x ∈ ⟦T_{n}⟧. On the other hand, for each n we have

μ(⟦D_{n}⟧ ∩ ⟦T_{n}⟧) = μ(⟦D_{n} ∩ T_{n}⟧) ≤ 2^{|F_{n}|s}2^{−|F_{n}|(s+ϵ)} = 2^{−|F_{n}|ϵ}

and so

∑_{n=1}^{∞} μ(⟦D_{n}⟧ ∩ ⟦T_{n}⟧) < ∞ .

Thus the Borel/Cantelli Lemma tells us that, for μ-almost all x and all sufficiently large n, x ∉ ⟦D_{n}⟧ ∩ ⟦T_{n}⟧. But then it follows that, for μ-almost all x and all sufficiently large n, x ∉ ⟦D_{n}⟧, i.e., x↾F_{n} ∉ D_{n}, i.e., K(x↾F_{n}) ≥ |F_{n}|s. Since this holds for all s < ent(X), we now see that (9) holds for μ-almost all x ∈ X. This completes the proof.

Theorem 5.3. Let G = ℕ^{d} or G = ℤ^{d} where d is a positive integer. Let A be a finite set of symbols, and let X ⊆ A^{G} be a subshift. Then

ent(X) = dim(X) = effdim(X) .

Moreover

dim(X) ≥ lim sup_{n→∞} \frac{K(x↾F_{n})}{|F_{n}|}

for all x ∈ X, and

dim(X) = lim_{n→∞} \frac{K(x↾F_{n})}{|F_{n}|}

for some x ∈ X.

Proof. This follows from Theorems 3.8 and 4.2 and Lemmas 5.1 and 5.2.

Questions 5.4.

1. Can we find an “elementary” or “direct” proof of Lemma 5.2? I.e., a proof which does not use measure-theoretic entropy?

2. Is it possible to generalize Theorems 4.2 and 5.3 so as to apply to wider classes of groups or semigroups? For example, do Theorems 4.2 and 5.3 continue to hold if G is an amenable group [38]?

3. Is it possible to generalize Theorems 4.2 and 5.3 so as to apply to scaled entropy and scaled Hausdorff dimension? For example, what about

lim inf_{n→∞} \frac{K(x↾F_{n})}{\sqrt{|F_{n}|}} ?

References

[1] M. Baaz, S.-D. Friedman, and J. Krajíček, editors. Logic Colloquium ’01: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Vienna, Austria, August 6–11, 2001. Number 20 in Lecture Notes in Logic. Association for Symbolic Logic, 2005. VIII + 486 pages.

[2] S. Bezuglyi and S. Kolyada, editors. Topics in Dynamics and Ergodic Theory. Number 310 in London Mathematical Society Lecture Note Series. Cambridge University Press, 2003. VIII + 262 pages.

[3] Rufus Bowen. Topological entropy for noncompact sets. Transactions of the American Mathematical Society, 184:125–136, 1973.

[4] Mike Boyle. Open problems in symbolic dynamics. In [6], pages 69–118, 2008.

[5] A. A. Brudno. Entropy and the complexity of the trajectories of a dynamical system. Transactions of the Moscow Mathematical Society, 2:127–151, 1983.

[6] K. Burns, D. Dolgopyat, and Y. Pesin, editors. Geometric and Probabilistic Structures in Dynamics. Number 469 in Contemporary Mathematics. American Mathematical Society, 2008. XVI + 340 pages.

[7] Vaughn Climenhaga. Bowen’s equation in the non-uniform setting. Ergodic Theory and Dynamical Systems, 31(4):1163–1182, 2011.

[8] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, 2nd edition, 2006. XXIII + 748 pages.

[9] Manfred Denker, Christian Grillenberger, and Karl Sigmund. Ergodic Theory on Compact Spaces. Number 527 in Lecture Notes in Mathematics. Springer-Verlag, 1976. IV + 360 pages.

[10] Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, 2010. XXVIII + 855 pages.

[11] Kenneth Falconer. Fractal Geometry. Wiley, 2nd edition, 2003. XXVIII + 337 pages.

[12] Harry Furstenberg. Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation. Mathematical Systems Theory, 1(1):1–49, 1967.

[13] G. Gallavotti, M. Keane, and D. Ruelle, editors. International Conference on Dynamical Systems in Mathematical Physics. Number 40 in Astérisque. Société Mathématique de France, 1976. IV + 192 pages.

[14] S. S. Goncharov, R. Downey, and H. Ono, editors. Mathematical Logic in Asia: Proceedings of the 9th Asian Logic Conference, Novosibirsk. World Scientific Publishing Company, Ltd., 2006. VIII + 328 pages.

[15] Felix Hausdorff. Dimension und äußeres Maß. Mathematische Annalen, 79(1–2):157–179, 1919.

[16] Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics, 171(3):2011–2038, 2010.

[17] Anatole Katok and Jean-Paul Thouvenot. Slow entropy type invariants and smooth realization of commuting measure-preserving transformations. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 33(3):323– 338, 1997.

[18] A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information and Transmission, 1(1):1–7, 1965.

[19] Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and its Applications. Graduate Texts in Computer Science. Springer-Verlag, 2nd edition, 1997. XX + 637 pages.

[20] Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995. XVI + 495 pages.

[21] Michał Misiurewicz. A short proof of the variational principle for a ℤ_{+}^{N}- action on a compact space. In [13], pages 147–157, 1976.

[22] André Nies. Computability and Randomness. Oxford University Press, 2009. XV + 433 pages.

[23] Donald Ornstein and Benjamin Weiss. The Shannon-McMillan-Breiman theorem for a class of amenable groups. Israel Journal of Mathematics, 44(1):53–60, 1983.

[24] Donald Ornstein and Benjamin Weiss. Entropy and isomorphism theorems for actions of amenable groups. Journal d’Analyse Mathématique, 48(1):1– 141, 1987.

[25] Yakov B. Pesin. Dimension Theory in Dynamical Systems. Chicago Lectures in Mathematics. University of Chicago Press, 1997. XI + 304 pages.

[26] Jan Reimann. Computability and Fractal Dimension. PhD thesis, University of Heidelberg, 2004. XI + 130 pages.

[27] Jan Reimann and Frank Stephan. Effective Hausdorff dimension. In [1], pages 369–385, 2005.

[28] Jan Reimann and Frank Stephan. On hierarchies of randomness tests. In [14], pages 215–232, 2006.

[29] C. A. Rogers. Hausdorff Measures. Cambridge University Press, 1970. VIII + 179 pages.

[30] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. XIX + 482 pages.

[31] David Ruelle. Statistical mechanics on a compact set with ℤ^{ν} action satisfying expansiveness and specification. Transactions of the American Mathematical Society, 185:237–251, 1973.

[32] Claude E. Shannon and Warren Weaver. The Mathematical Theory of Communication. University of Illinois Press, 1949. V + 117 pages.

[33] Paul C. Shields. The Ergodic Theory of Discrete Sample Paths. Number 13 in Graduate Studies in Mathematics. American Mathematical Society, 1996. XI + 249 pages.

[34] Stephen G. Simpson. Medvedev degrees of 2-dimensional subshifts of finite type. Ergodic Theory and Dynamical Systems, 34(2):665–674, 2014. http://dx.doi.org/10.1017/etds.2012.152.

[35] Yakov Sinai. Kolmogorov-Sinai entropy. Scholarpedia, 4(3):2034, 2009. doi:10.4249/scholarpedia.2034.

[36] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230– 265, 1936.

[37] V. A. Uspensky and A. Shen. Relations between varieties of Kolmogorov complexity. Mathematical Systems Theory, 29(3):271–292, 1996.

[38] Benjamin Weiss. Actions of amenable groups. In [2], pages 226–262, 2003.

[39] Homer S. White. Algorithmic complexity of points in dynamical systems. Ergodic Theory and Dynamical Systems, 13(4):807–830, 1993.