# Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts

Andrei Romashchenko, Julien Destombes

► To cite this version:

Andrei Romashchenko, Julien Destombes. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. STACS 2019 - 36th International Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.23:1–23:17, 10.4230/LIPIcs.STACS.2019.23 . lirmm-01793810

HAL Id: lirmm-01793810

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01793810

Submitted on 28 Jun 2019

**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
# Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts

## Julien Destombes

LIRMM, University of Montpellier, Montpellier, France
julien destombes@lirmm.fr

## Andrei Romashchenko

LIRMM, University of Montpellier, CNRS, Montpellier, France
andrei.romashchenko@lirmm.fr

## Abstract

We suggest necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity. Using this technique we provide examples of effective and non-sofic shifts on $Z^2$ with very low block complexity: the number of globally admissible patterns of size $n \times n$ grows only as a polynomial in $n$.

**2012 ACM Subject Classification** Mathematics of computing → Information theory; Mathematics of computing → Combinatorics

**Keywords and phrases** Sofic shifts, Block complexity, Kolmogorov complexity

**Digital Object Identifier** 10.4230/LIPIcs.STACS.2019.23

**Related Version** A full version of the paper is available at https://arxiv.org/abs/1805.03929.

**Funding** projet ANR-15-CE40-0016 RaCAF

**Acknowledgements** We are indebted to Bruno Durand, Alexander Shen, and Ilkka Törmä for fruitful discussions. We are grateful to Pierre Guillon and Emmanuel Jeandel for motivating comments. We also thank the anonymous referees of STACS 2019 for many valuable comments.

# 1 Introduction

Symbolic dynamics originally appeared in mathematics as a branch of the theory of dynamical systems that studies smooth or topological dynamical systems by discretizing the underlying space. Since the late 1930s, symbolic dynamics became an independent field of research, see [9, 10]. A classical dynamical system is a space (of states) $S$ with a function $F$ acting on this space; this function represents the “evolution rule,” i.e., the time dependence of a configuration in the space. The central notion of the theory of dynamical systems is a trajectory – a sequence of configurations obtained by iterating the evolution rules,

$$x, F(x), F(F(x)), \dots, F^{(n)}(x), \dots$$

In symbolic dynamics the space of states reduces to a finite set (an alphabet). The trajectories are represented by infinite (or bi-infinite) sequences of letters over this alphabet, and the “evolution rule” is the shift operator acting on these sequences. Symbolic dynamics focuses on the *shift spaces* – the sets of bi-infinite sequences of letters (over a finite alphabet) that are defined by a shift-invariant constraint on the factors of finite length. More precisely, a *shift* over an alphabet $\Sigma$ is a subset of bi-infinite sequences over $\Sigma$ that is translation invariant and closed in the natural topology of the Cantor space. Every shift can be defined in

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

© Julien Destombes and Andrei Romashchenko; licensed under Creative Commons License CC-BY

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019).

Editors: Rolf Niedermeier and Christophe Paul; Article No. 23; pp. 23:1–23:17

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

Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<figure><img src="image_4.png" /></figure>
## 23:2 An Obstacle to Soficness

terms of forbidden finite patterns: we fix a set of (finite) words $\mathcal{F}$ and say that a configuration (a bi-infinite sequence) belongs to the corresponding shift $S_{\mathcal{F}}$ if and only if it does not contain any factor from $\mathcal{F}$.

Obviously, the properties of shifts heavily depend on the corresponding set of forbidden patterns. The following three large classes of shifts play an important role in symbolic dynamics and computability theory:

- shifts of finite type (SFT), which are defined by a finite set of forbidden finite patterns;

- sofic shifts (introduced in [16]), where the set of forbidden finite patterns is a regular language;

- effective (or effectively closed) shifts, which are defined by a computable set of forbidden finite patterns.

These three classes are different: [the SFTs] $\subsetneq$ [the sofic shifts] $\subsetneq$ [the effective shifts].

The sofic shifts can be equivalently defined as the coordinate-wise projections of configurations from an SFT:

**Definition 1.** A shift $S$ over an alphabet $\Sigma$ is sofic if there is an SFT $S'$ over an alphabet $\Sigma'$ and a mapping $\pi: \Sigma' \to \Sigma$, such that $S$ consists of the coordinate-wise projections

$$ (\dots \pi(y_{-1})\pi(y_0)\pi(y_1)\pi(y_2)\dots) $$

of all configurations $(\dots y_{-1}y_0y_1y_2\dots)$ from $S'$.

There is a simple characterization of soficness. Let us say that two words $w_1, w_2$ are equivalent in a shift $S$, if exactly the same half-infinite configurations occur in $S$ immediately to the right of $w_1$ and to the right of $w_2$. A shift is sofic if and only if the finite patterns in this shift are subdivided in a finite number of equivalence classes (see [8, Theorem 3.2.10]). Loosely speaking, when we read a configuration from the left to the right and verify that it belongs to a sofic shift, we need to keep in mind only a finite information.

The SFTs and even the sofic shifts are rather restrictive classes of shifts with several very special properties. Not surprisingly, many important examples of effective shifts are not sofic. Non-soficness of a shift is usually proved with some version of the pumping lemma from automata theory.

### Multidimensional shifts

The formalism of shifts can be naturally extended to the grids $\mathbb{Z}^d$ for $d > 1$. A shift on $\mathbb{Z}^d$ (over a finite alphabet $\Sigma$) is defined as a set of $d$-dimensional configurations $f: \mathbb{Z}^d \to \Sigma$ that are (i) translation-invariant (under translations in all directions) and (ii) closed in Cantor's topology. Similar to the one-dimensional case, the shifts can be defined in terms of forbidden finite patterns.

The definitions of the effective shifts (the set of forbidden patterns is computable) and of the SFTs (the set of forbidden patterns is finite) apply to the multidimensional shift spaces directly, without any revision. The sofic shifts on $\mathbb{Z}^d$ are defined as in Definition 1 above (as the coordinate-wise projections of SFTs).

For multidimensional shifts spaces, the classes of the effective shifts, the sofic shifts, and the SFTs remain distinct, though the difference between these classes is more elusive than in the one-dimensional case. In this paper we discuss the tools that help to reveal the reasons why one or another effective multidimensional shift is not sofic.

