# Realizing semicomputable simplices by computable dynamical systems

Daniel Coronel, Alexander Frank, Mathieu Hoyrup, Cristóbal Rojas

► To cite this version:

Daniel Coronel, Alexander Frank, Mathieu Hoyrup, Cristóbal Rojas. Realizing semicomputable simplices by computable dynamical systems. Theoretical Computer Science, 2022, 933, pp.43-54. 10.1016/j.tcs.2022.09.001. hal-03339422

HAL Id: hal-03339422

https://inria.hal.science/hal-03339422

Submitted on 9 Sep 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Realizing semicomputable simplices by
computable dynamical systems*

Daniel Coronel<sup>a</sup>, Alexander Frank<sup>b</sup>,
Mathieu Hoyrup<sup>c</sup>, Cristóbal Rojas<sup>d</sup>

<sup>a</sup>Departamento de Matemáticas, Pontificia Universidad Católica de Chile

<sup>b</sup>Departamento de Matemáticas, Universidad Andes Bello

<sup>c</sup>Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

<sup>d</sup>Instituto de Ingeniería Matemática y Computacional, Pontificia Universidad Católica de Chile

Abstract

We study the computability of the set of invariant measures of a com-
putable dynamical system. It is known to be semicomputable but not
computable in general, and we investigate which semicomputable sim-
plices can be realized in this way. We prove that every semicomputable
finite-dimensional simplex can be realized, and that every semicomputable
finite-dimensional convex set is the projection of the set of invariant mea-
sures of a computable dynamical system. In particular, there exists a
computable system having exactly two ergodic measures, none of which
is computable. Moreover, all the dynamical systems that we build are
minimal Cantor systems.

# 1 Introduction

In this paper we investigate the computability of invariant measures in com-
putable dynamical systems.

This topic has attracted some attention in the last decades. One of the
first results about computability in ergodic theory was obtained by V'yugin
in [V'y97], where he built a computable dynamical system with a computable
invariant measure for which the convergence of Birkhoff averages is not com-
putable. Galatolo et al. [GHR11] produced examples of computable dynam-
ical systems for which every invariant measure is non computable. Hoyrup
showed in [Hoy14] the existence of a computable shift-invariant measure which
is the average of two ergodic measures, none of which is computable. A con-
sequence of Neumann's results in [Neu15] is that a finitely ergodic computable

<footnote>*This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 731143</footnote>
dynamical system always has a computable invariant measure. Other results at the intersection of ergodic theory and computability theory can be found in [Avi09, AGT10, FT14]. Computability of sets and of their elements is a rich topic in computability theory, on which a recent account can be found in [IK20].

All these results show that in general, invariant measures, as a set or individually, are difficult or even impossible to compute. However, they leave several questions open. What are the possible sets of invariant measures of computable dynamical systems? Which computable dynamical systems have at least one computable invariant measure? Which ones have at least one computable ergodic measure? In particular, what can be said about finitely ergodic systems?

In this article, we investigate which semicomputable simplices can be realized as the sets of invariant measures of a computable dynamical system. We use a particular class of dynamical systems, namely Bratteli-Vershik systems. We prove that every *finite-dimensional* semicomputable simplex is computably affine homeomorphic to the set of invariant measures of a computable Bratteli-Vershik system. As a consequence, we build a computable dynamical system having exactly two ergodic measures, none of which being computable. Moreover, we show that every finite-dimensional semicomputable convex set is the projection under a computable affine map of the set of invariant measures of a computable Bratteli-Vershik system. We leave an open question: is every semi-computable Choquet simplex realized by a computable Bratteli-Vershik system, or by any computable dynamical system?

Our strategy is to express a given semicomputable simplex as the inverse limit of a system of affine maps, and then to build a Bratteli-Vershik system from these maps. The second part can easily be made computable: if the affine maps are computable then the Bratteli-Vershik system is computable as well. Our main contribution is to investigate the computability of the first part, which is more subtle.

A first idea would be to use Lazar and Lindenstrauss' result that every Choquet simplex is affine homeomorphic to an inverse limit of affine maps [LL71]. However their proof cannot be made computable, which can be explained as follows. The affine maps that they build are *surjective*. It is not hard to see that if the affine maps are computable and surjective, then the Choquet simplex obtained by taking their inverse limit is *computable*. Therefore, these affine maps cannot be computable if one assumes the Choquet simplex to be semicomputable only. Therefore, we need a different argument, allowing the affine maps to be non-surjective. The general idea is to express a given semicomputable simplex as a computable infinite intersection of polygons, from which we build a computable sequence of affine maps sending each polygon to the next one. The inverse limit of these maps is then the simplex from which we started.

The paper is organized as follows. In Section 2 we present the needed background about Bratteli diagrams and Bratteli-Vershik systems. In Section 3, we give three descriptions of the set of invariant measures of Bratteli-Vershik system: the first one is expressed in terms of the underlying Bratteli diagram, the second one is expressed using a stochastic process, and the third one is geometrical. In Section 4 we give the necessary background on computability. In
Section 5, we prove the main results. In Section 6 we give two applications of these results.

# 2 Background on Bratteli-Vershik maps

Here we present a very brief introduction to minimal Cantor systems and Bratteli-Vershik systems.

## 2.1 Minimal Cantor systems

A *Cantor system* or *Z-action* is a pair $(X, T)$ where $X$ is the Cantor space and $T: X \to X$ is a homeomorphism (an $N$-action can be defined in the same and only requires $T$ to be continuous). If for every $x$ in $X$ the set $\{T^nx : n \in \mathbb{Z}\}$ is dense in $X$, then we say that the Cantor system $(X, T)$ is *minimal*.

Let $(X, T)$ be a Cantor system. A Borel measure $\mu$ on $X$ is called *T-invariant* if for every Borel set $A \subseteq X$, we have $\mu(T^{-1}A) = \mu(A)$. In addition, a probability measure $\mu$ is called *ergodic* if for every Borel set $A$ which is T-invariant up to a set of measure 0, one has $\mu(A) \in \{0, 1\}$.

It is known (see [Phe01]) that the set $M_T(X)$ of T-invariant probability measures of a Cantor system $(X, T)$ is a Choquet simplex and its extreme points are exactly the ergodic measures.

Consider two Cantor systems $(X_1, T_1)$ and $(X_2, T_2)$. We say that both systems are *conjugated* (or *topologically conjugated*) if there exists a homeomorphism $h: X_1 \to X_2$ such that $h \circ T_1 = T_2 \circ h$.

In [HPS92] it was shown that every minimal Cantor system is conjugated to a combinatorial model called Bratteli-Vershik system. These systems will be our main tool in the article. Below we recall their definition and main properties.

## 2.2 Bratteli-Vershik systems

Bratteli-Vershik systems were introduced in [HPS92], and are important because they allowed to use the theory of $C^*$-algebras for studying the orbit structure of Cantor minimal systems. They are also important since, due to their combinatorial nature, Bratteli-Vershik systems are suitable for constructing examples, see for instance [DFM15, DFM18].

### 2.2.1 Ordered Bratteli diagrams

A *directed graph* is a pair $(V, E)$ where $V$ is the set of vertices and $E$ is the set of edges, coming with two maps $\text{Sou}: E \to V$ and $\text{Ran}: E \to V$ (note that there may be several edges from vertex $u$ to vertex $v$).

A *Bratteli diagram* is a directed graph $(V, E)$ where $V = \bigcup_{k \in \mathbb{N}} V_k$ and $E = \bigcup_{k \in \mathbb{N}} E_k \subseteq V \times V$ satisfy the following conditions:

1. The family $\{V_k : k \in \mathbb{N}\}$ is pairwise disjoint,
2. For every $k \ge 0$, the set $V_k$ is non-empty and finite and $V_0$ has exactly one element,

3. For every $k \ge 1$, $E_k$ is non-empty and finite,

4. For every $k \ge 1$, $E_k \subseteq V_{k-1} \times V_k$, i.e. the elements of $E_k$ start at elements of $V_{k-1}$ and end on elements of $V_k$,

5. For every $v \in V$, the set $\{e \in E | \text{SOU}(e) = v\}$ is non-empty,

6. For every $v \in V \setminus V_0$, the set $\{e \in E | \text{Ran}(e) = v\}$ is non-empty.

For every $v$ in $V$ we define its depth as the unique $k$ in $\mathbb{N}$ such that $v$ belongs to $V_k$.

Let $B = (V, E)$ be a Bratteli diagram. The path space $X_B$ of $B$ is the set of infinite paths on $B$ starting from $V_0$:

$$X_B = \{(e_1, e_2, \dots) | e_k \in E_k \text{ and } \text{Ran}(e_k) = \text{SOU}(e_{k+1}) \text{ for } k \ge 1\}.$$

An ordered Bratteli diagram $(V, E, \leq)$ is a Bratteli diagram with a partial order $\leq$ on $E$ such that any two elements $e, e' \in E$ are comparable if and only if $\text{Ran}(e) = \text{Ran}(e')$.