The class of sofic shifts in dimension $d \ge 2$ is surprisingly wide. Besides many simple and natural examples, there are shifts whose soficness follow from rather subtle considerations. For instance, S. Mozes showed that the shift generated by (a natural class of) non deterministic
multidimensional substitutions systems are sofic [11]. L. B. Westrick proved that the two-dimensional shift on the alphabet {0,1} whose configurations consist of squares of 1s of pairwise different sizes on a background of 0s, is sofic; moreover, any effectively closed subshift of this shift is also sofic [17].

On the other hand, there are several examples of effective multidimensional shifts that are known to be non-sofic. In what follows we briefly discuss two of them.

**► Example 2 (the mirror shift).** One of the standard examples of a non-sofic shift is the shift of mirror-symmetric configurations on $Z^2$. Let $\Sigma$ be the alphabet with three letters (e.g., *black*, *white*, and *red*), and the configurations of the shift are all black-and-white configurations (without any red cell) and the configurations with an infinite horizontal line of red cells and symmetric black-and-white half-planes above and below this line, see Fig. 1.

It is easy to see that this shift is effective (the forbidden patterns are those where the red cells are not aligned, and those where the areas above and below the horizontal red line are not symmetric). At the same time, this shift is not sofic. The intuitive explanation of this fact is as follows. Let us focus on a pair of symmetric patterns of size $n \times n$ in black and white, above and below the horizontal red line (see the blue squares in Fig. 1). To make sure that the configuration belongs to the shift, we must “compare” these two patterns with each other. To this end, we need to transmit the information about a pattern of size $n^2$ through its border line (of length $O(n)$). However, in a sofic shift, the “information flow” across a contour of length $O(n)$ is bounded by $O(n)$ bits, and this contradiction implies non-soficness. For a more formal argument see, e.g. [1] and [4], or a similar example [5, Example 2.4].

**► Example 3 (the high complexity shift).** Let $S$ be the set of all binary configurations on $Z^2$ where for each $n \times n$ pattern $P$ its Kolmogorov complexity is quadratic, $C(P) = \Omega(n^2)$. Technically, this means that no globally admissible pattern can be produced by a program of size below $cn^2$, for some factor $c > 0$ (see the formal definition of Kolmogorov complexity below).

This shift is obviously effective: we can algorithmically enumerate the patterns whose Kolmogorov complexity is below the specified threshold. However, this shift is not sofic. This follows from two facts (proven in [2]):

(i) For some $c < 1$, the shift defined above is not empty.

(ii) In every non-empty sofic shift on $Z^2$, there is a configuration where the Kolmogorov complexity of each $n \times n$ pattern is bounded by $O(n)$.

<figure><img src="image_5.png" /><figcaption>■ **Figure 1** A configuration with mirror symmetry with respect to the horizontal red line. The blue squares select two symmetric black-and-white patterns.</figcaption></figure>
23:4 An Obstacle to Soficness

Note that the non-sofic shifts in the two examples above have positive entropy (the number of globally admissible patterns of size $n \times n$ grows as $2^{\Omega(n^2)}$). This is not surprising: the proofs of non-soficness of these shifts use the intuition about the information flows (super-linear amount of information cannot flow through a linear contour). This type of argument can be adapted for several shifts where the number of globally admissible patterns of size $n \times n$ grows slower than $2^{\Omega(n^2)}$ but still faster than $2^{O(n)}$ (see, e.g. [15, Proposition 15]). As it was noticed in [17], “all examples known to the author of effectively closed shifts which are not sofic were obtained by in some sense allowing elements to pack too much important information into a small area.”

This type of argument was formalized as rather general sufficient conditions of non-soficness in [13] and [5]. The theorems by Kass and Madden ([8, Theorem 3.2.10]) and Pavlov ([13, Theorem 1.1]) apply only to the two-dimensional shifts where the number of globally admissible $n \times n$ patterns is greater than $2^{O(n)}$. However, there is no reason to think that this condition is necessary for non-soficness (see, e.g. the discussion in [4, Section 1.2.2]). It is instructive to observe that non-effective non-sofic shifts can have very low block complexity [5, 12].

In this paper we extend the usual approach to the proof of non-soficness. We show that a shift cannot be sofic if the essential information contained in an $n \times n$ pattern cannot be compressed to the size $O(n)$ in bounded time.

The intuition behind our argument is similar to those used in [2] and [5] but with the idea of compression with *bounded computational resources*. This approach applies to several shifts with very low block complexity: we cannot “communicate” the essential information across a contour not because this information is too large, but since we do not have enough time and space to compress it. In particular, we provide examples of non-sofic effective shifts with only polynomial block complexity (and thus zero entropy).

► **Remark 4.** A standard and straightforward approach to the measure of the “*information flow through the border line of a pattern*” uses the notion of *extender*. Let $S$ be a shift and $P$ be a globally admissible pattern for this shift. The *extender* of $P$ in $S$ is the set of all configurations $Q$ completing $P$ to a valid configuration of $S$ (in particular, the support of $Q$ should be the complement of the support of $P$).

Let $S$ be a shift on $Z^2$; denote by $N_k$ the number of different extenders for the patterns with a support of size $k \times k$. (Several patterns can share one and the same extender, so the number of extenders might be much less than the number of globally admissible patterns of this size). It seems natural to interpret $\log N_k$ as “*the information flowing going through the border line*” of a $k \times k$ pattern.

However, this interpretation is deceptive. In a sofic shift the value of $\log N_k$ can grow much faster the length of the border line of the pattern ([5] attributes this observation to unpublished works of C. Hoffman, A. Quas, and R. Pavlov). In fact, for a sofic shift on $Z^2$, the value of $\log N_k$ can grow even as $\Omega(k^2)$. Therefore, we cannot use the asymptotic of $\log N_k$ to prove non-soficness of a multi-dimensional shift. This why we need a subtler implementation of the intuition of “information flows” in the sofic shifts.

The rest of the paper is organized as follows. After recalling the main definitions of the theory of Kolmogorov in the second section, we prove in the third one our main result. In the last section we elaborate our technique to a more general setting; in particular, we show that an argument from [5] (a proof of non-soficness with the method of union-increasing sequences of extenders) can be explained in the language of Kolmogorov complexity.
## 2 Preliminaries

### Kolmogorov complexity

In this section we recall the main definitions of the theory of Kolmogorov complexity. Let $U$ be a (partial) computable function. The complexity of $x$ with respect to the description method $U$ is defined as $C_U(x) := \min\{|p| : U(p) = x\}$.

If there is no $p$ such that $U(p) = x$, we assume that $C_U(x) = \infty$. Here $U$ is understood as a programming language; $p$ is a program that prints $x$; the complexity of $x$ is the length of (one of) the shortest programs $p$ that generate $x$ (on the empty input).

The obvious problem with this definition is its dependence on $U$. The theory of Kolmogorov complexity becomes possible due to the invariance theorem:

**▶ Theorem 5 (Kolmogorov [6]).** *There exists a computable function $U$ such that for any other computable function $V$ there is a constant $c$ such that $C_U(x) \le C_V(x) + c$ for all $x$.*

This $U$ is called an *optimal description method*. We fix an optimal $U$ and in what follows omit the subscript in $C_U(x)$. The value $C(x)$ is called the (plain) Kolmogorov complexity of $x$.

In a similar way, we define Kolmogorov complexity in terms of programs with bounded resources (the time of computation). Let $U$ be a Turing machine; we define the Kolmogorov complexity $C_U^t(x)$ as the length of the shortest $p$ such that $U(p)$ produces $x$ in at most $t$ steps. There exists an *optimal description method $U$* in the following sense: for every Turing machine $V$ we have $C_U^{\text{poly}(t)}(x) \le C_V^t(x) + O(1)$.

For multi-tape Turing machines a slightly stronger statement can be proven:

**▶ Theorem 6 (see [7]; the proof uses the simulation technique from [3]).** *There exists an optimal description method (multi-tape Turing machine) $U$ in the following sense: for every multi-tape Turing machine $V$ there exists a constant $c$ such that $C_U^{ct \log t}(x) \le C_V^t(x) + c$ for all strings $x$.*

We fix such a machine $U$, and in the sequel use for the resource-bounded version of Kolmogorov complexity the notation $C^t(x)$ instead of $C_U^t(x)$. Without loss of generality we may assume that $C(x) \le C^t(x)$ for all $x$ and for all $t$.

We fix a computable enumeration of finite patterns (over a finite alphabet) that assigns a binary string (a *code*) to each pattern in dimension two. In the sequel we take the liberty of talking about Kolmogorov complexity of finite patterns in dimension two (assuming the Kolmogorov complexity of the *codes* of these patterns).

### Shift spaces

In this paper we focus on two-dimensional shifts, though all arguments can be extended to the shifts on $Z^d$ for all $d \ge 2$. A (finite) *pattern* on $Z^2$ over a finite alphabet $\Sigma$ is a mapping from a (finite) subset of $Z^2$ to $\Sigma$; the domain of this mapping is the *support* of the pattern. Sometimes a pattern $P$ with a support $A$ is called a *coloring* of $A$ (the “colors” are letters from $\Sigma$).

For a shift $S$, we say that a pattern $P$ is *globally admissible*, if $P$ is a restriction of a configuration from $S$ to some finite support. For a shift of finite type determined by a set of forbidden patterns $\mathcal{F}$, we say that a pattern is *locally admissible* if it contains no forbidden patterns from $\mathcal{F}$.

The *block complexity* of a shift is a function that gives for each integer $n > 0$ the number of globally admissible patterns of size $n \times n$ (patterns with support $\{1, \dots, n\}^2$) in this shift.
23:6 An Obstacle to Soficness

If a sofic shift $S$ is a coordinate-wise projection of configurations from $\hat{S}$, we say that $\hat{S}$ is a covering of $S$. Every sofic shift has a covering SFT such that the supports of all forbidden patterns in this SFT are pairs of neighboring cells (see, e.g. [8]).

3 High resource-bounded Kolmogorov complexity is compatible with low block complexity

The following theorem was proven implicitly in [2]:

**Theorem 7.** In every non-empty sofic shift $S$ there exists a configuration $x$ such that for all $n \times n$-patterns $P$ in $x$, we have $C^{T(n)}(P) = O(n)$ for a time threshold $T(n) = 2^{O(n^2)}$.

In [2] a weaker version of this theorem is stated: it is claimed only that the plain complexity of $n \times n$ patterns is $O(n)$. However, the argument from [2] implies a bound for a resource-bounded version of Kolmogorov complexity. For the sake of self-containedness, we provide a proof of this theorem in the full version of this paper.

**Theorem 8.** For every $\epsilon > 0$ and for every computable $T(n)$ there exists an effective shift on $\mathbb{Z}^2$ such that for every $n$ and for every globally admissible pattern $P$ of size $n \times n$, we have that

(i) $C(P) = O(\log n)$, and

(ii) $C^{T(n)}(P) = \Omega(n^{2-\epsilon})$.

Theorem 8 is proven is the full version of the paper. In what follows we prove a slightly weaker version of this theorem, which is nevertheless strong enough for our main applications:

**Theorem 8'.** For every computable $T(n)$ there exists an effective shift on $\mathbb{Z}^2$ such that

(i) for every $n$ and for every globally admissible pattern $P$ of size $n \times n$, we have $C(P) = O(\log n)$, and

(ii) for infinitely many $n$ and for every globally admissible pattern $P$ of size $n \times n$, we have that $C^{T(n)}(P) = \Omega(n^{1.5})$.

From Theorem 7 and Theorem 8' we deduce the following corollary:

**Corollary 9.** There exists an effective non-sofic shift on $\mathbb{Z}^2$ with block complexity $\text{poly}(n)$, i.e., with $\le \text{poly}(n)$ globally admissible blocks of size $n \times n$.

**Proof.** We take the shift from Theorem 8' assuming that the threshold $T(n)$ is much greater than $2^{\Omega(n^2)}$ (e.g., we can let $T(n) = 2^{n^3}$). On the one hand, property (ii) of Theorem 8' and Theorem 7 guarantee that this shift is not sofic. On the other hand, property (i) of Theorem 8' implies that the number of globally admissible blocks of size $n \times n$ is not greater than $2^{O(\log n)}$. $\blacksquare$

**Remark 10.** Our proof of Theorem 8 implies a stronger bound than property (i). In fact, instead of the bound $C(P) = O(\log n)$ we can prove that for every globally admissible $n \times n$ pattern $P$ in this shift,

$$C^{\hat{T}(n)}(P) \le \lambda \log n, \qquad (1)$$

where $\lambda$ is a (large enough) constant and $\hat{T}(n)$ is a (large enough) computable function of $n$. The constant $\lambda$ and the threshold $\hat{T}(n)$ can be defined quite explicitly given $T(n)$ and $\epsilon$.