The order $\leq$ on an ordered Bratteli diagram $B = (V, E, \leq)$ induces a lexicographic (partial) ordering on its path space $X_B$, more precisely

$$(e_1, e_2, e_3, \dots) \prec (f_1, f_2, f_3, \dots)$$

(where $\prec$ stands for $\leq$ and $\neq$) if and only if there exists $k_0 \ge 1$ such that $e_k = f_k$ for every $k > k_0$, $e_{k_0} \neq f_{k_0}$ and $e_{k_0} \leq f_{k_0}$.

### 2.2.2 Vershik map

Let $B = (V, E, \leq)$ be an ordered Bratteli diagram such that $X_B$ contains a unique infinite path $x^-$ consisting of minimal edges only, a unique infinite path $x^+$ consisting of maximal edges only and $x^- \neq x^+$. We will refer to these diagrams as proper Bratteli diagrams.

Let us first observe that every $x \in X_B \setminus \{x^+\}$ has a successor with respect to the lexicographic ordering induced by $\leq$. For this, write $x = (e_k)_{k \in \mathbb{N}}$ and take $k_0$ minimal such that $e_{k_0}$ is not maximal. This non-maximal edge $e_{k_0}$ has a successor $e'_{k_0}$ with respect to the order $\leq$. There is a unique path $y \in X_B$ such that its first $k_0 - 1$ edges are minimal, its $k_0$th edge is $e'_{k_0}$, and it coincides with $x$ from the $(k_0 + 1)$th edge onward. This path $y$ is the successor of $x$ we were looking for.

For a proper Bratteli diagram, we define the Vershik map $T_B : X_B \to X_B$ by

$$T_B(x) = \begin{cases} \text{Successor of } x & \text{if } x \neq x^+ \\ x^- & \text{if } x = x^+. \end{cases}$$

For every $k$ in $\mathbb{N}$, we endow $E_k$ with the discrete topology and $\prod_{k=1}^{\infty} E_k$ with the product topology. We consider the induced topology on $X_B$ as a
subset of $\Pi_{k=1}^{\infty} E_k$. With respect to this topology, the Vershik map $T_B$ is a homeomorphism (see [HPS92]). The pair $(X_B, T_B)$ is called a *Bratteli-Vershik system*.

### 2.2.3 Counting Matrices

Let $B = (V, E)$ be a Bratteli diagram. Let $M_n$ be the *counting matrix* whose entry $(u, v) \in V_{n-1} \times V_n$ is the number of edges joining $u$ with $v$. Points 5 and 6 of the definition of a Bratteli diagram (see Section 2.2.1) guarantee that no column or row of $M_n$ be null.

Let us define the *height* row vector

$$h_n = (h_n(v) : v \in V_n)$$

by setting $h_n(v)$ as the number of paths joining $v_0 \in V_0$ and $v \in V_n$. Height vectors and counting matrices are related by the equality

$$h_n = M_1 \times M_2 \times \cdots \times M_n.$$

For $1 \le m < n$, let us define

$$P_{m,n} = M_{m+1} \times M_{m+2} \times \cdots \times M_n$$

and adopt the convention $P_{n,n} = I$. An entry $(u, v) \in V_m \times V_n$ of $P_{m,n}$ corresponds to the number of paths from $u$ to $v$. We have

$$h_{n+1} = h_n M_{n+1} \qquad (1)$$

and therefore

$$h_n = h_m P_{m,n}. \qquad (2)$$

*Remark 2.1.* It is known (see [HPS92]) that every minimal Cantor system $(X, T)$ is conjugated to some Bratteli-Vershik system whose underlying diagram is *simple*, i.e., it satisfies that for every $m \ge 1$ there exists a $n > m$ such that the matrix $P_{m,n}$ has no zero entries. And conversely, if a simple proper Bratteli diagram $B$ is given, then $(X_B, T_B)$ is a minimal Cantor system.

## 3 Invariant measures of Bratteli-Vershik systems

In this section we explore the invariant measures of a Bratteli-Vershik system in three different ways. The first approach is to describe them using the underlying Bratteli diagram. The second approach is to express them as the joint distributions of a stochastic process associated to the Bratteli diagram, and can be seen as an intermediate step towards the third approach, which is geometrical and will be used to prove our results.
## 3.1 Reading invariant measures from the Bratteli diagram