When $\hat{T}(n)$ (compatible with given $\epsilon$ and $T(n)$) is chosen, we can define another shift $S_{T,\epsilon}$ that consists of the configurations where all $n \times n$ patterns $P$ satisfy (1). The shift from
Theorem 8 is a proper subshift of $S_{T,\epsilon}$. Besides all configurations from Theorem 8, the shift $S_{T,\epsilon}$ contains also configurations with patterns of very low time bounded complexity (e.g., the configuration with all 0s and the configuration with all 1s). In the next section we use this shift $S_{T,\epsilon}$ to construct some other examples of effective non-soft shifts.

**Proof of Theorem 8'.** In this proof we construct the required shift explicitly. Let us fix a sequence $(n_i)$ where $n_0$ is a large enough integer number, and

$$n_{i+1} := (n_0 \cdots n_i)^c \quad \text{for } i = 0, 1, 2, \dots, \qquad (2)$$

where $c \ge 3$ is a constant. We set $N_i := n_0 \cdots n_i$. In what follows we construct for each $i$ a pair of standard binary patterns $Q_i^0$ and $Q_i^1$ of size $N_i \times N_i$ such that

- the plain Kolmogorov complexities of the standard patterns $C(Q_i^0)$ and $C(Q_i^1)$ are not greater than $O(\log N_i)$, and

- the resource-bounded Kolmogorov complexities $C^{T(N_i)}(Q_i^0)$ and $C^{T(N_i)}(Q_i^1)$ are not less than $\Omega(N_i^{1.5})$.

The construction is hierarchical: both $Q_i^0$ and $Q_i^1$ are defined as $n_i \times n_i$ matrices composed of patterns $Q_{i-1}^0$ and $Q_{i-1}^1$; for each $i$ the blocks $Q_i^0$ and $Q_i^1$ are bitwise inversions of each other.

When the standard patterns $Q_i^0$ and $Q_i^1$ are constructed for all $i$, we define the shift as the closure of these patterns: we say that a finite pattern is globally admissible if and only if it appears in some standard pattern $Q_i^j$ or at least in a 2 × 2-block composed of $Q_i^0$ and $Q_i^1$ (for some $i$).

**Remark 11.** Due to the hierarchical structure of the standard patterns, we can guarantee that every globally admissible pattern $P$ of size $N_i \times N_i$ appears in a 2 × 2-block composed of $Q_i^0$ and $Q_i^1$ (no need to try the blocks $Q_i^j$ for $s > i$).

Since the construction of $Q_i^j$ is explicit, the resulting shift is effective. Properties (i) and (ii) of the theorem will follow from the properties of the standard patterns.

In what follows we explain an inductive construction of $Q_i^0$ and $Q_i^1$. Let $Q_0^0$ and $Q_1^0$ be the squares composed of only 0s and only 1s respectively. Further, for every $i$ we take the lexicographically first binary matrix $R_i$ of size $n_i \times n_i$ such that

$$C^{t_i}(R_i) \ge n_i^2 \qquad (3)$$

(the time bound $t_i$ is fixed in the sequel). We claim that such a matrix exists. Indeed, there exists a matrix of size $n_i \times n_i$ that is incompressible in the sense of the plain Kolmogorov complexity. The resource-bounded Kolmogorov complexity of a matrix can be only greater than the plain complexity. Therefore, there exists at least one matrix satisfying (3). If $t_i$ is a computable function of $i$, then given $i$ we can find $R_i$ algorithmically.

Now we substitute in $R_i$ instead of each zero and one entry the copies of $Q_{i-1}^0$ and $Q_{i-1}^1$ respectively, e.g.,

$$R_i = \begin{pmatrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \end{pmatrix} \implies Q_i^0 := \begin{pmatrix} Q_{i-1}^0 & Q_{i-1}^0 & Q_{i-1}^0 & Q_{i-1}^0 & Q_{i-1}^1 \\ Q_{i-1}^0 & Q_{i-1}^1 & Q_{i-1}^0 & Q_{i-1}^0 & Q_{i-1}^1 \\ Q_{i-1}^1 & Q_{i-1}^1 & Q_{i-1}^1 & Q_{i-1}^1 & Q_{i-1}^0 \\ Q_{i-1}^0 & Q_{i-1}^1 & Q_{i-1}^1 & Q_{i-1}^0 & Q_{i-1}^0 \\ Q_{i-1}^0 & Q_{i-1}^1 & Q_{i-1}^0 & Q_{i-1}^1 & Q_{i-1}^0 \end{pmatrix}$$

The resulting matrix (of size $N_i \times N_i$) is denoted $Q_i^0$. Matrix $Q_i^1$ is defined as the bitwise inversion of $Q_i^0$.
23:8 An Obstacle to Soficness

<figure><img src="image_6.png" /><figcaption>■ **Figure 2** A pattern of size $N_k \times N_k$ (shown in gray in fig. (a)) covered by a quadruple of standard blocks of the same size contains enough information to reconstruct a standard pattern (fig. (b)).</figcaption></figure>

▷ Claim 12. Assuming that $t'_i \ll t_i$ (in what follows we discuss the choice of $t'_i$ in more detail) we have

$$C^{t'_{i}}(Q_{i}^{0}) = \Omega(N_{i}^{1.5}) \text{ and } C^{t'_{i}}(Q_{i}^{1}) = \Omega(N_{i}^{1.5}).$$

Proof of Claim 12. Given $Q_i^j$ (for $j = 0, 1$) we can retrieve the matrix $R_i$ (this retrieval can be implemented in polynomial time). Therefore, for every time bound $t$

$$C^{t+\text{poly}(N_i)}(R_i) \leq C^t(Q_i^j) + O(1).$$

Therefore, if $t_i > t'_i + \text{poly}(N_i)$ then