Consider a Bratteli-Vershik system $(X_B, T_B)$ given by a proper diagram $B = (V, E, \leq)$, and an invariant probability measure $\mu$ for the system. For $v \in V_n$, let $\alpha = (e_1, e_2, \dots, e_n)$ be the unique maximal path starting at $v_0 \in V_0$ and ending in $v$, and let $C_n(v)$ be the cylinder $[\alpha]$ of all infinite paths starting with $\alpha$. Let $\hat{\mu}_n$ be the column vector $(\hat{\mu}_n(v) : v \in V_n)$ where $\hat{\mu}_n(v) = \mu(C_n(v))$.

The image of every cylinder $[\beta]$, where $\beta$ is a path starting at $v_0 \in V_0$ and ending at $v \in V_n$, after a finite number of iterations of $T_B$ is equal to $C_n(v)$. Therefore each of such cylinders has measure $\hat{\mu}_n(v)$ due to the $T_B$-invariance of $\mu$.

The cylinder $C_n(v)$ is the disjoint union of all cylinders $[\alpha e]$ for $e$ an edge joining $v \in V_n$ with some $w \in V_{n+1}$. Recalling that the $(v, w)$ entry of the counting matrix $M_{n+1}$ gives the number of edges joining $v \in V_n$ and $w \in V_{n+1}$, the additivity of the measure $\mu$ gives

$$ \hat{\mu}_n = M_{n+1}\hat{\mu}_{n+1}, \qquad (3) $$

and inductively

$$ \hat{\mu}_m = P_{m,n}\hat{\mu}_n \quad \text{for } n \geq m \geq 1. \qquad (4) $$

For $v \in V_n$, let $\mu_n(v)$ be the $\mu$-probability that an infinite path in $X_B$ goes through $v$. Then $\mu_n(v) = h_n(v)\hat{\mu}_n(v)$ and

$$ \sum_{v \in V_n} \mu_n(v) = 1. \qquad (5) $$

In other words, one has

$$ h_n\hat{\mu}_n = 1 \quad \text{for } n \geq 1. \qquad (6) $$

Conversely, any sequence of non-negative column vectors $(\hat{\mu}_n(v) : v \in V_n)$ satisfying (3) and (6) defines an invariant probability measure for the Bratteli-Vershik system $(X_B, T_B)$ ([BKMS10, Theorem 2.9]).

## 3.2 Stochastic formulation

The set of invariant measures of a Bratteli-Vershik system can equivalently be thought as the set of joint distributions of a stochastic process with prescribed transition probabilities. We explain this equivalence, in particular the correspondence between a Bratteli diagram and a sequence of stochastic matrices with rational coefficients representing transition probabilities. More precisely, given a Bratteli diagram, we define a stochastic process with values on the set of vertices of a diagram.

Here, for each $n$, the cardinality of the finite set $V_n$ will be denoted by $k_n$. We consider a stochastic process $S$ consisting of random variables $X_n \in V_n$ with fixed backwards transition probabilities $Pr[X_n = u | X_{n+1} = v]$ and let $A_{n+1}$ be
the $k_n \times k_{n+1}$-matrix whose entry $(u, v) \in V_n \times V_{n+1}$ is given by the corresponding transition probability:

$$A_{n+1}(u, v) = \mathrm{Pr}[X_n = u | X_{n+1} = v].$$

We remark that the matrix $A_{n+1}$ is left stochastic, i.e., its coefficients are all in $[0, 1]$ and each column sums to 1. Note that it is not necessarily a square matrix.

Let $\Delta_k$ be the set of (column) probability vectors in $\mathbb{R}^k$. A left stochastic $k \times l$-matrix $A$ maps $\Delta_l$ into $\Delta_k$.

A joint distribution $\pi$ for the process $S$ is a probability measure over the space of sequences $\{(u_n)_{n \in \mathbb{N}} : \forall n, u_n \in V_n\}$ that respects the transition probabilities. More precisely, if we write $\pi_n(u) = \pi[X_n = u]$ for $u \in V_n$, and

$$p_n = (\pi_n(u))_{u \in V_n} \in \Delta_{k_n},$$

then $\pi$ respects the transition probabilities if and only if

$$p_n = A_{n+1}p_{n+1}.$$

Such a joint distribution $\pi$ can be identified with the sequence of (column) probability vectors $(p_n)_{n \in \mathbb{N}}$.

The collection of all joint probability distributions is therefore given by

$$\Delta_S = \left\{ (p_1, p_2, \dots) \in \prod_n \Delta_{k_n} : \forall n, p_n = A_{n+1}p_{n+1} \right\},$$

which is the inverse limit $\lim_{\leftarrow\leftarrow A_{n+1} : \Delta_{k_{n+1}} \to \Delta_{k_n}}$ where we have identified the matrices with the functions defined by them. In particular, since the sets $\Delta_{k_i}$ are compact, the projection of $\Delta_S$ on $\Delta_{k_i}$ is given by

$$\mathrm{Pr}(\Delta_S, k_i) = \bigcap_{n \ge i} A_i \circ \dots \circ A_n(\Delta_{k_n}). \qquad (7)$$

Given fixed transition matrices $(A_n)_{n \ge 1}$, the collection $\Delta_S$ of all possible joint probability distributions of the process $S$ forms a Choquet simplex and, conversely, every Choquet simplex can be realized in this way, up to affine homeomorphism ([LL71]).

### 3.2.1 Equivalence with Bratteli diagrams

For the case of stochastic processes as described in the previous section for which the transition matrices are rational numbers, there is a correspondence with Bratteli-Vershik systems where the joint probability distributions of the stochastic system correspond to the invariant measures of the Bratteli-Vershik system in an explicit manner that we now describe.

Let us start by showing how to construct a stochastic system from a given Bratteli-Vershik system $B = (X_B, T_B)$ with underlying Bratteli diagram $(V, E)$.
Let $h_n$ be the height vectors of $B$ and $M_n$ be the counting matrices. Let $H_n$ be the diagonal matrix whose diagonal coefficients are given by:

$$H_n(u, u) = h_n(u) \quad \text{for } u \in V_n.$$

The equality $h_{n+1} = h_n M_{n+1}$ (1) can be reformulated by saying that the matrices $A_{n+1} = H_n M_{n+1} H_{n+1}^{-1}$ are stochastic. In order to proceed with the construction in the other direction, we need the following Lemma.

**Lemma 3.1.** Let $A = (A(u, v))_{u,v}$ with $u \in V_n$ and $v \in V_{n+1}$ be a stochastic rational matrix and let $(h(u))_{u \in V_n}$ be a row vector with positive integer entries. Then there exists a matrix $M$ with natural coefficients such that if $h'$ denotes the vector $hM$ then

$$A(u, v) = \frac{h(u)M(u, v)}{h'(v)}.$$

*Proof.* Let $v$ be fixed. Let $p(u, v)$, $q(v)$ be natural numbers such that

$$\frac{A(u, v)}{h(u)} = \frac{p(u, v)}{q(v)} \quad \text{for all } u \in V_n.$$

We now let $M(u, v) = p(u, v)$ and obtain

$$h'(v) = \sum_{u} h(u)M(u, v) = \sum_{u} A(u, v)q(v) = q(v).$$

Then it is straightforward to check that

$$A(u, v) = \frac{h(u)M(u, v)}{h'(v)},$$

as wanted. Observe that one could take $M$ so that $h'$ is constant, by choosing the same $q(v)$ for all $v$. $\square$

The conclusion of the Lemma can be reformulated as $A = HMH'^{-1}$, where $H$ and $H'$ are the diagonal matrices with coefficients given by $h$ and $h'$ respectively. Now, let $S$ be a given stochastic process with states $(V_n)_n$ and stochastic backwards transition matrices $(A_n)_n$. We inductively define matrices $M_n$ and row vectors $(h_n(u))_{u \in V_n}$ such that

* $M_n$ has the same dimensions as $A_n$ and its entries are all non-negative integers

* $h_n(u)$ are positive integers for all $n$ and $u$, and satisfy

$$h_{n+1} = h_n M_{n+1} \quad \text{and} \quad M_{n+1} = H_n A_{n+1} H_{n+1}^{-1}.$$

The definition is as follows. Start with $h_1 = 1$. Then inductively apply Lemma 3.1 to $A_{n+1}$ and $h_n$ to get $M_{n+1}$ and $h_{n+1} = h_n M_{n+1}$. The matrices $M_n$
uniquely determine the set of edges E between vertices of V such that the counting matrices of the corresponding Bratteli diagram are precisely $M_n$.

Now assume that the Bratteli diagram have a proper order and consider the Bratteli-Vershik system $(X_B, T_B)$ associated with this order. The connection between an invariant measure $\mu$ of the Bratteli-Vershik system $(X_B, T_B)$ and the corresponding joint probability measure $\pi$ of $S$ is given by

$$ \mu_n(u) = \pi_n(u) \quad \forall u \in V_n \quad n \ge 0. \qquad (8) $$

*Remark 3.1.* Observe that if the counting matrices of a Bratteli diagram are all positive then the diagram admits a proper order.

### 3.3 Geometrical interpretation

Stochastic matrices can be seen as geometrical transformations, which will help relating simplices, which are geometrical objects, to sets of invariant measures in Bratteli-Vershik, which can be formulated using stochastic matrices as previously discussed.

Let $\Delta_k$ be the set of probability vectors in $\mathbb{R}^k$. A stochastic $k \times l$-matrix $A$ maps $\Delta_l$ into $\Delta_k$. The image of $\Delta_l$ under $A$ is a convex polytope contained in $\Delta_k$, with at most $l$ vertices. The following lemma states that each such polytope can be obtained.

**Lemma 3.2.** Let $k, l \in \mathbb{N}$. For every convex polytope $P \subseteq \Delta_k$ with rational coefficients and at most $l$ vertices, there exists a stochastic matrix $A$ such that the image of $\Delta_l$ under $A$ is exactly $P$. Moreover, $A$ can be computed from the finite description of $P$.

*Proof.* Let $(p_i)_{i \le l}$ be points whose convex hull is $P$. Put $p_i$ at column $i$ of $A$. $\square$

Note that if the coordinates of $P$ are rational then the coefficients of $A$ are rational.

## 4 Computable analysis

In this section, we recall notions from computable analysis on metric spaces. All the results presented here are well known. For a detailed modern exposition we refer to [BH21]. In the following, we will make use of the word *algorithm* to mean a computer program written in any standard programming language or, more formally, a Turing Machine [Tur36]. Algorithms are assumed to be only capable of manipulating integers. By identifying countable sets with integers in a constructive way, we can let algorithms work on these countable sets as well. For example, algorithms can manipulate rational numbers by identifying each $p/q$ with some integer $n$ in such a way that both $p$ and $q$ can be computed from $n$, and vice-versa. We fix such a numbering from now on.
## 4.1 Computable metric spaces

Computable analysis is about making algorithms able to process infinite objects, such as real numbers or infinite sequences. A convenient unifying way to formalize this idea is to see these objects as points of a metric space with an extra computable structure.

**Definition 4.1.** A computable metric space is a triple $(X, d, \mathcal{S})$, where $(X, d)$ is a separable metric space and $\mathcal{S} = \{s_i : i \ge 0\}$ a countable dense subset of $X$, such that there exists an algorithm which, upon input $(i, j, n) \in \mathbb{N}^3$, outputs $r \in \mathbb{Q}$ such that

$$|d(s_i, s_j) - r| \le 2^{-n}.$$

We say that the distances $d(s_i, s_j)$ are uniformly computable.

For $r > 0$ a rational number and $x$ an element of $X$, we denote by $B(x, r) = \{z \in X : d(z, x) < r\}$ the ball with center $x$ and radius $r$. The balls centered on elements of $\mathcal{S}$ with rational radii are called **basic balls**. A computable enumeration of the basic balls $B_n = B(s^{(n)}, r^{(n)})$ can be obtained by taking for instance a bi-computable bijection $\varphi : \mathbb{N} \to \mathbb{N} \times \mathbb{Q}$ and letting $s^{(n)} = s_{\varphi_1(n)}$ and $r^{(n)} = \varphi_2(n)$, where $\varphi(n) = (\varphi_1(n), \varphi_2(n))$. We fix such a computable enumeration from now on. For any subset $I$ (finite or infinite) of $\mathbb{N}$, we define

$$U_I = \bigcup_{n \in I} B_n.$$

An open set $V \subseteq X$ is **effectively open** if $V = U_I$ for some computably enumerable (c.e.) set $I \subseteq \mathbb{N}$. That is, there is an algorithm running forever and progressively listing $I$, in an arbitrary order. A point $x \in X$ is **computable** if the set $\{n \in \mathbb{N} : x \in B_n\}$ is c.e.

*Example 1.* The following are two important examples.

* For a finite alphabet $\mathcal{A}$ and 0 one of its elements, the Cantor space $\mathcal{A}^\mathbb{N}$ with its usual metric $d(x, y) = 2^{-\min\{n:x_n \neq y_n\}}$ has a natural computable metric space structure using a standard enumeration of the dense countable set $\mathcal{S} = \{w0^\infty : w \in \mathcal{A}^*\}$, where $\mathcal{A}^*$ denotes the set of all finite words one can make with the symbols of $\mathcal{A}$. In this case, the basic balls are the cylinders.

* The compact interval $[0, 1]$, with the Euclidean metric $d(x, y) = |x - y|$ and $\mathcal{S} = \mathbb{Q} \cap [0, 1]$ is also a computable metric space. The basic balls here are the open intervals with rational endpoints, intersected with $[0, 1]$.

Let $(X, d)$ and $(X', d')$ be computable metric spaces. Let $(B'_m)_{m \in \mathbb{N}}$ denote the canonical enumeration of the basic balls of $X'$. A function $f : X \to X'$ is **computable** if there exists an algorithm which, given as input some integer $m$, enumerates a set $I_m$ such that

$$f^{-1}(B'_m) = U_{I_m},$$
i.e. if the preimages $f^{-1}(B'_m)$ are uniformly effective open sets.

It follows that computable functions are continuous. It is perhaps more intuitively familiar, and provably equivalent, to think of a computable function as one for which there is an algorithm which, provided with arbitrarily good approximations of $x$, outputs arbitrarily good approximations of $f(x)$. In symbolic spaces, this can easily be made precise:

**Example 2.** In Cantor space $\mathcal{A}^N$, a function $f: \mathcal{A}^N \to \mathcal{A}^N$ is computable if and only if there exists some non decreasing computable function $\varphi: \mathbb{N} \to \mathbb{N}$ together with an algorithm which, provided with the $\varphi(n)$ first symbols of the sequence $x$, computes the $n$th first symbols of the sequence $f(x)$.

## 4.2 Computability of compact sets

There are mainly two notions of computability for compact subsets of a computable metric space $X$.

A compact set $K \subseteq X$ is said to be **semicomputable** if the inclusion

$$K \subseteq U_I,$$

where $I$ is some finite subset of $\mathbb{N}$, is semi-decidable. That is, if there is an algorithm which, given $I$ as input, halts if and only if the inclusion above is verified.

A compact set $K \subseteq X$ is said to be **computable** if it is semicomputable and contains a dense computable sequence.

When the compact set is the space $X$ itself, we will say that $X$ is **effectively compact** if it is semicomputable, as a subset of $X$ (we use this alternative terminology to avoid the misleading expression “semicomputable computable metric space”).

**Example 3.** The Cantor space and the compact interval are easily seen to be effectively compact.

We will make use of the following fact, which is a computable version of the fact that in a compact Hausdorff space, a subset is compact if and only if it is closed. For a proof see for instance in [BP03].

**Proposition 4.1.** Let $(X, d, \mathcal{S})$ be an effectively compact computable metric space. A compact subset $K \subseteq X$ is semicomputable if and only if its complement is effectively open.

**Example 4.** If $X$ is an effectively compact computable metric space, then the set $M_X$ of probability measures is also an effectively compact computable metric space. Moreover, if $T: X \to X$ is a computable map, then the set of invariant measures $M_T$ is upper computable, and therefore effectively compact as well (see [Gác08, HR09]).

If $f: X \to X'$ is a computable function between computable metric spaces, then the image of a semicomputable set is semicomputable, and the image of a computable set is computable.
## 4.3 Computable Bratteli-Vershik systems

Let $B = (V, E)$ be a Bratteli diagram such that $k_n = |V_n|$ and $M_n$ are computable functions of $n$. We assume w.l.o.g. that $V_n = \{1, \dots, |V_n|\}$. Note that in this case, $X_B$ is an effectively compact computable metric space.

**Proposition 4.2.** If an ordered Bratteli diagram $B$ has a unique minimal path $x^{-}$, then the Vershik map $T_B: X_B \to X_B$ is a computable function.

*Proof.* Let $n \in \mathbb{N}$. By compactness, there exists $p \in \mathbb{N}$ such that every path whose prefix of length $p$ is minimal starts with the first $n$ symbols of $x^{-}$ (otherwise for each $p$ there is a path that is minimal up to $p$ far away from $x^{-}$, but by compactness they accumulate to a minimal path that must be different from $x^{-}$, contradicting the uniqueness of the minimal path). Such a $p$ can be computed from $n$: look for $p$ such that all the minimal paths of length $p$ share the same prefix of length $n$. Let $p(n)$ be the corresponding computable function. The function $p(n)$ is actually a modulus of continuity of the dynamics. Indeed, if $x$ is maximal up to $p(n)$, then $f(x)$ is minimal up to $p(n)$, so that $f(x)$ and $x^{-}$ have the same prefix of length $n$ by construction of $p(n)$.

The path $x^{-}$ is therefore computable: to compute the $n$ first bits, compute some minimal path of length $p(n)$, and output its $n$ first bits.

We can assume w.l.o.g. that $p(n) \ge n$. To compute the first $n$ symbols of $f(x)$ given $x$, decide whether the prefix of $x$ of length $p(n)$ is maximal. If it is, then output the first $n$ symbols of $x^{-}$. In the other case, simply apply the transformation using the first non-maximal position. $\square$

# 5 Realization results

Let us start with a few geometric Lemmas.

**Lemma 5.1.** Let $U \subseteq \Delta_n \subseteq \mathbb{R}^n$ be an open convex set in $\mathbb{R}^n$ and $S \subseteq U$ be a simplex with $\ell \le n$ vertices. Then there exists a simplex $S' \subseteq U$ with $n$ vertices, all of them rational, which contains $S$ in its interior.

*Proof.* First assume $\ell = n$. Take a vertex $p$ of $S$ and consider the $n-1$ hyperplanes $\{H_1(p), \dots, H_{n-1}(p)\}$ where each one contains exactly $n-1$ vertices of $S$, including the vertex $p$ (i.e., each $H_i(p)$ is a hyperplane in $\mathbb{R}^n$ containing an $(n-1)$-dimensional face of $S$ and $p$). Each $H_i(p)$ divides $\Delta_n$ in two open regions, let us call them $R_i(p)$ and $\tilde{R}_i(p)$, and let us say that $R_i(p) \cap S \ne \emptyset$ (and thus $\tilde{R}_i(p) \cap S = \emptyset$). Under the hypotheses of the lemma, the set $U \cap \tilde{R}_1(p) \cap \dots \cap \tilde{R}_{n-1}(p) \subseteq \Delta_n$ is non-empty and open in $\mathbb{R}^n$, and therefore it has a rational point $r_p \in \Delta_n$.

Let $\{p_1, \dots, p_n\}$ be the vertices of $S$. The previous procedure gives rational elements $\{r_{p_1}, \dots, r_{p_n}\}$, which we can choose linearly independent, such that any group of $n-1$ of them belongs to some $\tilde{R}_i(p_j)$, with $1 \le i \le n-1$ and $1 \le j \le n$. Defining $S'$ as the convex hull of $\{r_{p_1}, \dots, r_{p_n}\}$, the above implies that $S$ is contained in the interior of $S'$, and the convexity of $U$ implies $S' \subseteq U$.
The case $\ell < n$ can be reduced to the previous one in the following way: Consider the set $\{p_1, \dots, p_\ell\}$ of vertices of $S$. It is possible to chose $n - \ell$ points $\{p_{\ell+1}, \dots, p_n\}$ such that all of them belong to $U$ and the combined set $\{p_1, \dots, p_n\}$ is linearly independent (in particular, the new points do not belong to $S$). Let $\tilde{S}$ be the convex hull of this last set of $n$ points. The linear independence implies that $\tilde{S}$ is a simplex of $n$ vertices, so we can apply the previous case to it and get a simplex of $n$ rational vertices $S' \subseteq U$ such that $S \subseteq \tilde{S} \subseteq \text{Int}(S')$. $\square$

**Remark 5.1.** As an $\ell$-polytope with finitely many vertices is a finite union of simplices of $\ell$ vertices, the statement of Lemma 5.1 is also true for $\ell$-polytopes with $\ell \le n$, i.e. given a finite convex $\ell$-polytope $P$ ($\ell \le n$) contained in some convex open $U$ in the interior of $\Delta_n$, there is a finite $n$-polytope $P'$ with rational vertices also contained in $U$ and that contains $P$ in its interior. Moreover, if $P$ is an $n$-polytope with $k$ vertices (obviously $k \ge n$), the $n$-polytope $P'$ can be chosen having also $k$ vertices.

**Lemma 5.2.** Let $S$ be a simplex of $\ell \le n$ vertices contained in the interior of $\Delta_n \subseteq \mathbb{R}^n$. If $S$ is semicomputable then there exists a decreasing computable sequence of rational simplices $(S_k)_k$ contained in $\Delta_n$ such that each $S_k$ has $n$ vertices and $\bigcap_k S_k = S$.

*Proof.* Let $\mathcal{E}$ be a computable enumeration of all simplices of dimension $n$ with rational vertices contained in $\Delta_n$. The effective compactness of $S$ allows us to have a semi-decidable procedure for knowing whether an element in $\mathcal{E}$ contains $S$ in its interior (the procedure halts only if the input is an element in $\mathcal{E}$ containing $S$ in its interior).

With this, we can make an algorithm generating a sequence $(S_k)_k$ of elements in $\mathcal{E}$ each one containing $S$ in its interior. By Lemma 5.1, this algorithm can be made such that the sequence $(S_k)_k$ is decreasing and intersects in $S$. $\square$

**Lemma 5.3.** Let $S \subseteq \Delta_n \subseteq \mathbb{R}^n$ be a semicomputable convex set. There exists a decreasing computable sequence of rational convex polytopes $P_i \subseteq \Delta_n$ such that $S = \bigcap_i P_i$.

*Proof.* First observe that one can enumerate all the rational convex polytopes that contain $P$ in their interior, as $S$ is semicomputable.

For every open set $U$ containing $P$, we show that there exists a rational convex polytope containing $P$ in its interior and contained in $U$. For each point $x \in \Delta_n \setminus U$ there exists a hyperplane $H_x$ separating $P$ from $x$, which by density of the rational numbers can be assumed to be defined by an equation with rational coefficients. Let $R_p$ be the open half-space delimited by $H_x$ containing $x$, and therefore disjoint from $P$. The union $\bigcup_x \in \Delta_n \setminus UR_x$ covers $\Delta_n \setminus U$ which is compact, hence is already covered by a finite union. The complement of that finite union is a polytope with rational coordinates (these coordinates are solutions of linear systems with rational coefficients).

Enumerate all the finite unions of open balls covering $P$ and take their finite intersections to obtain a decreasing sequence of open sets $U_i$. In each open
set $U_{i+1}$, one can compute by exhaustive search a rational convex polytope $P_{i+1}$ contained in the interior of $P_i \cap U_{i+1}$ and containing $S$ in its interior. $\square$

The following proposition is the key to construct the Bratteli-Vershik systems exhibiting a statistics with prescribed geometry.

**Proposition 5.1.** Let $k \in \mathbb{N}$ and let $S \subseteq \Delta_k \subseteq \mathbb{R}^k$ be a semicomputable convex set. Let $(P_n)_{n \in \mathbb{N}}$ be a decreasing sequence of rational convex polytopes in $\Delta_k$ such that $S = \bigcap_n P_n$. Then one can compute finite sets $V_n$ and stochastic $|V_n| \times |V_{n+1}|$-matrices $A_n$ such that $|V_1| = k$ and the set

$$ \{(\pi[X_1 = u])_{u \in V_1} : \pi \text{ is a joint distribution of the process}\} $$

is exactly $S$.

*Proof.* Let $|V_1| = k_1 := k$ and let $|V_{n+1}| = k_{n+1}$ be the number of vertices of $P_n$. We inductively build a sequence $A_n$ so that

$$ A_1 \dots A_{n-1} A_n (\Delta_{k_{n+1}}) = P_n. $$

As $P_1$ has $k_2$ vertices, one can take $A_1 : \Delta_{k_2} \to \Delta_{k_1}$ such that

$$ A_1(\Delta_{k_2}) = P_1, $$

using Lemma 3.2. Let $n \ge 2$ and assume that

$$ A_1 \dots A_{n-1}(\Delta_{k_n}) = P_{n-1}. $$

As $P_n \subseteq P_{n-1}$, there exists a rational convex polytope $Q \subseteq \Delta_{k_n}$ such that

$$ A_1 \dots A_{n-1}(Q) = P_n. $$

As $P_n$ has $k_{n+1}$ vertices, one can take $Q$ with $k_{n+1}$ vertices as well. By Lemma 3.2, there exists $A_n$ so that $A_n(\Delta_{k_{n+1}}) = Q$. As a result, on has that

$$ A_1 \dots A_{n-1} A_n (\Delta_{k_{n+1}}) = P_n. $$

Therefore, applying (7), the first projection of the set of joint distributions of the process is

$$ \bigcap_n A_1 \dots A_{n-1} A_n (\Delta_{k_{n+1}}) = \bigcap_n P_n = S. \quad \square $$

We are now in position to state the first main result of this section. It solves the problem of realisation of semicomputable simplices for the finite dimensional case.

**Theorem 5.1.** Let $S$ be a semicomputable simplex of $\ell \le n$ vertices contained in $\Delta_n$. Then there exists a computable minimal Bratteli-Vershik system $(X, T)$ such that its set of invariant measures $M_T(X)$ is computably affine homeomorphic to $S$. Moreover, the following hold:
* The Bratteli diagram B defining X satisfies that for every integer $k \ge 1$ the number of vertices of depth k is equal to n, and the stochastic matrices associated to B are invertible of size n,

* If $V_1$ denote the set of vertices of depth 1 in B then

$$S = \{(\mu_1(u))_{u \in V_1} : \mu \text{ invariant for } T\}.$$

*Proof.* By scaling by a computable factor $\alpha < 1$ if necessary, we may assume that $S$ is contained in the interior of $\Delta_n$. By Lemma 5.2 we can compute a decreasing sequence of rational simplices ($S_k$) contained in $\Delta_n$ whose intersection equals $S$ and such that each $S_k$ has $n$ vertices. Proposition 5.1 gives corresponding sets $V_k$ and matrices $A_k$, which in turn can be converted into a computable Bratteli-Vershik system ($X_B, T_B$) by Remark 3.1 and Lemma 3.1. By Proposition 5.1 combined with (8) we have that

$$S = \{(\mu_1(u))_{u \in V_1} : \mu \text{ invariant for } T_B\}.$$

Moreover, since all the $A_k$ are square of size $n$ and of full rank, they are actually invertible matrices, which implies that $S$ is in fact computably affine homeomorphic to the whole inverse limit. □

The next result says that, when $S$ is not necessarily a simplex but just a semicomputable convex set of finite dimension, then it can still be realised as a projection of the set of invariant measures.

**Theorem 5.2.** Let $n \in \mathbb{N}$ and $S \subseteq \Delta_n$ be a semicomputable convex set. Then there exists a computable minimal Bratteli-Vershik system $(X, T)$ with $|V_1| = n$ such that

$$S = \{(\mu_1(u))_{u \in V_1} : \mu \text{ invariant}\}.$$

*Proof.* By Lemma 5.3, there exists a computable decreasing sequence of rational convex polytopes $P_n$ such that $S = \bigcap_n P_n$. Proposition 5.1 gives sets $V_n$ and stochastic rational matrices $A_n$. They can be converted into a Bratteli diagram by Lemma 3.1. □

# 6 Applications

In this section we give two applications of the main results: a computable dynamical system with exactly two ergodic measures, both of which are non-computable, and a reformulation of the main result using subshifts.

## 6.1 Finiteness of ergodic measures does not imply computability

One can apply Theorem 5.1 to obtain for instance a computable Bratteli-Vershik system with exactly two ergodic measures, none of which is computable. Indeed,
up to computably affine homeomorphisms, any semicomputable interval can be realized as the set of invariant measures of a computable Bratteli-Vershik system. We workout explicitly the particular case of a symmetric interval.

**Theorem 6.1.** There exists a computable dynamical system with exactly two ergodic measures, none of which is computable.

<figure><img src="image_2.png" /><figcaption>Figure 1: A Bratteli diagram inducing a Bratteli-Vershik system with two non-computable ergodic measures</figcaption></figure>

*Proof.* We build a Bratteli diagram with $V_n = \{0,1\}$ for all $n$ (but we consider them as different copies). Let $\beta \in (0,1)$ be upper semicomputable but not computable and $\beta_n \in (0,1)$ be a computable sequence of rationals such that $\prod_n \beta_n = \beta$ (start with a computable sequence $b_n \searrow \beta$ with $b_1 = 1$ and take $\beta_n = b_{n+1}/b_n$). Let

$$A_n = \left( \frac{\frac{1+\beta_n}{2}}{\frac{1-\beta_n}{2}}, \frac{\frac{1-\beta_n}{2}}{\frac{1+\beta_n}{2}} \right).$$

Note that $A_n$ is stochastic. In particular one has that

$$A_n \left( \frac{\frac{1+x}{2}}{\frac{1-x}{2}} \right) = \left( \frac{\frac{1+\beta_n x}{2}}{\frac{1-\beta_n x}{2}} \right).$$

Let $\bar{\beta}_n = \beta_1 \dots \beta_n$. Then one can express $A_1 A_2 \dots A_n$ as

$$A_1 \dots A_n = \left( \frac{\frac{1+\bar{\beta}_n}{2}}{\frac{1-\bar{\beta}_n}{2}}, \frac{\frac{1-\bar{\beta}_n}{2}}{\frac{1+\bar{\beta}_n}{2}} \right).$$

Let $p, q \in \mathbb{N}$ be such that $\frac{1+\beta_n}{2} = \frac{p}{q}$ and define positive numbers $X_n = p$ and $Y_n = q - p$. Finally, define the counting matrices by

$$M_n = \begin{pmatrix} X_n & Y_n \\ Y_n & X_n \end{pmatrix},$$
which completely describe the sought Bratteli-Vershik system.

Figure 6.1 shows the Bratteli diagram. From a vertex at depth $n$, there are $X_n$ edges to the vertex below it and $Y_n$ edges to the facing vertex at level $n+1$. Typically, $\beta_n$ is very close to 1, so $X_n$ is much larger than $Y_n$. The quantity $\mu(a)$, where $\mu$ ranges over all the invariant measures, takes all values in the interval $[\frac{1-\beta}{2}, \frac{1+\beta}{2}]$. The extremal values are obtained for the two ergodic measures of the system. As $\beta$ is not computable, those measures are not computable either. $\square$

## 6.2 Minimal Subshifts with prescribed set of invariant measures

Subshifts are an important class of Cantor systems. If $\mathcal{A}$ is a finite alphabet, then $X \subseteq \mathcal{A}^Z$ is computable if the set of cylinders intersecting $X$ is computable.

**Theorem 6.2.** Let $n \in \mathbb{N}$ and $S \subseteq \Delta_n$ be a semicomputable simplex. There are a finite alphabet $\mathcal{A}$ and a computable minimal subshift $X \subseteq \mathcal{A}^Z$ such that $S$ is computably affine isomorphic to the simplex of invariant measures of $(X, \sigma)$. Moreover, if $S$ is not a singleton then there is an invertible rational stochastic matrix $\mathcal{A}$ such that the image of the set

$$ \{(\mu[a])_{a \in \mathcal{A}} : \mu \text{ invariant measure of } (X, \sigma)\} $$

by $\mathcal{A}$ is equal to $S$.

*Proof.* Let $S$ be a semicomputable simplex, which we assume not to be a singleton. By Theorem 5.1, there is a computable Bratteli-Vershik system $(X_B, T_B)$ which is minimal and such that $S$ is computable affine homeomorphic to the simplex of invariant measures of $(X_B, T_B)$. Moreover, for every integer $k \ge 1$ the set of vertices of depth $k$ in the Bratteli diagram $B$ defining $X_B$ is equal to $n$. Together with [DM08, Theorem 1] this implies that $(X_B, T_B)$ is expansive or equicontinuous. But equicontinuity and minimality implies unique ergodicity which contradicts the fact that $S$ is not a singleton. Hence, $(X_B, T_B)$ must be expansive. This means that there exists $\varepsilon > 0$ such that for all $x$ and $y$ in $X_B$, there is $n$ in $\mathbb{Z}$ for which

$$ \mathrm{dist}_{X_B}(T_B^n(x), T_B^n(y)) > \varepsilon. $$

Let us fix some $k \ge 1$ such that $2^{-k} < \varepsilon$. For all $x, y \in X_B$, there exists $n$ such that $T_B^n(x)$ and $T_B^n(y)$ differ at a position smaller than $k$.

Let $\mathcal{A}$ be the finite partition of $X_B$ into cylinders of length $k$. Let $h : X_B \to \mathcal{A}^Z$ associate to each $x \in X_B$ the sequence $(a_n)_{n \in \mathbb{Z}}$ such that $T_B^n(x) \in a_n$ for each $n \in \mathbb{Z}$. As $T_B$ is computable, so is $h$. By expansiveness of $T_B$ and by choice of $k$, $h$ is injective. As a result, $h$ is a computable homeomorphism between $X_B$ and $X := h(X_B) \subseteq \mathcal{A}^Z$, $X$ is a computable subshift and $h$ is a conjugacy between $(X_B, T_B)$ and $(X, \sigma)$.
The invariant measures $\nu$ of $(X_B, T_B)$ are in one-to-one correspondence with the invariant measures $\mu$ of $(X, \sigma)$ by the simple equation, for $u \in V_1$:

$$ \nu(u) = \sum_{a \text{ starts with } u} \mu[a]. \qquad (9) $$

This equality can be expressed in matrix form, defining a $V_1 \times A$-matrix $A$ whose entry $(u, a)$ is 1 if $a$ starts with $u$, 0 otherwise. $\square$

## References

[AGT10] Jeremy Avigad, Philipp Gerhardy, and Henry Towsner. Local stability of ergodic averages. *Transactions of the American Mathematical Society*, 362:261–288, 2010.

[Avi09] Jeremy Avigad. The metamathematics of ergodic theory. *Ann. Pure Appl. Logic*, 157(2-3):64–76, 2009.

[BH21] Vasco Brattka and Peter Hertling, editors. *Handbook of Computability and Complexity in Analysis, Theory and Applications of Computability*, Cham, 2021. Springer.

[BKMS10] Sergey Bezuglyi, Jan Kwiatkowski, Kostyantyn Medynets, and Boris Solomyak. Invariant measures on stationary Bratteli diagrams. *Ergod. Theor. Dyn. Syst.*, 30(4):973–1007, August 2010.

[BP03] Vasco Brattka and Gero Presser. Computability on subsets of metric spaces. *Theoretical Computer Science*, 305(1-3):43–76, 2003.

[DFM15] Fabien Durand, Alexander Frank, and Alejandro Maass. Eigenvalues of Toeplitz minimal systems of finite topological rank. *Ergod. Theor. Dyn. Syst.*, 35(8):2499–2528, 2015.

[DFM18] Fabien Durand, Alexander Frank, and Alejandro Maass. Eigenvalues of minimal Cantor systems. *J. Eur. Math. Soc.*, 2018. (Accepted).

[DM08] Tomasz Downarowicz and Alejandro Maass. Finite-rank Bratteli-Vershik diagrams are expansive. *Ergod. Theor. Dyn. Syst.*, 28(3):739–747, December 2008.

[FT14] Johanna N. Y. Franklin and Henry Towsner. Randomness and non-ergodic systems. *Mosc. Math. J.*, 14(4):711–744, 827, 2014.

[Gác08] Peter Gács. Lecture notes on descriptional complexity and randomness. Technical report, Boston University, 2008. http://www.cs.bu.edu/faculty/gacs/papers/ait-notes.pdf.

[GHR11] Stefano Galatolo, Mathieu Hoyrup, and Cristobal Rojas. Dynamics and abstract computability: computing invariant measures. *Discret. Contin. Dyn. S. Series A*, 29(1):193–212, 2011.
[Hoy14] Mathieu Hoyrup. Irreversible computable functions. In Ernst W. Mayr and Natacha Portier, editors, *31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)*, STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 362-373. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014.

[HPS92] Richard Herman, Ian Putnam, and Christian Skau. Ordered Bratteli diagrams, dimension groups and topological dynamics. *Int. J. Math.*, 3(6):827-864, December 1992.

[HR09] Mathieu Hoyrup and Cristóbal Rojas. Computability of probability measures and Martin-Löf randomness over metric spaces. *Information and Computation*, 207(7):830-847, 2009.

[IK20] Zvonko Iljazović and Takayuki Kihara. Computability of subsets of metric spaces. In Vasco Brattka and Peter Hertling, editors, *Handbook of Computability and Complexity in Analysis*. Springer, 2020.

[LL71] Aldo J. Lazar and Joram Lindenstrauss. Banach spaces whose duals are L1 spaces and their representing matrices. *Acta Math.*, 126:165-193, 1971.

[Neu15] Eike Neumann. Computational problems in metric fixed point theory and their weihrauch degrees. *Logical Methods in Computer Science*, 11(4), Dec 2015.

[Phe01] Robert Phelps. *Lectures on Choquet's theorem*, volume 1757 of Lecture Notes on Mathematics. Springer Berlin Heidelberg, 2001.

[Tur36] Alan Turing. On computable numbers, with an application to the entscheidungsproblem. *Proceedings of the London Mathematical Society*, 2, 42:230-265, 1936.

[V'y97] Vladimir V. V'yugin. Effective convergence in probability and an ergodic theorem for individual random sequences. *SIAM Theory of Probability and Its Applications*, 42(1):39-50, 1997.