$$n_i^2 \leq C^{t_i}(R_i) \leq C^{t'_i}(Q_i^j).$$

It remains to observe that our choice of parameters in (2) with $c \geq 3$ implies $n_i^{1/2} \geq (n_0 \cdots n_{i-1})^{3/2}$, and therefore

$$n_i^2 \geq (n_0 \cdots n_i)^{1.5} = (N_i)^{1.5}.$$

Thus, we obtain $C^{t'_i}(Q_i^j) \geq (N_i)^{1.5} - O(1)$, and the claim is proven. △

► Remark 13. By choosing a larger constant $c$ in (2), we can achieve a lower bound $C^{t'_i}(Q_i^j) = \Omega(n^{2-\epsilon})$ for any $\epsilon > 0$.

▷ Claim 14. For every globally admissible pattern $P$ of size $N_i \times N_i$ (and not only for the standard patterns, as it was in Claim 1) its time-bounded Kolmogorov complexity $C^{T(N_i)}(P)$ is $\Omega(n^{1.5})$ (assuming that $T(N_i) \ll t'_i$).

Proof of Claim 14. If a pattern $P$ of size $N_i \times N_i$ is globally admissible then it is covered by a quadruple of standard patterns of rank $i$, see Remark 11 on p 7 above. Then $P$ can be divided into four rectangles which are “corners” of standard patterns of rank $i$, see Fig. 2 (a). Since the standard blocks $Q_i^0$ and $Q_i^1$ are the inversions of each other, these four “corners” (with a bitwise inversion if necessary) form together the entire standard pattern, as shown in Fig. 2 (b). Therefore, we can reconstruct $Q_i^j$ from $P$ given (a) the position of $P$ with respect to the grid of standard blocks (this involves $O(\log N_i)$ bits) and (b) the four bits identifying the standard blocks covering $P$ (we need to know which of them is a copy of $Q_i^0$ and which one is a copy of $Q_i^1$).
The retrieval of $Q_i^j$ from $P$ requires only poly($N_i$) steps of computation (in addition to the time we need to produce $P$). Now the claim follows from the bound for the resource-bounded Kolmogorov complexity of the standard patterns $Q_i^0$ and $Q_i^1$. ▹

▷ Claim 15. For every $k \times k$-pattern in $Q_i^0$ or $Q_i^1$, its plain Kolmogorov complexity is at most $O(\log k)$.

Proof of Claim 15. First of all, we observe that the standard patterns $Q_i^0$ or $Q_i^1$ can be computed given $i$. Therefore, $C(Q_i^0) = O(\log i)$ and $C(Q_i^1) = O(\log i)$.

Every globally admissible $k \times k$-pattern is covered by at most four standard patterns $Q_i^0$ or $Q_i^1$ with

$$N_{i-1} < k \le N_i,$$

see Remark 11 on p. 7. Therefore, to obtain a globally admissible pattern $P$ of size $k \times k$ we need to produce a quadruple of standard patterns of size $N_i \times N_i$ and then to specify the position of $P$ with respect to the grid of standard blocks. This description consists of only $O(\log N_i)$ bits, and we conclude that $C(P) = O(\log k)$. ▹

Given a computable threshold $T(N_i)$, we choose a suitable $t'_i \gg T(N_i)$ and then a suitable $t_i \gg t'_i$. The theorem follows from Claim 14 and Claim 15. ◀

► Remark 16. For all large enough $i$, the incompressible pattern $R_i$ constructed in the proof of Theorem 8' contains copies of all $2^4$ binary patterns of size $2 \times 2$. Therefore, we can guarantee that every standard block $Q_i^j$ contains all globally admissible patterns of size $N_{i-1} \times N_{i-1}$. It follows that the shift constructed in Theorem 8' is transitive and even minimal.

There exists a non-empty effective shift on $\mathbb{Z}^2$ where the Kolmogorov complexity of all $n \times n$ patterns is $\Omega(n^2)$ (see [2] and [14]). So a natural question arises: can we improve Theorem 8 and strengthen condition (ii) to $C^{T(n)}(P) = \Omega(n^2)$? The answer is negative: we cannot achieve the resource bounded complexity $\Omega(n^2)$, even with a much weaker version of property (i) for the plain complexity:

► Proposition 17. For all large enough time bounds $T(n)$, there is no shift on $\mathbb{Z}^2$ such that
(i) for every globally admissible pattern $P$ of size $n \times n$, we have that $C(P) = o(n^2)$, and
(ii) for infinitely many $n$ and for every globally admissible pattern $P$ of size $n \times n$, we have that $C^{T(n)}(P) = \Omega(n^2)$.

**Proof.** Assume for the sake of contradiction that such a shift exists. For every $k$, the number of globally admissible $k \times k$ patterns in this shift is not greater than

$$L_k \le 2^{o(k^2)} \ll 2^{k^2}.$$

Therefore, for any $N$, every globally admissible pattern $P$ of size $(Nk) \times (Nk)$ can be specified by

- the list of all globally admissible patterns of size $k \times k$ (which requires $L_k \cdot k^2$ bits),

- by an array of $N \times N$ indices of $k \times k$ blocks that constitute $P$ (which requires $N^2 \cdot \log L_k$ bits).

Clearly, $P$ can be reconstructed from such a description in polynomial time. It follows that

$$C^{\text{poly}(Nk)}(P) \le 2^{o(k^2)} \cdot k^2 + N^2 \cdot o(k^2).$$

For $N \gg 2^{o(k^2)}$ this bound contradicts the condition $C^{T(Nk)}(P) = \Omega((Nk)^2)$. ▶
## 4 Epitomes

The technique from Section 3 does not apply to the shifts that contain very simple configurations (with low resource-bounded Kolmogorov complexity of all patterns). In particular, it does not apply to Example 2 from Introduction. In this section we propose a different technique (also based on resource-bounded Kolmogorov complexity) that helps to handle these examples. The intuitive idea behind this technique is as follows: we try to capture the “essential” information in each pattern (discarding irrelevant data) and then measure the resource-bounded Kolmogorov complexity of an “epitome” of this essential information.

Let us fix some notation. We denote by $B_n$ the set $\{0, \dots, n-1\}^2 \subset \mathbb{Z}^2$ and by $F_n$ its complement, $F_n := \mathbb{Z}^2 \setminus B_n$. We say that two patterns with disjoint supports are compatible (for a shift $S$) if the union of these patterns is globally admissible in $S$. In particular, a finite pattern $P$ with support $B_n$ and an infinite pattern $R$ with support $F_n$ are compatible, if the union of these patterns is a valid configuration of the shift.

### 4.1 Plain epitomes

**► Definition 18.** We say that a family of functions

$$ \mathcal{E}_n : [\text{pattern of size } n \times n] \mapsto [\text{binary string}] $$

is a family of epitomes for a shift $S$, if for every globally admissible pattern $P$ with support $B_n$ there exists a pattern $R$ on $F_n$ compatible with $P$ such that for all patterns $P'$ with support $B_n$ compatible with $R$, we have

$$ \mathcal{E}_n(P') = \mathcal{E}_n(P) $$

(i.e., the pattern $R$ on the complement of $B_n$ determines the $\mathcal{E}_n$-epitome of the pattern on $B_n$). We say that a family of epitomes is uniformly computable if there is an algorithm (one algorithm for all $n$) that computes the mappings $\mathcal{E}_n$. If, in addition, $\mathcal{E}_n$ are computable in time $2^{O(n^2)}$, we say that this family of epitomes is exp-time computable.

**► Proposition 19.** For every sofic shift with an exp-time computable family of epitomes $\mathcal{E}_n$, for every globally admissible pattern $P$ of size $n \times n$, we have $C^{T(n)}(\mathcal{E}_n(P)) = O(n)$ for a time threshold $T(n) = 2^{O(n^2)}$.

**► Remark 20.** If patterns $P_1, \dots, P_m$ with support $B_n$ have pairwise distinct epitomes, then these patterns have a union-increasing sequence of extenders in the sense of [5]. Thus, a version of Proposition 19 with the plain (non time bounded) Kolmogorov complexity is a special case of [5, Theorem 2.3].

**Proof.** Assume $S$ is a sofic shift with a covering SFT $\hat{S}$ ($S$ is a coordinate-wise $\pi$-projection of $\hat{S}$). Let $P$ be a pattern with support $B_n$ in $S$ and $R$ be the pattern on the complement of $B_n$ that enforces the value of the $\mathcal{E}_n$-epitome of $P$ (as specified in Definition 18). Denote by $y$ a configuration in $\hat{S}$ whose $\pi$-projection gives the union of $P$ and $R$. Let $Q$ be a pattern of size $n \times n$ in $y$ such that $P$ is a coordinate-wise projection of $Q$, see Fig. 3. Denote by $\partial Q$ the border of $Q$.

We assume that the local constraints in $\hat{S}$ involve only pairs of neighboring nodes in $\mathbb{Z}^2$. Then, every locally admissible pattern $Q'$ of size $n \times n$ that is compatible with the border $\partial Q$, must be compatible with the rest of configuration $y$. Therefore, the $\pi$-projections of these $Q'$ are compatible with $R$. Thus, the $\mathcal{E}_n$-epitomes of the projections of these $Q'$ must be equal to the $\mathcal{E}_n$-epitome of $P$.
<figure><img src="image_7.png" /><figcaption>Figure 3 Projection of an $n \times n$ pattern from an SFT onto a sofic shift.</figcaption></figure>

It follows that $\mathcal{E}_n(P)$ can be computed in time $2^{O(n^2)}$ given only the coloring of the border line $\partial Q$: we use the brute-force search to find one $Q'$ computable with this border, apply projection $\pi$, and then compute the epitome. Observe that the computed projection $\pi(Q')$ may be different from $P$, but the epitome must coincide with the epitome of $P$. Since the size of $\partial Q$ is linear in $n$, we conclude that $C^{2^{O(n^2)}}(P) = O(n)$. ◀

Proposition 19 gives a necessary condition for soficness. To prove that a shift is not sofic, we need to provide an exp-time computable family of epitomes with high resource-bounded Kolmogorov complexities. In what follows we discuss a simple application of this technique.

## Example 2 revisited

Let $\mathcal{S}$ be the shift from Example 2 in the Introduction (the mirror-symmetric configurations). For this example we can define epitome functions $\mathcal{E}_n$ as follows:

- if an $n \times n$ pattern $P$ contains only black and white letters, then $\mathcal{E}_n(P)$ maps it to a binary string of length $n^2$ that identifies $P$ uniquely (roughly speaking, $\mathcal{E}_n$ does not compress the patterns in black and white);

- all patterns with red letters are mapped to the empty string.

It is not hard to see that $\mathcal{E}_n$ is an exp-time computable family of epitomes for this shift (since a configuration below the red line determines all black-and-white patterns above this line). Since for some patterns of size $n \times n$ we have $C(P) \ge n^2$ (i.e., even the plain Kolmogorov complexity of $P$ is super-linear), we can apply Proposition 19 and conclude that the shift is not sofic.

## Example 2 with low plain Kolmogorov complexity

Let us consider a subshift of $\mathcal{S}$: we still admit only symmetric configurations, but we now allow only those $n \times n$ patterns $P$ in black and white that are globally admissible for the shift $S_{T,\epsilon}$ defined in Remark 10 on p. 6, assuming $T(n) = 2^{n^3}$. (We have chosen the time threshold so that $T(n) \gg 2^{O(n^2)}$.) A typical configuration of this shift looks as follows: there is an infinite horizontal line in red, and the symmetric half-planes above and below this line are areas in black and white, with $n \times n$ patterns $P$ such that $C^{T(n)}(P) = O(\log n)$.

The new shift is effective, and the number of globally admissible patterns is $2^{O(\log n)} = \text{poly}(n)$. Due to Theorem 8 know that some $n \times n$ patterns in this shift satisfy the condition $C^{2^{n^3}}(P) = \Omega(n^{2-\epsilon})$.
23:12 An Obstacle to Soficness

We cannot apply Theorem 8 directly and conclude that the new shift is non-soft. Indeed, this shift also admits patterns with very low time-bounded complexity. For example, the shift admits the configuration with an infinite horizontal line in red and only white cells above and below this line.

Note that the functions $\mathcal{E}_n$ defined above provide for this shift an exp-time computable family of epitomes. Since for some (though not for all) $n \times n$ patterns $P$ we have

$$C^{2n^3}(\mathcal{E}_n(P)) = \Omega(n^{2-\epsilon}),$$

it follows from Proposition 19 that the shift is not sofic.

4.2 Ordered epitomes

The argument based on Definition 18 does not apply to [5, Example 2.5] and similar examples. To handle this class of (non-soft) shifts we introduce a slightly more general version for epitomes:

► **Definition 21.** Let $E_n$ be a finite set with a partial order $\le_n$ on it, and

$$\mathcal{E}_n : [\text{pattern of size } n \times n] \mapsto [\text{element of } E_n]$$

be a partial function, for each integer $n > 0$. We say that $(\mathcal{E}_n, \le_n)$ is a family of ordered epitomes for a shift $S$, if for every globally admissible pattern $P$ with support $B_n$ such that $\mathcal{E}_n(P)$ is defined, there exists a pattern $R$ on $F_n$ such that

(i) $R$ is compatible with $P$, i.e., the union of $P$ and $R$ forms a valid configuration in $S$, and

(ii) for every pattern $P'$ on support $B_n$ compatible with $R$, if $\mathcal{E}_n(P')$ is defined then

$$\mathcal{E}_n(P') \le_n \mathcal{E}_n(P)$$

(i.e., this configuration $R$ on the complement of $B_n$ determines the maximum of the $\mathcal{E}_n$-epitomes over all valid $P'$).

We say that a family of ordered epitomes is uniformly computable if there is an algorithm (one algorithm for all $n$) that computes the relations $\le_n$ and the mappings $\mathcal{E}_n$. If, moreover, $\mathcal{E}_n$ and $\le_n$ are computable in time $2^{O(n^2)}$, we say that this family of ordered epitomes is exp-time computable.

► **Remark 22.** When we say that a partial function is *computable* (or *computable in bounded time*), we assume that its domain is decidable (respectively, decidable in bounded time). Thus, for an exp-time computable family of epitomes we can decide effectively whether $\mathcal{E}_n(x)$ is defined.

Definition 18 can be viewed as a special case of Definition 21. If $\mathcal{E}_n$ is a family of exp-time computable epitomes in the sense of Definition 18 and $\le_n$ is an arbitrary effectively computable order on the $\mathcal{E}_n$-epitomes, then $(\mathcal{E}_n, \le_n)$ is an exp-time computable family of ordered epitomes in the sense of Definition 21 (in Definition 18, the neighborhood $R$ enforces the exact value of $\mathcal{E}_n(P')$ over all $P'$ compatible with $R$, while in Definition 21 we need to enforce only the maximum of $\mathcal{E}_n(P')$).

► **Proposition 23.** For every sofic shift with an exp-time computable ordered family of epitomes $(\mathcal{E}_n, \le_n)$, for every globally admissible pattern $P$ of size $n \times n$, $C^{T(n)}(\mathcal{E}_n(P)) = O(n)$ for a time threshold $T(n) = 2^{O(n^2)}$.
**Proof.** The proof is similar to the proof of Proposition 19, except for the last part. In the previous proof, we use brute-force search to find one pattern $Q'$ compatible with the given border line $\partial Q$, apply projection $\pi$, and then compute the epitome. Now we should find all patterns $Q'$ compatible with $\partial Q$, apply to each of them the projection $\pi$, try to compute their epitomes ($\mathcal{E}_n$ is partial), and then take the maximum of the obtained results. It remains to notice that for an exp-time computable ordered family of epitomes this exhaustive search runs in time $2^{O(n^2)}$.

<figure><img src="image_8.png" /><figcaption>(a) Forbidden pattern: a square with a red top and a black bottom.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(b) A pattern for which the epitome $\mathcal{E}_n$ is defined: each row starts with a few black cells on the left followed by white cells on the right.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(c) A pair of incomparable patterns.</figcaption></figure>

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

Figure 4

**► Example 24 (the shift with no hidden red-black squares).** Now we discuss an example proposed by Kass and Madden in [5, Example 2.5], and reformulate the argument given in [5] in the language of Kolmogorov complexity, in terms of ordered epitomes.

Let $\Sigma$ be the alphabet with three letters (e.g., *black*, *white*, and *red*), and the forbidden patterns be all squares (of all sizes) where the top side consists of red cells, and the bottom one consists of black cells (*hidden red-black squares*), as shown in Fig. 4a.

**► Proposition 25 ([5]).** The shift on $\mathbb{Z}^2$ defined by the set of forbidden patterns specified above is not *sofic*.

In [5] this proposition was proven with the technique of *union-increasing sequence of extenders*. In what follows we propose a similar argument, but explain it in terms of ordered epitomes.

**Proof of Proposition 25.** We define for this shift a family of ordered epitomes. First of all, we define a class of *simple patterns*: the simple patterns are all square patterns that (i) consist of only black and white letters (with no red letters), where (ii) every row starts with a few successive black letters followed by a sequence of white letters, as show in Fig. 4b. Every simple pattern of size $n \times n$ can be specified by its *profile* – a tuple of integers $(k_1, \dots, k_n)$, where $k_i$ is the number of black cells in the $i$-th row of the pattern. (Thus, a simple pattern with the profile $(k_1, \dots, k_n)$ is an $n \times n$ square where each $i$-th row starts with $k_i$ black letters followed by $(n-k_i)$ white letters.)

Let epitome $\mathcal{E}_n$ assign to each simple pattern its profile, and be undefined for all other patterns. For example, for the pattern $P$ show in Fig. 4b we have $\mathcal{E}_8(P) = (4, 3, 8, 5, 4, 2, 4, 6)$.

We introduce the natural order $\leq_n$ on the profiles of simple patterns of size $n \times n$; we say that the profile of $P_1$ is *not greater* than the profile of $P_2$, if the first profile is coordinate-wise not greater than the second profile. For example, the profiles of the two patterns shown in Fig. 4c are not greater than the profile of the pattern in Fig. 4b (and incomparable with each other).

The introduced $\mathcal{E}_n$ and $\leq_n$ are obviously computable, even in polynomial time. Some work is required to show that $\mathcal{E}_n$ and $\leq_n$ satisfy Definition 21:
<figure><img src="image_12.png" /><figcaption>■ **Figure 5** An $n \times n$ pattern $P$ with a neighborhood that enforces the desired maximum of $\mathcal{E}_n$.</figcaption></figure>

**▶ Lemma 26.** The defined above ($\mathcal{E}_n, \le_n$) provide a family of exp-time computable ordered epitomes for the shift under consideration.

This lemma is proven implicitly in [5]. In what follows, for the sake of self-containedness, we sketch this proof.

**Proof of Lemma 26.** For every simple pattern $P$ of size $n \times n$ we should construct a configuration $R$ on the complement of $B_n$, so that

(i) $P$ and $R$ are compatible,

(ii) for every other simple pattern $P'$ compatible with $R$ we have $\mathcal{E}_n(P') \le_n \mathcal{E}_n(P)$.

We build $R$ by following the construction from [5]. By definition, each row of $P$ consists of a contiguous sequence of black cells followed by a contiguous sequence of white cells, as shown in Fig. 4b. The pattern $R$ will consist of a finite number of black and red cells (the other cells will be white).

*Black cells in R.* To construct $R$, we extend each stripes of black cells in $P$ to the left, so that in the first line we get a contiguous sequence of $(3n-1)$ black cells (including those black cells that belong to $P$), in the second line a contiguous sequence of $(3n-3)$ black cells, in the third line a contiguous sequence of $(3n-5)$ black cells, etc. In the $n$-th line we obtain a contiguous sequence of $(n+1)$ black cell, see Fig. 5.

*Red cells in R.* Similarly, we put in $R$ stripes of red cells: $3n$ contiguous red cells in line $3n$, $(3n-2)$ contiguous red cells in line $3n-1$, ..., $(n+2)$ contiguous red cells in line $(2n+1)$. We place these stripes of red cells so that for each $i = 1, \dots, n$ the leftmost red cell in the line $(3n - i + 1)$ is vertically aligned with the leftmost black cell in the line $i$, as shown in Fig. 5.

All other cells outside $B_n$ are made white.

▷ Claim 27. The constructed $R$ is compatible with $P$.

**Proof of Claim 27.** This fact is easy to verify: we have chosen the lengths of black and red stripes so that they cannot form a forbidden pattern (as in Fig. 4a), regardless the horizontal placement of each stripes. Indeed, on the one hand, the black cells of the $i$-th line cannot
interfere with the red stripes in lines $3n, 3n-1, ..., 3n-i$, since *this black stripe* is too short to form a forbidden pattern together with any of these red stripes; on the other hand, the black cells of the *i*-th line cannot interfere with the red stripes in lines $3n-i-1, 3n-i-2, ..., 2n+1$, since *those red stripes* are too short. ◁

▷ Claim 28. The constructed pattern $R$ is compatible only with simple patterns $P'$ such that $\mathcal{E}_n(P') \le_n \mathcal{E}_n(P)$.

Proof of Claim 28. If $R$ is compatible with an $n \times n$ pattern $P'$, the profile of $P'$ is not determined uniquely. In fact, $R$ can be compatible with simple patterns $P'$ whose profiles are *strictly less* than the profile of $P$ (in each row of $P'$ the number of black cells must be not greater than the number of black cells in the corresponding row of $P$), see Fig. 6 below. On the other hand, if at least one row of $P'$ contains more black cells than the same row in $P$, then $P'$ and $R$ are incompatible, i.e., the joint of $P'$ and $R$ contains a forbidden pattern, as shown in Fig. 7. ◁

The lemma follows from Claim 27 and Claim 28. For a more detailed argument we refer the reader to [5]. ◁

► Remark 29. In the construction discussed above, pattern $R$ does not determine uniquely the epitomes of $P'$ compatible with $R$ (these epitomes can be different, though they must be *not greater* than the epitome of the initial pattern $P$). This is why we cannot apply Proposition 19, and we have to employ the extended definition of *partial* epitomes.

To prove the proposition, it remains to observe that for every $n$ there are $(n+1)^n$ simple patterns of size $n \times n$ (in each row of a simple pattern the frontier between black and white areas varies between 0 and $n$). Therefore, for some simple patterns $P$ of size $n \times n$ the Kolmogorov complexity of their profile is greater than $n \log(n+1)$, i.e., even the plain Kolmogorov complexity $C(P)$ is super-linear. We apply Proposition 23 and conclude that the shift is not sofic. ◁

<figure><img src="image_13.png" /><figcaption>Figure 6 A pattern $P'$ with $\mathcal{E}_n(P') \le_n \mathcal{E}_n(P)$ matches the neighborhood.</figcaption></figure>

► Open Problem 1. Is there any *sufficient* condition of sofiveness for effective shifts that can be formulated in terms of resource-bounded Kolmogorov complexity?
23:16 An Obstacle to Soficness

<figure><img src="image_14.png" /><figcaption>Figure 7 A pattern $P''$ with $\mathcal{E}_n(P'') \not\subseteq \mathcal{E}_n(P)$ does not match the neighborhood.</figcaption></figure>

**▶ Open Problem 2.** The shift in Example 24 has positive entropy, and in the argument discussed above we could employ the definition of uniformly computable (but not exp-time computable) ordered epitomes. It would be interesting to suggest a natural example of an effective (but non-sofic) shift where the technique of *exp-time computable* ordered epitomes is valid while *uniformly computable but not exp-time computable* ordered epitomes do not apply.

References

1. N. Aubrun, S. Barbieri, and E. Jeandel. About the Domino Problem for Subshifts on Groups. Sequences, Groups, and Number Theory. *Birkhäuser, Cham*, pages 331–389, 2018.

2. B. Durand, L. Levin, and A. Shen. Complex tilings. *The Journal of Symbolic Logic*, 73:2:593–613, 2008.

3. F.C. Hennie and R.E. Stearns. Two-tape simulation of multitape Turing machines. *Journal of the ACM*, 13(4):533–546, 1966.

4. E. Jeandel. Propriétés structurelles et calculatoires des pavages. *Habilitation thesis, Université Montpellier 2*, 2011.

5. S. Kass and K. Madden. A sufficient condition for non-soficness of higher-dimensional subshifts. *Proceedings of the American Mathematical Society*, 141:11:3803–3816, 2013.

6. A. N. Kolmogorov. Three approaches to the quantitative definition of information. *Problems of information transmission*, 1:1:1–7, 1965.

7. M. Li and P. Vitányi. An introduction to Kolmogorov complexity and its applications. 3rd ed. Springer, New York, 2008.

8. D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding. *Cambridge University Press*, 1995.

9. M. Morse and G.A. Hedlund. Symbolic dynamics. *Amer. J. Math.*, 60:815–866, 1938.

10. M. Morse and G. A. Hedlund. Symbolic dynamics II: Sturmian trajectories. *Amer. J. Math.*, 62:1–42, 1940.

11. S. Mozes. Tilings, substitution systems and dynamical systems generated by them. *Journal d'analyse mathématique (Jerusalem)*, 53:139–186, 1989.

12. N. Ormes and R. Pavlov. Extender sets and multidimensional subshifts. *Ergodic Theory and Dynamical Systems*, 36:3:908–923, 2016.

13. R. Pavlov. A class of nonsofic multidimensional shift spaces. *Proceedings of the American Mathematical Society*, 141:3:987–996, 2013.
14 A. Rumyantsev and M. Ushakov. Forbidden substrings, Kolmogorov complexity and almost periodic sequences. *In Proc. Annual Symposium on Theoretical Aspects of Computer Science*, pages 396–407, 2006.

15 V. Salo. Subshifts with sparse projective subdynamics. *arXiv preprint*, arXiv:1605.09623, 2016.

16 B. Weiss. Subshifts of finite type and sofic systems. *Monatsh. Math.*, 77:462–474, 1973.

17 L.B. Westrick. Seas of squares with sizes from a $\Pi_1^0$ set. *Israel Journal of Mathematics*, 22:1, 2017.