$$ (q\lfloor\alpha\rfloor - \lfloor q\alpha \rfloor) \in \left\{ -\frac{n-1}{m}, -\frac{n-2}{m}, \dots, \frac{m-1}{m} \right\} $$

Now suppose we have incarry $c_i \in S$ and $c_i = q\mathcal{B}(\alpha)_{i-1} - \mathcal{B}(q\alpha)_{i-1}$:

$$ \begin{aligned} c_i + q b(\alpha)_i - b(q\alpha)_i &= q\mathcal{B}(\alpha)_{i-1} - \mathcal{B}(q\alpha)_{i-1} \\ &\quad + q\mathcal{B}(\alpha)_i - q\mathcal{B}(\alpha)_{i-1} \\ &\quad - \mathcal{B}(q\alpha)_i + \mathcal{B}(q\alpha)_{i-1} \\ &= (q\mathcal{B}(\alpha)_i - \mathcal{B}(q\alpha)_i) \\ &= (q\lfloor i\alpha \rfloor - \lfloor qi\alpha \rfloor) \in S \end{aligned} $$

It is thus possible to obtain $b(q\alpha)$ by multiplying $b(\alpha)$ by $q$ using only carries from $S$. $\square$

So we now know that multiplying balanced representations by some positive rational can yield balanced representations. Let us now see in the next subsection how this translates to aperiodic tilings.

## 5.3 An aperiodic tileset

The idea now is to use the fact that our multiplication uses only a finite number of rational carries (see Lemma 2) to implement multiplication by using non-deterministic transducers.

For a multiplication by $q = \frac{n}{m}$, the states will correspond to the possible carries:

$$ S = \left\{ -\frac{n-1}{m}, -\frac{n-2}{m}, \dots, \frac{m-1}{m} \right\} $$

The idea is to take balanced representations of numbers that belong only to the interval $[1, 3]$, avoiding any possible representation of 0. In particular, numbers in $[1, 1.5]$ will be multiplied by 2 and numbers in $[1.5, 3]$ by $\frac{2}{3}$. The alphabet on which the transducers will act will hence be $\Sigma = \{1, 2, 3\}$. The transition table will contain all transitions

$$ s \xrightarrow{a|b} s' $$

verifying $aq + s = b + s'$.

We can now construct a tileset corresponding to our transducer: for each transition we get one tile where the bottom and top represent the input and the output respectively and the left and right edges represent the inward carry and the outward carry respectively.

So in order to apply multiplications by 2 and $\frac{2}{3}$ we need two different transducers and corresponding sets of tiles. We can assume their set of states is disjoint, up to renaming the states. Limiting the output of the transducer multiplying by 2 to $\{2, 3\}$ de facto limits the input interval to $[1, 1.5]$.
$$ (q\lfloor\alpha\rfloor - \lfloor q\alpha \rfloor) \in \left\{ -\frac{n-1}{m}, -\frac{n-2}{m}, \dots, \frac{m-1}{m} \right\} $$

Now suppose we have incarry $c_i \in S$ and $c_i = q\mathcal{B}(\alpha)_{i-1} - \mathcal{B}(q\alpha)_{i-1}$:

$$ \begin{aligned} c_i + q b(\alpha)_i - b(q\alpha)_i &= q\mathcal{B}(\alpha)_{i-1} - \mathcal{B}(q\alpha)_{i-1} \\ &\quad + q\mathcal{B}(\alpha)_i - q\mathcal{B}(\alpha)_{i-1} \\ &\quad - \mathcal{B}(q\alpha)_i + \mathcal{B}(q\alpha)_{i-1} \\ &= (q\mathcal{B}(\alpha)_i - \mathcal{B}(q\alpha)_i) \\ &= (q\lfloor i\alpha \rfloor - \lfloor qi\alpha \rfloor) \in S \end{aligned} $$

It is thus possible to obtain $b(q\alpha)$ by multiplying $b(\alpha)$ by $q$ using only carries from $S$. $\square$

So we now know that multiplying balanced representations by some positive rational can yield balanced representations. Let us now see in the next subsection how this translates to aperiodic tilings.

## 5.3 An aperiodic tileset

The idea now is to use the fact that our multiplication uses only a finite number of rational carries (see Lemma 2) to implement multiplication by using non-deterministic transducers.

For a multiplication by $q = \frac{n}{m}$, the states will correspond to the possible carries:

$$ S = \left\{ -\frac{n-1}{m}, -\frac{n-2}{m}, \dots, \frac{m-1}{m} \right\} $$

The idea is to take balanced representations of numbers that belong only to the interval $[1, 3]$, avoiding any possible representation of 0. In particular, numbers in $[1, 1.5]$ will be multiplied by 2 and numbers in $[1.5, 3]$ by $\frac{2}{3}$. The alphabet on which the transducers will act will hence be $\Sigma = \{1, 2, 3\}$. The transition table will contain all transitions

$$ s \xrightarrow{a|b} s' $$

verifying $aq+s=b+s'$.

We can now construct a tileset corresponding to our transducer: for each transition we get one tile where the bottom and top represent the input and the output respectively and the left and right edges represent the inward carry and the outward carry respectively.

So in order to apply multiplications by 2 and $\frac{2}{3}$ we need two different transducers and corresponding sets of tiles. We can assume their set of states is disjoint, up to renaming the states. Limiting the output of the transducer multiplying by 2 to $\{2, 3\}$ de facto limits the input interval to $[1, 1.5]$.
<figure><img src="image_32.png" /><figcaption>**Fig. 26** On the left the transducer corresponding to multiplication by 2 and on the right the corresponding tiles. Notice how the input must belong to $\{1,2\}$ and the outputs to $\{2,3\}$, which translates the fact that the input belongs to $[1,2]$ and the output to $[2,3]$.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>**Fig. 27** The transducer corresponding to multiplication by $\frac{2}{3}$ for inputs in $[1,2]$ and outputs in $[1,3]$.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>**Fig. 28** The set of tiles for the multiplication by $\frac{2}{3}$. We assume the 0 of this part of the tileset is different from the one of the multiplication by 2.</figcaption></figure>
<figure><img src="image_32.png" /><figcaption>**Fig. 26** On the left the transducer corresponding to multiplication by 2 and on the right the corresponding tiles. Notice how the input must belong to $\{1,2\}$ and the outputs to $\{2,3\}$, which translates the fact that the input belongs to $[1,2]$ and the output to $[2,3]$.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>**Fig. 27** The transducer corresponding to multiplication by $\frac{2}{3}$ for inputs in $[1,2]$ and outputs in $[1,3]$.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>**Fig. 28** The set of tiles for the multiplication by $\frac{2}{3}$. We assume the 0 of this part of the tileset is different from the one of the multiplication by 2.</figcaption></figure>
**Lemma 4.** *The tileset T tiles the plane.*

*Proof.* Take some irrational real $\alpha$ in $[1,3]$, one can tile $\mathbb{Z} \times \mathbb{N}$, by applying iteratively a multiplication by 2 to $b(\alpha)$ when $\alpha \in [1, 1.5]$ and a multiplication by $\frac{2}{3}$ when $\alpha \in [1.5, 3]$; the result always stays in $[1,3]$. By compactness the tileset then tiles the whole plane.
□

We now know that we can tile the plane aperiodically however, lines of a valid tiling do not necessarily correspond to a balanced representation, we therefore still have to prove that the tileset always tiles aperiodically.

**Lemma 5.** *The tileset T tiles only aperiodically.*

*Proof.* Suppose $T$ tiles periodically, then there exists a tiling $c: \mathbb{Z}^2 \to T$ periodic in both directions. Let $a$ and $b$ be its horizontal and vertical periods respectively and let $x_i$ be the finite sum of the values represented on top of $c(1,i)$ to $c(a,i)$. Since all the values are positive, $x_i$ cannot be zero. And since the carry on the left is equal to the carry on the right of the period, $x_i = q_i x_{i-1}$ with $q_i$ equal to 2 or $\frac{2}{3}$.

Therefore, $x_0 = q_n \cdots q_1 x_0$ which is imposible since no nonempty product of 2's and $\frac{2}{3}$'s can equal 1.
□

See Figure 29 for an example of tiling by this tileset. The tileset obtained here is not Kari's tileset but a tileset built using the same techniques. Kari's original tileset used only numbers in the interval $[\frac{1}{2}, 2]$ but still used multiplications by 2 and $\frac{2}{3}$ and used a technical trick to avoid 0.

## 5.4 Undecidability

What is interesting about this construction of aperiodic tilesets is that it allows a different encoding of computation: we will use piecewise affine maps in order to encode computations. While in the usual encoding of Turing machines in tilesets, the head and the current state are explicitly encoded in some tile, using piecewise affine functions will allow to encode the state implicitly in two real numbers representing the full instantaneous description of the Turing machine at some timestep.

### 5.4.1 Computing with piecewise affine maps

Let us first explain how Turing machine computations may be encoded by piecewise affine maps. Let $M$ be a Turing machine working on alphabet $\Gamma = \{0,1\}$ and with state set $Q = \{0, \dots, n\}$.

Let $(c,h,q) \in \Gamma^{\mathbb{Z}} \times \mathbb{Z} \times Q$ be an ID of said Turing machine. We will encode this ID inside two real numbers $(l,r)$ so that the fractional part of $l$ and $r$ will encode the left and right side of the infinite tape respectively and $\lfloor l \rfloor$ will encode the symbol currently under the head and $\lfloor r \rfloor$ the current state of the machine. This encoding will
**Lemma 4.** *The tileset T tiles the plane.*

*Proof.* Take some irrational real $\alpha$ in $[1,3]$, one can tile $\mathbb{Z} \times \mathbb{N}$, by applying iteratively a multiplication by 2 to $b(\alpha)$ when $\alpha \in [1, 1.5]$ and a multiplication by $\frac{2}{3}$ when $\alpha \in [1.5, 3]$; the result always stays in $[1,3]$. By compactness the tileset then tiles the whole plane.

□

We now know that we can tile the plane aperiodically however, lines of a valid tiling do not necessarily correspond to a balanced representation, we therefore still have to prove that the tileset always tiles aperiodically.

**Lemma 5.** *The tileset T tiles only aperiodically.*

*Proof.* Suppose $T$ tiles periodically, then there exists a tiling $c: \mathbb{Z}^2 \to T$ periodic in both directions. Let $a$ and $b$ be its horizontal and vertical periods respectively and let $x_i$ be the finite sum of the values represented on top of $c(1,i)$ to $c(a,i)$. Since all the values are positive, $x_i$ cannot be zero. And since the carry on the left is equal to the carry on the right of the period, $x_i = q_i x_{i-1}$ with $q_i$ equal to $2$ or $\frac{2}{3}$.

Therefore, $x_0 = q_n \cdots q_1 x_0$ which is imposible since no nonempty product of 2's and $\frac{2}{3}$'s can equal 1.

□

See Figure 29 for an example of tiling by this tileset. The tileset obtained here is not Kari's tileset but a tileset built using the same techniques. Kari's original tileset used only numbers in the interval $[\frac{1}{2}, 2]$ but still used multiplications by 2 and $\frac{2}{3}$ and used a technical trick to avoid 0.

## 5.4 Undecidability

What is interesting about this construction of aperiodic tilesets is that it allows a different encoding of computation: we will use piecewise affine maps in order to encode computations. While in the usual encoding of Turing machines in tilesets, the head and the current state are explicitly encoded in some tile, using piecewise affine functions will allow to encode the state implicitly in two real numbers representing the full instantaneous description of the Turing machine at some timestep.

### 5.4.1 Computing with piecewise affine maps

Let us first explain how Turing machine computations may be encoded by piecewise affine maps. Let $M$ be a Turing machine working on alphabet $\Gamma = \{0,1\}$ and with state set $Q = \{0, \dots, n\}$.

Let $(c,h,q) \in \Gamma^{\mathbb{Z}} \times \mathbb{Z} \times Q$ be an ID of said Turing machine. We will encode this ID inside two real numbers $(l,r)$ so that the fractional part of $l$ and $r$ will encode the left and right side of the infinite tape respectively and $\lfloor l \rfloor$ will encode the symbol currently under the head and $\lfloor r \rfloor$ the current state of the machine. This encoding will
<figure><img src="image_35.png" /><figcaption>**Fig. 29** An example of tiling, the bottom row starts from the balanced representation of $\phi + 1$, and the transducers are then applied according to which interval the resulting multiplied integer belongs to.</figcaption></figure>
<figure><img src="image_35.png" /><figcaption>**Fig. 29** An example of tiling, the bottom row starts from the balanced representation of $\phi + 1$, and the transducers are then applied according to which interval the resulting multiplied integer belongs to.</figcaption></figure>
be done in a way reminiscent of Cantor middle thirds: if the symbol currently under the head is 1, then $l \in [2, 3]$ and if it is 0 then $l \in [0, 1]$.

Knowing the state of the machine is thus equivalent to determining to which $[k, k+1]$ interval $r$ belongs to, moving to a new state corresponds to adding/sub- subtracting some integer to $r$ and moving the head corresponds to shifting (multiplying) the tape and writing the new symbol (adding a constant).

The transition function hence corresponds to applying a rational piecewise affine map depending only on $\lfloor r \rfloor$ and $\lfloor l \rfloor$. This map will not be defined on $[1, 2]$ reflecting the fact that $[1, 2]$ does not code for any valid symbol of the tape.

Let's see an example, with the Turing machine in state $q$ and the following tape:

...0000101001001.1.010101010101010101010...

$(l, r)$ can be as follows:

$$l = 2.2002002020000\dots$$

$$r = q.02020202020202020\dots$$

If the machine goes from state $q$ to state $q'$, writes $s$ and shifts the tape to the right, it is equivalent to do the following operations on $l$ and $r$:

$$l := (l - \lfloor l \rfloor) \cdot 10$$

$$r := ((r - \lfloor r \rfloor) + 2 \cdot s)/10 + q'$$

which leads to the following new values of $l$ and $r$:

$$l = 2.002002020000\dots$$

$$r = q'.(2s)02020202020202020\dots$$

Thus our Turing machine has become a set of affine maps whose application depend only on which rational intervals $r$ and $l$ belong to. Let us now formalize this.

**Definition 23.** $(l, r)$ is a valid coding of ID $(c, h, q)$ iff

* for any $i \in \mathbb{N}$, $10(10^i \cdot l - \lfloor 10^i \cdot l \rfloor)$ is in $[0, 1]$ when $c_{h-i} = 0$ and is in $[2, 3]$ when $c_{h-i} = 1$,

* for any $i \in \mathbb{N}^*$, $10(10^i \cdot r - \lfloor 10^i \cdot r \rfloor)$ is in $[0, 1]$ when $c_{h+i} = 0$ and is in $[2, 3]$ when $c_{h+i} = 1$,

* and $\lfloor r \rfloor \in \mathbb{Q}$.

**Theorem 14.** Let $M$ be a Turing machine and $f$ a piecewise affine map constructed as stated before:

1. If $c$ is an ID of $M$, and $(l, r)$ a valid coding of $c$, then $f(l, r)$ is a valid coding of $c'$ the ID obtained after one more step of $M$.

2. If $(l, r)$ is such that $f^n(l, r)$ is defined for all $n \in \mathbb{N}$, then there exists an ID $c$ and a valid coding $(l', r')$ of $c$ such that $f^n(l', r')$ is defined for all $n \in \mathbb{N}$.
be done in a way reminiscent of Cantor middle thirds: if the symbol currently under the head is 1, then $l \in [2, 3]$ and if it is 0 then $l \in [0, 1]$.

Knowing the state of the machine is thus equivalent to determining to which $[k, k+1]$ interval $r$ belongs to, moving to a new state corresponds to adding/sub- subtracting some integer to $r$ and moving the head corresponds to shifting (multiplying) the tape and writing the new symbol (adding a constant).

The transition function hence corresponds to applying a rational piecewise affine map depending only on $\lfloor r \rfloor$ and $\lfloor l \rfloor$. This map will not be defined on $[1, 2]$ reflecting the fact that $[1, 2]$ does not code for any valid symbol of the tape.

Let's see an example, with the Turing machine in state $q$ and the following tape:

...0000101001001.1.010101010101010101010...

$(l, r)$ can be as follows:

$$l = 2.2002002020000\dots$$

$$r = q.02020202020202020\dots$$

If the machine goes from state $q$ to state $q'$, writes $s$ and shifts the tape to the right, it is equivalent to do the following operations on $l$ and $r$:

$$l := (l - \lfloor l \rfloor) \cdot 10$$

$$r := ((r - \lfloor r \rfloor) + 2 \cdot s)/10 + q'$$

which leads to the following new values of $l$ and $r$:

$$l = 2.002002020000\dots$$

$$r = q'.(2s)02020202020202020\dots$$

Thus our Turing machine has become a set of affine maps whose application depend only on which rational intervals $r$ and $l$ belong to. Let us now formalize this.

**Definition 23.** $(l, r)$ is a valid coding of ID $(c, h, q)$ iff

* for any $i \in \mathbb{N}$, $10(10^i \cdot l - \lfloor 10^i \cdot l \rfloor)$ is in $[0, 1]$ when $c_{h-i} = 0$ and is in $[2, 3]$ when $c_{h-i} = 1$,

* for any $i \in \mathbb{N}^*$, $10(10^i \cdot r - \lfloor 10^i \cdot r \rfloor)$ is in $[0, 1]$ when $c_{h+i} = 0$ and is in $[2, 3]$ when $c_{h+i} = 1$,

* and $\lfloor r \rfloor \in \mathbb{Q}$.

**Theorem 14.** Let $M$ be a Turing machine and $f$ a piecewise affine map constructed as stated before:

1. If $c$ is an ID of $M$, and $(l, r)$ a valid coding of $c$, then $f(l, r)$ is a valid coding of $c'$ the ID obtained after one more step of $M$.

2. If $(l, r)$ is such that $f^n(l, r)$ is defined for all $n \in \mathbb{N}$, then there exists an ID $c$ and a valid coding $(l', r')$ of $c$ such that $f^n(l', r')$ is defined for all $n \in \mathbb{N}$.
*Proof.* 1. is straightforward. For 2., let (l,r) be such reals, suppose (l,r) is not a valid coding, and let $l = \sum_{i=0}^{\infty} l_i 10^{-i}$ and $r = \sum_{i=0}^{\infty} r_i 10^{-i}$, since (l,r) is not valid, this means that some $l_i$ and $r_i$ are not zeroes or twos, but since $f^n(l,r)$ is always defined, this also means that these never appear as $l_0$, so the computation to which they correspond is a computation that never reaches them. It then suffices to replace them by zeroes to obtain a valid coding, c then corresponds to this valid coding. See [12] for a more precise proof. □

Using two disjoint sets like $[0,1]$ and $[2,3]$ allows us to avoid some decoding problems that would necessarily happen if the tape was directly coded with its representation in binary<fnref n="3" />.

### 5.4.2 Undecidability of the Domino Problem

The piecewise affine map that we have constructed can easily be transformed into a set of tiles: it has rational coefficients, adding or subtracting a rational number can be done in a similar way to what was done for multiplication and the fact that we are now considering two reals and not only one does not constitute an obstacle, the transducers can as easily be constructed.

The outputs of any transducer coding for a transition will belong either to $\{0,1\}$ or to $\{2,3\}$, thus ensuring that numbers written on one row either belong to $[0,1]$ or to $[2,3]$ and that invalid codings can never appear as a result of applying piecewise affine map.

In order to obtain the undecidability of the domino problem, we will use the immortality problem:

**Theorem 8 (Hooper [25]).** There is no algorithm that, given a Turing machine *M*, decides if *M* halts on all configurations.

*This is still true if we restrict ourselves to Turing machines with a working alphabet of size 2.*

By not having any representation for any halting state in the tileset corresponding to the piecewise affine map, any tiling by this tileset will represent an infinite computation of our Turing machine. And thus the tileset will only be able to tile a half plane if the Turing machine is immortal, by compactness, if the tileset tiles the half plane, it tiles the whole plane.

<footnote n="3">³ The representations 0.100... and 0.011... code the same real but should not encode the same tape</footnote>
*Proof.* 1. is straightforward. For 2., let (l,r) be such reals, suppose (l,r) is not a valid coding, and let $l = \sum_{i=0}^{\infty} l_i 10^{-i}$ and $r = \sum_{i=0}^{\infty} r_i 10^{-i}$, since (l,r) is not valid, this means that some $l_i$ and $r_i$ are not zeroes or twos, but since $f^n(l,r)$ is always defined, this also means that these never appear as $l_0$, so the computation to which they correspond is a computation that never reaches them. It then suffices to replace them by zeroes to obtain a valid coding, c then corresponds to this valid coding. See [12] for a more precise proof. □

Using two disjoint sets like $[0,1]$ and $[2,3]$ allows us to avoid some decoding problems that would necessarily happen if the tape was directly coded with its representation in binary<fnref n="3" />.

### 5.4.2 Undecidability of the Domino Problem

The piecewise affine map that we have constructed can easily be transformed into a set of tiles: it has rational coefficients, adding or subtracting a rational number can be done in a similar way to what was done for multiplication and the fact that we are now considering two reals and not only one does not constitute an obstacle, the transducers can as easily be constructed.

The outputs of any transducer coding for a transition will belong either to $\{0,1\}$ or to $\{2,3\}$, thus ensuring that numbers written on one row either belong to $[0,1]$ or to $[2,3]$ and that invalid codings can never appear as a result of applying piecewise affine map.

In order to obtain the undecidability of the domino problem, we will use the immortality problem:

**Theorem 8 (Hooper [25]).** There is no algorithm that, given a Turing machine *M*, decides if *M* halts on all configurations.

*This is still true if we restrict ourselves to Turing machines with a working alphabet of size 2.*

By not having any representation for any halting state in the tileset corresponding to the piecewise affine map, any tiling by this tileset will represent an infinite computation of our Turing machine. And thus the tileset will only be able to tile a half plane if the Turing machine is immortal, by compactness, if the tileset tiles the half plane, it tiles the whole plane.

<footnote n="3">³ The representations 0.100... and 0.011... code the same real but should not encode the same tape</footnote>
# 6 The Substitutive Method 2/2

The construction of an aperiodic tileset, and the undecidability result, that we describe in this section comes from the work of Durand, Romashchenko and Shen [14] and is inspired by the work of Gács in the 70's.

We saw in section 3 the concept of an intrinsically substitutive tileset, and we gave an example of such a tileset. However, we gave no indication how this tileset was obtained, or how to prove in general that such a tileset should exist. The core of the construction of Durand, Romashchenko and Shen is to use recursion theory to prove this.

We will first redefine more generally the notion of substitutive tiling, and of a simulation

**Definition 24 ([13, 43, 5, 14]).** Let $\sigma, \tau$ be two tilesets.

We say that $\sigma$ simulates $\tau$ with zoom factor $N$ if there exists a one-to-one function $\phi: \tau \to \sigma^{N \times N}$ s.t.

* For any finite pattern $w$, $\phi(w)$ is a valid tiling for $\sigma$ precisely when $w$ is a valid tiling for $\tau$.

* For any tiling of the plane $x$ by $\sigma$, there exist $w$ s.t. $\phi(w) = x$ upto shift. More precisely there exists a *unique* pair $(i', j') \in [0, N-1] \times [0, N-1]$ and a unique $w$ s.t. $x_{i+i', j+j'} = \phi(w)_{i,j}$.

The uniqueness property means that there is only one way to shift $x$ to obtain an image of $\phi$.

**Theorem 15 ([14]).** There exists a tileset that simulates itself.

We will explain in this section how this theorem is proven, and then how to apply it to obtain the undecidability of the domino problem.

The idea is that, given a tileset $\tau$, it is easy to build a tileset $\sigma$ that simulates $\tau$ with a given zoom factor $N$.

We now somehow want to have $\sigma = \tau$ in the previous construction.

How to do this is similar to the fixed point theorem of recursion theorem, which allows in particular to prove that functions that call themselves are (partial) computable.

We will first illustrate this fixed point theorem in a particular example.

Suppose we want to compute recursively the factorial function, in a language where recursion is not allowed. Here is what we would write in Python:

```python
def f(n):
    if n == 0:
        return 1
    else:
        return n*f(n-1)
```

But in our fictive language, recursion is not allowed, so we cannot write call $f$.

One solution is to have $f$ call another function $g$, and then somehow set $g$ to be equal to $f$. A first version would be:
# 6 The Substitutive Method 2/2

The construction of an aperiodic tileset, and the undecidability result, that we describe in this section comes from the work of Durand, Romashchenko and Shen [14] and is inspired by the work of Gács in the 70's.

We saw in section 3 the concept of an intrinsically substitutive tileset, and we gave an example of such a tileset. However, we gave no indication how this tileset was obtained, or how to prove in general that such a tileset should exist. The core of the construction of Durand, Romashchenko and Shen is to use recursion theory to prove this.

We will first redefine more generally the notion of substitutive tiling, and of a simulation

**Definition 24 ([13, 43, 5, 14]).** Let $\sigma, \tau$ be two tilesets.

We say that $\sigma$ simulates $\tau$ with zoom factor $N$ if there exists a one-to-one function $\phi: \tau \to \sigma^{N \times N}$ s.t.

* For any finite pattern $w$, $\phi(w)$ is a valid tiling for $\sigma$ precisely when $w$ is a valid tiling for $\tau$.

* For any tiling of the plane $x$ by $\sigma$, there exist $w$ s.t. $\phi(w) = x$ upto shift. More precisely there exists a *unique* pair $(i', j') \in [0, N-1] \times [0, N-1]$ and a unique $w$ s.t. $x_{i+i', j+j'} = \phi(w)_{i,j}$.

The uniqueness property means that there is only one way to shift $x$ to obtain an image of $\phi$.

**Theorem 15 ([14]).** There exists a tileset that simulates itself.

We will explain in this section how this theorem is proven, and then how to apply it to obtain the undecidability of the domino problem.

The idea is that, given a tileset $\tau$, it is easy to build a tileset $\sigma$ that simulates $\tau$ with a given zoom factor $N$.

We now somehow want to have $\sigma = \tau$ in the previous construction.

How to do this is similar to the fixed point theorem of recursion theorem, which allows in particular to prove that functions that call themselves are (partial) computable.

We will first illustrate this fixed point theorem in a particular example.

Suppose we want to compute recursively the factorial function, in a language where recursion is not allowed. Here is what we would write in Python:

```python
def f(n):
    if n == 0:
        return 1
    else:
        return n*f(n-1)
```

But in our fictive language, recursion is not allowed, so we cannot write call $f$.

One solution is to have $f$ call another function $g$, and then somehow set $g$ to be equal to $f$. A first version would be:
```python
def f(n):
    if n == 0:
        return 1
    else:
        return n*g(n-1)

g = f
```

In this example, `g` is a global variable that was somehow defined before the definition of `f` and then changed value afterwards. This is bad programming practice, so we prefer to give it as an argument to `f`:

```python
def f(g,n):
    if n == 0:
        return 1
    else:
        return n*g(g,n-1)
```

we can then call `f` with input `(f,n)` to obtain the result. This version would however make type theorists jump out of their skin<fnref n="4" />, as it not easy to find what type is `f`.

We will then proceed differently. Suppose that our programming language has a way to convert the code of a program (which is just a string of characters) into a function. Let call this procedure `eval`. Then we can write:

```python
def f(x,n):
    if n == 0:
        return 1
    else:
        return n*eval(x)(x,n-1)
```

Now `f` is just a function that takes an integer and a string and outputs an integer. Now if we feed `f` with `n` and its own code, then we obtain the factorial function.<fnref n="5" />

The tileset we will construct mimics exactly this idea.

## 6.1 The fixed point theorem of computability theory

The generalization of what precedes is called Kleene's fixed point theorem and is one of the fundamental theorems of computability theory. Usually in computability theory functions, strings, integers are all represented by finite binary sequences that may be seen as integers, and thus all theorems are on computable functions on integers.

```python
x = "lambda n,x: 1 if n == 0 else n*eval(x)(n-1,x)"
f = lambda n: eval(x)(n,x)
```

<footnote n="4">⁴ It however works in python.</footnote>

<footnote n="5">⁵ Up to a few syntactic changes, the reasoning we took actually works in python, as shown by the following two lines:</footnote>
```python
def f(n):
    if n == 0:
        return 1
    else:
        return n*g(n-1)

g = f
```

In this example, `g` is a global variable that was somehow defined before the definition of `f` and then changed value afterwards. This is bad programming practice, so we prefer to give it as an argument to `f`:

```python
def f(g,n):
    if n == 0:
        return 1
    else:
        return n*g(g,n-1)
```

we can then call `f` with input `(f,n)` to obtain the result. This version would however make type theorists jump out of their skin<fnref n="4" />, as it not easy to find what type is `f`.

We will then proceed differently. Suppose that our programming language has a way to convert the code of a program (which is just a string of characters) into a function. Let call this procedure `eval`. Then we can write:

```python
def f(x,n):
    if n == 0:
        return 1
    else:
        return n*eval(x)(x,n-1)
```

Now `f` is just a function that takes an integer and a string and outputs an integer. Now if we feed `f` with `n` and its own code, then we obtain the factorial function.<fnref n="5" />

The tileset we will construct mimics exactly this idea.

## 6.1 The fixed point theorem of computability theory

The generalization of what precedes is called Kleene's fixed point theorem and is one of the fundamental theorems of computability theory. Usually in computability theory functions, strings, integers are all represented by finite binary sequences that may be seen as integers, and thus all theorems are on computable functions on integers.

```python
x = "lambda n,x: 1 if n == 0 else n*eval(x)(n-1,x)"
f = lambda n: eval(x)(n,x)
```

<footnote n="4">⁴ It however works in python.</footnote>

<footnote n="5">⁵ Up to a few syntactic changes, the reasoning we took actually works in python, as shown by the following two lines:</footnote>
**Theorem 16 (Kleene's fixed point).** If $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is a computable function, then there exists a computable function $g$ such that $f(g, n) = g(n)$.

*Proof.* Let $U$ be a universal program: given $p, n_1, \dots, n_k$ as arguments, $U$ computes $p$ with arguments $n_1, \dots, n_k$, that is to say:

$$U(p, n_1, \dots, n_k) = p(n_1, \dots, n_k).$$

This is essentially what the `eval` function from before does.

Consider $s(p) = U(p, p)$, the function that applies $p$ to its own code and denote $h(i, n) = f(s(i), n)$. Now set $g(n) = h(h, n)$ we have:

$$g(n) = h(h, n) = f(s(h), n) = f(h(h), n) = f(g, n)$$

□

One way to interpret this theorem is that there exists a function $g$ that “mimics” an infinite application of $f$ on itself: $g(n) = f(g, n) = f(f(g, n)) = f(f(f(...), n), n)$.

The universal Turing machine of the proof induces some overhead to the time $t(n)$ that the program $p$ would take by itself on an input of size $n$. Using several tapes, one can design a universal TM taking an overhead at most polynomial in $t(n)$, see for instance [22, 4].

The aim is to construct a tileset using Kleene's fixed point theorem to obtain a self simulating tileset.

## 6.2 Simulating a tileset with a Turing machine

A tile can be summed up by the colors $c = \langle n, w, s, e \rangle$ of its four borders:

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

And thus a tileset can be seen as a computable function $g(c)$ that accepts when $c$ represents a tile belonging to the tileset and rejects otherwise:

**Definition 25.** A computable function $g$ codes a tileset $\tau$ with $k$ colors if:

* $g$ interprets its argument as a quadruplet of colors: $g$ rejects if its input is not of size $4 \log k$.

* $g$ accepts only when $c$ represents a tile of $\tau$.

Now if $g$ is a function defining a tileset $\tau$, we are going to design a computable function $f(N, k, g, c)$ that verifies if the tile $c$ is in a tileset $\tau'$ simulating $\tau$ with zoom
**Theorem 16 (Kleene's fixed point).** If $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is a computable function, then there exists a computable function $g$ such that $f(g, n) = g(n)$.

*Proof.* Let $U$ be a universal program: given $p, n_1, \dots, n_k$ as arguments, $U$ computes $p$ with arguments $n_1, \dots, n_k$, that is to say:

$$U(p, n_1, \dots, n_k) = p(n_1, \dots, n_k).$$

This is essentially what the eval function from before does.

Consider $s(p) = U(p, p)$, the function that applies $p$ to its own code and denote $h(i, n) = f(s(i), n)$. Now set $g(n) = h(h, n)$ we have:

$$g(n) = h(h, n) = f(s(h), n) = f(h(h), n) = f(g, n)$$

□

One way to interpret this theorem is that there exists a function $g$ that “mimics” an infinite application of $f$ on itself: $g(n) = f(g, n) = f(f(g, n)) = f(f(f(...), n), n)$.

The universal Turing machine of the proof induces some overhead to the time $t(n)$ that the program $p$ would take by itself on an input of size $n$. Using several tapes, one can design a universal TM taking an overhead at most polynomial in $t(n)$, see for instance [22, 4].

The aim is to construct a tileset using Kleene's fixed point theorem to obtain a self simulating tileset.

## 6.2 Simulating a tileset with a Turing machine

A tile can be summed up by the colors $c = \langle n, w, s, e \rangle$ of its four borders:

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

And thus a tileset can be seen as a computable function $g(c)$ that accepts when $c$ represents a tile belonging to the tileset and rejects otherwise:

**Definition 25.** A computable function $g$ codes a tileset $\tau$ with $k$ colors if:

* $g$ interprets its argument as a quadruplet of colors: $g$ rejects if its input is not of size $4 \log k$.

* $g$ accepts only when $c$ represents a tile of $\tau$.

Now if $g$ is a function defining a tileset $\tau$, we are going to design a computable function $f(N, k, g, c)$ that verifies if the tile $c$ is in a tileset $\tau'$ simulating $\tau$ with zoom
factor $N$. That is to say, $f$ builds the tileset $\tau'$ from $g$ and then checks that its input $c$ belongs to it.

The tileset constructed by $f$ will divide the plane into *macrotiles*, virtual tiles formed by an $N \times N$ square of smaller tiles. Each macrotile then runs the function $g$ on input $C = \langle n, w, s, e \rangle$, the 4 colors coded in the border of the macrotile. The program $g$ is only allowed to accept, so that only valid macrotiles may be formed. Let us now see the details.

The tileset constructed by $f$ first starts by separating the grid into $N \times N$ squares:

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

This can easily be done by having tiles that count modulo $N$, the borders of the macrotile appearing on the transition between 0 and $N-1$:

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

The center of each macrotile then contains a zone on each side that represents the color of the side and wires that route them towards a computation zone which applies $g$ to $c$:

<figure><img src="image_39.png" /></figure>
factor $N$. That is to say, $f$ builds the tileset $\tau'$ from $g$ and then checks that its input $c$ belongs to it.

The tileset constructed by $f$ will divide the plane into *macrotiles*, virtual tiles formed by an $N \times N$ square of smaller tiles. Each macrotile then runs the function $g$ on input $C = \langle n, w, s, e \rangle$, the 4 colors coded in the border of the macrotile. The program $g$ is only allowed to accept, so that only valid macrotiles may be formed. Let us now see the details.

The tileset constructed by $f$ first starts by separating the grid into $N \times N$ squares:

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

This can easily be done by having tiles that count modulo $N$, the borders of the macrotile appearing on the transition between 0 and $N-1$:

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

The center of each macrotile then contains a zone on each side that represents the color of the side and wires that route them towards a computation zone which applies $g$ to $c$:

<figure><img src="image_39.png" /></figure>
We make the computation zone of size $N/2 \times N/2$ inside each macrotile.

If $N$ is big enough, this computation zone has enough time and space to run $g$:

**Theorem 17.** If $g$ codes $\tau$ with $k$ colors, there exists $N$ such that for any $N' > N$, $f(N', k, g, c)$ codes a tileset simulating $\tau$ with zoom factor $N'$.

*Proof.* Let $t$ be an upper bound of the time taken by $g$ on any accepting input of size $4 \log k$, when $g$ is executed on a universal machine. We now take $N = 2t$.

Let $N' > N$. By our choice of $N$, the computation zone inside each macrotile defined by $f(N', k, g, c)$ is big enough for the computation of $g$ to fit.

In this case, each macrotile codes colors $n, s, e, w$ on its border s.t. $g(\langle n, s, e, w \rangle)$ accepts, i.e. the macrotile codes a tile of $\tau$.

Therefore the whole tileset $\tau'$ is simulating $\tau$ with zoom factor $N'$.

## 6.3 A fixedpoint based tileset

Wishful thinking would lead us to apply the fixedpoint theorem to $f$ however this is not possible as is for several reasons:

* First, $g$ does not take the same arguments as $f$. As defined before, $g$ supposes that $N$ and $k$ are externally defined.

* $N$ and $k$ would depend on the size of $f$ to be defined.

The solution to this is straightforward and is to make $k$ and $N$ become arguments of $g$. The only modification needed in the previous construction for is to hardcode $N$ and $k$ as inputs of $g$ inside the macrotiles that are constructed by $f$. As the number of tiles generated by $f$ is $O(N^2)$, this means that taking $k = N^2$ colors is sufficient to code them all. Furthermore, there is always room in the macrotiles to carry $N^2$ colors, as this only takes $2 \log N$ bits.

So we now have a function $f(g, N, c)$ which takes a function $g(N, c)$ as an argument.

It now suffices to apply Kleene's fixed point theorem to $f$. We obtain a new program $\rho$ such that $f(\rho, N, c) = \rho(N, c)$.

**Theorem 18.** There exists $N$ such that for any $n > N$, $\rho(N, c)$ codes a tileset $\tau$ simulating itself with zoom factor $N$.

*Proof.* As $f$ is polynomial in $\log N$, $|g|$ and $|c|$, this means that $\rho$'s runtime is polynomial in $\log N$. So taking $N \gg \text{poly}(\log N)$ suffices to have enough runtime inside the macrotiles.

$\rho$ defines a tileset $\tau$ which produces macrotiles of size $N \times N$ that themselves check if they belong to $\tau$ by running $\rho$ in their computation zone. Thus $\rho$ simulates itself with zoom factor $N$.

We can now show that $\tau$ indeed tiles the plane by inductively defining macrotiles of level $k$, this will also give us a picture of what tiling by $\tau$ look like:
We make the computation zone of size $N/2 \times N/2$ inside each macrotile.

If $N$ is big enough, this computation zone has enough time and space to run $g$:

**Theorem 17.** If $g$ codes $\tau$ with $k$ colors, there exists $N$ such that for any $N' > N$, $f(N', k, g, c)$ codes a tileset simulating $\tau$ with zoom factor $N'$.

*Proof.* Let $t$ be an upper bound of the time taken by $g$ on any accepting input of size $4 \log k$, when $g$ is executed on a universal machine. We now take $N = 2t$.

Let $N' > N$. By our choice of $N$, the computation zone inside each macrotile defined by $f(N', k, g, c)$ is big enough for the computation of $g$ to fit.

In this case, each macrotile codes colors $n, s, e, w$ on its border s.t. $g(\langle n, s, e, w \rangle)$ accepts, i.e. the macrotile codes a tile of $\tau$.

Therefore the whole tileset $\tau'$ is simulating $\tau$ with zoom factor $N'$.

☐

## 6.3 A fixedpoint based tileset

Wishful thinking would lead us to apply the fixedpoint theorem to $f$ however this is not possible as is for several reasons:

* First, $g$ does not take the same arguments as $f$. As defined before, $g$ supposes that $N$ and $k$ are externally defined.

* $N$ and $k$ would depend on the size of $f$ to be defined.

The solution to this is straightforward and is to make $k$ and $N$ become arguments of $g$. The only modification needed in the previous construction for is to hardcode $N$ and $k$ as inputs of $g$ inside the macrotiles that are constructed by $f$. As the number of tiles generated by $f$ is $O(N^2)$, this means that taking $k = N^2$ colors is sufficient to code them all. Furthermore, there is always room in the macrotiles to carry $N^2$ colors, as this only takes $2 \log N$ bits.

So we now have a function $f(g, N, c)$ which takes a function $g(N, c)$ as an argument.

It now suffices to apply Kleene's fixed point theorem to $f$. We obtain a new program $\rho$ such that $f(\rho, N, c) = \rho(N, c)$.

**Theorem 18.** There exists $N$ such that for any $n > N$, $\rho(N, c)$ codes a tileset $\tau$ simulating itself with zoom factor $N$.

*Proof.* As $f$ is polynomial in $\log N$, $|g|$ and $|c|$, this means that $\rho$'s runtime is polynomial in $\log N$. So taking $N \gg \text{poly}(\log N)$ suffices to have enough runtime inside the macrotiles.

$\rho$ defines a tileset $\tau$ which produces macrotiles of size $N \times N$ that themselves check if they belong to $\tau$ by running $\rho$ in their computation zone. Thus $\rho$ simulates itself with zoom factor $N$.

We can now show that $\tau$ indeed tiles the plane by inductively defining macrotiles of level $k$, this will also give us a picture of what tiling by $\tau$ look like:
• The macrotiles of level 0 are the macrotiles formed by $N \times N$ squares of tiles of $\tau$.

• The macrotiles formed $N \times N$ squares of macrotiles of level $k$ are macrotiles of level $k+1$, see figure 30.

$\tau$ does indeed tile the plane since for any $k$ one can tile an $N^{2^k} \times N^{2^k}$ square just by taking a macrotile of level $k$, which implies that there exists a tiling of the plane, by compactness.

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

<figure><img src="image_41.png" /><figcaption>**Fig. 30** An $N \times N$ square of macrotiles of level $k$ forms a macrotile of level $k+1$.</figcaption></figure>

One may also show that $\tau$ is aperiodic:

**Lemma 6.** A tileset that simulates itself is aperiodic.

*Proof*. Let $T$ be a tileset that simulates itself with zoom factor $N$ and suppose it is periodic. Since any tiling is uniquely subdivided in $N \times N$ zones, the period must be divisible by $N$. However, since the tileset simulates itself, any tiling can also be uniquely subdivided in $N^2 \times N^2$ zones, so $N^2$ must also divide the period. By the same argument this must be true for any $N^{2^k}$, which is impossible. $\square$

## 6.4 Undecidability

The tileset $\tau$ we constructed in the previous subsection, while aperiodic, does not prove the undecidability of the Domino Problem. In order to do this, given a Turing machine $M$ we will construct $\tau_M$ in a similar fashion, but we will embed computations of $M$ into the macrotiles which will prevent the tileability in case $M$ halts.

We cannot use exactly the construction from before, as a zoom factor of $N$ for each level of macrotiles will mean that the macrotiles of different levels have the
• The macrotiles of level 0 are the macrotiles formed by $N \times N$ squares of tiles of $\tau$.

• The macrotiles formed $N \times N$ squares of macrotiles of level $k$ are macrotiles of level $k+1$, see figure 30.

$\tau$ does indeed tile the plane since for any $k$ one can tile an $N^{2^k} \times N^{2^k}$ square just by taking a macrotile of level $k$, which implies that there exists a tiling of the plane, by compactness.

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

<figure><img src="image_41.png" /><figcaption>**Fig. 30** An $N \times N$ square of macrotiles of level $k$ forms a macrotile of level $k+1$.</figcaption></figure>

One may also show that $\tau$ is aperiodic:

**Lemma 6.** A tileset that simulates itself is aperiodic.

*Proof*. Let $T$ be a tileset that simulates itself with zoom factor $N$ and suppose it is periodic. Since any tiling is uniquely subdivided in $N \times N$ zones, the period must be divisible by $N$. However, since the tileset simulates itself, any tiling can also be uniquely subdivided in $N^2 \times N^2$ zones, so $N^2$ must also divide the period. By the same argument this must be true for any $N^{2^k}$, which is impossible. $\square$

## 6.4 Undecidability

The tileset $\tau$ we constructed in the previous subsection, while aperiodic, does not prove the undecidability of the Domino Problem. In order to do this, given a Turing machine $M$ we will construct $\tau_M$ in a similar fashion, but we will embed computations of $M$ into the macrotiles which will prevent the tileability in case $M$ halts.

We cannot use exactly the construction from before, as a zoom factor of $N$ for each level of macrotiles will mean that the macrotiles of different levels have the
same computation space and thus all computations would be bounded by the same $N$. The goal being that macrotiles of level $k$ simultaneously generate macrotiles of level $k+1$ and simulate a computation of $M$ for more and more time steps.

Thus, if $M$ halts, some macrotile of level $k$ would uncover it and prevent the formation of macrotiles of level $k+1$ and the tileset to tile the plane.

To achieve this, instead of making $f$ hardcode $N$ as an input to $g$, $f$ hardcodes $2N$. Thus the computation zone is doubled with each simulation. So now a macrotile of level $k+1$ divides the plane in $2^k N \times 2^k N$ macrotiles of level $k$. And the computation zone inside the macrotiles of level $k+1$ now is $2^k N/2$.

The program run by a macrotile can be summed up by the following pseudocode:

def $f(g, N, c)$:
    construct $T_k$: a tileset dividing the plane in $N \times N$ macrotiles which contain a computation of $g(2N, c')$.
    if $c \notin T_k$:
        reject
    else:
        launch $N/2$ timesteps of the simulation of $M$ if the simulation halts reject

Instead of a constant zoom factor between the different levels, each level $k$ now has zoom factor $N_k = 2^k N$ which gives more and more computational room. So each level of macrotiles now ensures more simulation steps of $M$ and thus if $M$ halts, it will happen at some finite level which will prevent the tileability.

## 6.5 Bibliographic notes

The fixed point tileset construction originally appeared in [15]. Its versatility allowed Durand, Romashchenko and Shen to prove new and original results on tilings as well as reprove ancient results [14]. For instance, among the results that can be proven with almost no modifications of the construction is a result by Hanf and Myers [21, 41] stating that there exists tilesets producing only non computable tilings of the plane. Other results that can be proved using variations of this technique include:

* Substitutive tilesets defined by a rectangular substitution are sofic (Mozes [40]).

* $d$-dimensional effective subshifts are subactions of $d+1$ dimensional sofic subshifts, a result originally discovered only with $d+2$-dimensional sofic shifts by Hochman [23].

* A characterization of the entropy of tilings by right recursively enumerable numbers (Hochman and Meyerovitch [24]).

* That there exists tilesets robust to errors.

* A characterization of the set of non-expansive directions of tilings [54].

* The subshift whose configurations are constituted only of squares whose sizes are chosen from a co-recursively enumerable set [53].
same computation space and thus all computations would be bounded by the same $N$. The goal being that macrotiles of level $k$ simultaneously generate macrotiles of level $k+1$ and simulate a computation of $M$ for more and more time steps.

Thus, if $M$ halts, some macrotile of level $k$ would uncover it and prevent the formation of macrotiles of level $k+1$ and the tileset to tile the plane.

To achieve this, instead of making $f$ hardcode $N$ as an input to $g$, $f$ hardcodes $2N$. Thus the computation zone is doubled with each simulation. So now a macrotile of level $k+1$ divides the plane in $2^k N \times 2^k N$ macrotiles of level $k$. And the computation zone inside the macrotiles of level $k+1$ now is $2^k N/2$.

The program run by a macrotile can be summed up by the following pseudocode:

def $f(g, N, c)$:
    construct $T_k$: a tileset dividing the plane in $N \times N$ macrotiles which contain a computation of $g(2N, c')$.
    if $c \notin T_k$:
        reject
    else:
        launch $N/2$ timesteps of the simulation of $M$ if the simulation halts reject

Instead of a constant zoom factor between the different levels, each level $k$ now has zoom factor $N_k = 2^k N$ which gives more and more computational room. So each level of macrotiles now ensures more simulation steps of $M$ and thus if $M$ halts, it will happen at some finite level which will prevent the tileability.

## 6.5 Bibliographic notes

The fixed point tileset construction originally appeared in [15]. Its versatility allowed Durand, Romashchenko and Shen to prove new and original results on tilings as well as reprove ancient results [14]. For instance, among the results that can be proven with almost no modifications of the construction is a result by Hanf and Myers [21, 41] stating that there exists tilesets producing only non computable tilings of the plane. Other results that can be proved using variations of this technique include:

* Substitutive tilesets defined by a rectangular substitution are sofic (Mozes [40]).

* $d$-dimensional effective subshifts are subactions of $d+1$ dimensional sofic subshifts, a result originally discovered only with $d+2$-dimensional sofic shifts by Hochman [23].

* A characterization of the entropy of tilings by right recursively enumerable numbers (Hochman and Meyerovitch [24]).

* That there exists tilesets robust to errors.

* A characterization of the set of non-expansive directions of tilings [54].

* The subshift whose configurations are constituted only of squares whose sizes are chosen from a co-recursively enumerable set [53].
References

1. Aanderaa, S.O., Lewis, H.R.: Linear Sampling and the $\forall\exists\forall$ Case of the Decision Problem. Journal of Symbolic Logic **39**(3, 519–548 (1974). See also [36]

2. Allauzen, C., Durand, B.: Tiling Problems. In: The Classical Decision Problem, Perspectives in Mathematical Logic, chap. A, pp. 407–420. Springer (2001)

3. Ammann, R., Grunbaum, B., Shephard, G.: Aperiodic tiles. Discrete and Computational Geometry **8**(1), 1–25 (1992)

4. Arora, S., Barak, B.: Computational Complexity: A Modern Approach, 1st edn. Cambridge University Press, New York, NY, USA (2009)

5. Ballier, A.: Propriétés structurelles, combinatoires et logiques des pavages. Ph.D. thesis, Aix-Marseille Université (2009)

6. Beatty, S.: Problem 3173. American Mathematical Monthly **33**, 159 (1926)

7. Berger, R.: The Undecidability of the Domino Problem. Ph.D. thesis, Harvard University (1964)

8. Berger, R.: The Undecidability of the Domino Problem. No. 66 in Memoirs of the American Mathematical Society. The American Mathematical Society (1966)

9. Büchi, J.R.: Turing-Machines and the Entscheidungsproblem. Math. Annalen **148**(3), 201–213 (1962). DOI 10.1007/BF01470748

10. Chazottes, J.R., Gambaudo, J.M., Gautero, F.: Tilings of the plane and Thurston semi-norm. Geometriae Dedicata **173**(1), 129–142 (2014). DOI 10.1007/s10711-013-9932-4

11. Church, A.: An unsolvable problem of elementary number theory. American Journal of Mathematics **58**(2), 345–363 (1936)

12. Collins, P., van Schuppen, J.H.: Observability of Hybrid Systems and Turing Machines. In: 43rd IEEE conference on Decision and Control, pp. 7–12 (2004). DOI 0.1109/CDC.2004.1428598

13. Durand, B., Levin, L.A., Shen, A.: Local rules and global order, or aperiodic tilings. Mathematical Intelligencer **27**(1), 64–68 (2004)

14. Durand, B., Romashchenko, A., Shen, A.: Fixed-point tile sets and their applications. Journal of Computer and System Sciences **78**(3), 731–764 (2012). DOI 10.1016/j.jcss.2011.11.001

15. Durand, B., Shen, A., Romashchenko, A.: Fixed Point and Aperiodic Tilings. Tech. Rep. TR08-030, ECCC (2008)

16. Eigen, S., Navarro, J., Prasad, V.S.: An aperiodic tiling using a dynamical system and Beatty sequences. In: Recent Progress in Dynamics, MSRI Publications, vol. 54. Cambridge University Press (2007)

17. Fernique, T., Ollinger, N.: Combinatorial Substitutions and Sofic Tilings. In: JournÃ©es Automates Cellulaires (JAC), TUCS, pp. 100–110 (2010)

18. Fogg, N.P.: Substitutions in Dynamics, Arithmetics and Combinatorics, chap. Sturmian Sequences. Lecture Notes in Mathematics. Springer (2002)

19. Gähler, F., Julien, A., Savinien, J.: Combinatorics and Topology of the Robinson tiling. Comptes Rendus de l'Académie des Sciences de Paris, Série I - Mathématiques pp. 627–631 (2012). DOI 10.1016/j.crma.2012.06.007

20. Goodman-Strauss, C.: Matching Rules and Substitution Tilings. Annals of Mathematics **147**(1), 181–223 (1998)

21. Hanf, W.: Non Recursive Tilings of the Plane I. Journal of Symbolic Logic **39**(2), 283–285 (1974)

22. Hennie, F.C., Stearns, R.E.: Two-tape simulation of multitape turing machines. J. ACM **13**(4), 533–546 (1966). DOI 10.1145/321356.321362. URL http://doi.acm.org/10.1145/321356.321362

23. Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae **176**(1), 2009 (2009)

24. Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics **171**(3), 2011–2038 (2010). DOI 10.4007/annals.2010.171.2011
References

1. Aanderaa, S.O., Lewis, H.R.: Linear Sampling and the $\forall\exists\forall$ Case of the Decision Problem. Journal of Symbolic Logic 39(3), 519–548 (1974). See also [36]

2. Allauzen, C., Durand, B.: Tiling Problems. In: The Classical Decision Problem, Perspectives in Mathematical Logic, chap. A, pp. 407–420. Springer (2001)

3. Ammann, R., Grunbaum, B., Shephard, G.: Aperiodic tiles. Discrete and Computational Geometry 8(1), 1–25 (1992)

4. Arora, S., Barak, B.: Computational Complexity: A Modern Approach, 1st edn. Cambridge University Press, New York, NY, USA (2009)

5. Ballier, A.: Propriétés structurelles, combinatoires et logiques des pavages. Ph.D. thesis, Aix-Marseille Université (2009)

6. Beatty, S.: Problem 3173. American Mathematical Monthly 33, 159 (1926)

7. Berger, R.: The Undecidability of the Domino Problem. Ph.D. thesis, Harvard University (1964)

8. Berger, R.: The Undecidability of the Domino Problem. No. 66 in Memoirs of the American Mathematical Society. The American Mathematical Society (1966)

9. Büchi, J.R.: Turing-Machines and the Entscheidungsproblem. Math. Annalen 148(3), 201–213 (1962). DOI 10.1007/BF01470748

10. Chazottes, J.R., Gambaudo, J.M., Gautero, F.: Tilings of the plane and Thurston semi-norm. Geometriae Dedicata 173(1), 129–142 (2014). DOI 10.1007/s10711-013-9932-4

11. Church, A.: An unsolvable problem of elementary number theory. American Journal of Mathematics 58(2), 345–363 (1936)

12. Collins, P., van Schuppen, J.H.: Observability of Hybrid Systems and Turing Machines. In: 43rd IEEE conference on Decision and Control, pp. 7–12 (2004). DOI 0.1109/CDC.2004.1428598

13. Durand, B., Levin, L.A., Shen, A.: Local rules and global order, or aperiodic tilings. Mathematical Intelligencer 27(1), 64–68 (2004)

14. Durand, B., Romashchenko, A., Shen, A.: Fixed-point tile sets and their applications. Journal of Computer and System Sciences 78(3), 731–764 (2012). DOI 10.1016/j.jcss.2011.11.001

15. Durand, B., Shen, A., Romashchenko, A.: Fixed Point and Aperiodic Tilings. Tech. Rep. TR08-030, ECCC (2008)

16. Eigen, S., Navarro, J., Prasad, V.S.: An aperiodic tiling using a dynamical system and Beatty sequences. In: Recent Progress in Dynamics, MSRI Publications, vol. 54. Cambridge University Press (2007)

17. Fernique, T., Ollinger, N.: Combinatorial Substitutions and Sofic Tilings. In: JournÃ©es Automates Cellulaires (JAC), TUCS, pp. 100–110 (2010)

18. Fogg, N.P.: Substitutions in Dynamics, Arithmetics and Combinatorics, chap. Sturmian Sequences. Lecture Notes in Mathematics. Springer (2002)

19. Gähler, F., Julien, A., Savinien, J.: Combinatorics and Topology of the Robinson tiling. Comptes Rendus de l'Académie des Sciences de Paris, Série I - Mathématiques pp. 627–631 (2012). DOI 10.1016/j.crma.2012.06.007

20. Goodman-Strauss, C.: Matching Rules and Substitution Tilings. Annals of Mathematics 147(1), 181–223 (1998)

21. Hanf, W.: Non Recursive Tilings of the Plane I. Journal of Symbolic Logic 39(2), 283–285 (1974)

22. Hennie, F.C., Stearns, R.E.: Two-tape simulation of multitape turing machines. J. ACM 13(4), 533–546 (1966). DOI 10.1145/321356.321362. URL http://doi.acm.org/10.1145/321356.321362

23. Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae 176(1), 2009 (2009)

24. Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics 171(3), 2011–2038 (2010). DOI 10.4007/annals.2010.171.2011
25. Hooper, P.K.: The Undecidability of the Turing Machine Immortality Problem. Journal of Symbolic Logic **31**(2), 219–234 (1966)

26. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)

27. Jeandel, E., Rao, M.: An aperiodic set of 11 Wang tiles. Preprint

28. Johnson, A., Madden, K.: Putting the Pieces Together: Understanding Robinson's Nonperiodic Tilings. The College Mathematics Journal **28**(3), 172–181 (1997)

29. Kahr, A., Moore, E.F., Wang, H.: Entscheidungsproblem reduced to the $\forall\exists\forall$ case. Proceedings of the National Academy of Sciences of the United States of America **48**(3), 365–377 (1962)

30. Kari, J.: The Nilpotency Problem of One-Dimensional Cellular Automata. SIAM Journal on Computing **21**(3), 571–586 (1992)

31. Kari, J.: A small aperiodic set of Wang tiles. Discrete Mathematics **160**, 259–264 (1996)

32. Kari, J.: The Tiling Problem Revisited. In: Machines, Computations, and Universality (MCU), no. 4664 in Lecture Notes in Computer Science, pp. 72–79 (2007)

33. Kari, J., Ollinger, N.: Periodicity and Immortality in Reversible Computing. In: MFCS 2008, LNCS 5162, pp. 419–430 (2008)

34. Kleene, S.: Two Papers on the Predicate Calculus., chap. Finite Axiomatizability of Theories in the Predicate Calculus Using Additional Predicate Symbols. No. 10 in Memoirs of the American Mathematical Society. American Mathematical Society (1952)

35. Levin, L.A.: Forbidden Information. Journal of the ACM **60**(2), 9:1–9 (2013). DOI 10.1145/2450142.2450145

36. Lewis, H.R.: Unsolvable Classes of Quantificational Formulas. Addison-Wesley (1979)

37. Lewis, H.R., Papadimitriou, C.H.: Elements of the Theory of Computation. Prentice-Hall (1998)

38. Lind, D.A., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York, NY, USA (1995)

39. Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall (1967)

40. Mozes, S.: Tilings, substitutions systems and dynamical systems generated by them. J. d'Analyse Math. **53**, 139–186 (1989)

41. Myers, D.: Non Recursive Tilings of the Plane II. Journal of Symbolic Logic **39**(2), 286–294 (1974)

42. Nillsen, R., Tognetti, K., Winley, G.: Bernoulli (beta) and integer part sequences. Australian Mathematical Society (1999)

43. Ollinger, N.: Two-by-Two Substitution Systems and the Undecidability of the Domino Problem. In: CiE 2008, no. 5028 in Lecture Notes in Computer Science, pp. 476–485 (2008)

44. Papadimitriou, C.H.: Computational Complexity. Addison Wesley (1995)

45. Poizat, B.: Une théorie finiement axiomatisable et superstable. Groupe d'études de théories stables **3**, 1–9 (1980)

46. Robinson, R.M.: Seven polygons which permit only nonperiodic tilings of the plane. Notices of the American Mathematical Society **14**, 835 (1967)

47. Robinson, R.M.: Undecidability and Nonperiodicity for Tilings of the Plane. Inventiones Mathematicae **12**(3), 177–209 (1971). DOI 10.1007/BF01418780

48. Salon, O.: Quelles tuiles! (Pavages apériodiques du plan et automates bidimensionnels). Journal de Théorie des Nombres de Bordeaux **1**(1), 1–26 (1989)

49. Simpson, S.G.: Medvedev degrees of two-dimensional subshifts of finite type. Ergodic Theory and Dynamical Systems **34**, 679–688 (2014). DOI 10.1017/etds.2012.152

50. Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society **s2-42**(1), 230–265 (1937)

51. Wang, H.: Proving theorems by Pattern Recognition II. Bell Systems technical journal **40**, 1–41 (1961)

52. Wang, H.: Dominoes and the $\forall\exists\forall$ case of the decision problem. Mathematical Theory of Automata pp. 23–55 (1963)

53. Westrick, L.B.: Seas of squares with sizes from a $\Pi_1^0$ set. Israel Journal of Mathematics **222**(1), 431–462 (2017). DOI 10.1007/s11856-017-1596-6
25. Hooper, P.K.: The Undecidability of the Turing Machine Immortality Problem. Journal of Symbolic Logic **31**(2), 219–234 (1966)

26. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)

27. Jeandel, E., Rao, M.: An aperiodic set of 11 Wang tiles. Preprint

28. Johnson, A., Madden, K.: Putting the Pieces Together: Understanding Robinson's Nonperiodic Tilings. The College Mathematics Journal **28**(3), 172–181 (1997)

29. Kahr, A., Moore, E.F., Wang, H.: Entscheidungsproblem reduced to the $\forall\exists\forall$ case. Proceedings of the National Academy of Sciences of the United States of America **48**(3), 365–377 (1962)

30. Kari, J.: The Nilpotency Problem of One-Dimensional Cellular Automata. SIAM Journal on Computing **21**(3), 571–586 (1992)

31. Kari, J.: A small aperiodic set of Wang tiles. Discrete Mathematics **160**, 259–264 (1996)

32. Kari, J.: The Tiling Problem Revisited. In: Machines, Computations, and Universality (MCU), no. 4664 in Lecture Notes in Computer Science, pp. 72–79 (2007)

33. Kari, J., Ollinger, N.: Periodicity and Immortality in Reversible Computing. In: MFCS 2008, LNCS 5162, pp. 419–430 (2008)

34. Kleene, S.: Two Papers on the Predicate Calculus., chap. Finite Axiomatizability of Theories in the Predicate Calculus Using Additional Predicate Symbols. No. 10 in Memoirs of the American Mathematical Society. American Mathematical Society (1952)

35. Levin, L.A.: Forbidden Information. Journal of the ACM **60**(2), 9:1–9 (2013). DOI 10.1145/2450142.2450145

36. Lewis, H.R.: Unsolvable Classes of Quantificational Formulas. Addison-Wesley (1979)

37. Lewis, H.R., Papadimitriou, C.H.: Elements of the Theory of Computation. Prentice-Hall (1998)

38. Lind, D.A., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York, NY, USA (1995)

39. Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall (1967)

40. Mozes, S.: Tilings, substitutions systems and dynamical systems generated by them. J. d'Analyse Math. **53**, 139–186 (1989)

41. Myers, D.: Non Recursive Tilings of the Plane II. Journal of Symbolic Logic **39**(2), 286–294 (1974)

42. Nillsen, R., Tognetti, K., Winley, G.: Bernoulli (beta) and integer part sequences. Australian Mathematical Society (1999)

43. Ollinger, N.: Two-by-Two Substitution Systems and the Undecidability of the Domino Problem. In: CiE 2008, no. 5028 in Lecture Notes in Computer Science, pp. 476–485 (2008)

44. Papadimitriou, C.H.: Computational Complexity. Addison Wesley (1995)

45. Poizat, B.: Une théorie finiement axiomatisable et superstable. Groupe d'études de théories stables **3**, 1–9 (1980)

46. Robinson, R.M.: Seven polygons which permit only nonperiodic tilings of the plane. Notices of the American Mathematical Society **14**, 835 (1967)

47. Robinson, R.M.: Undecidability and Nonperiodicity for Tilings of the Plane. Inventiones Mathematicae **12**(3), 177–209 (1971). DOI 10.1007/BF01418780

48. Salon, O.: Quelles tuiles! (Pavages apériodiques du plan et automates bidimensionnels). Journal de Théorie des Nombres de Bordeaux **1**(1), 1–26 (1989)

49. Simpson, S.G.: Medvedev degrees of two-dimensional subshifts of finite type. Ergodic Theory and Dynamical Systems **34**, 679–688 (2014). DOI 10.1017/etds.2012.152

50. Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society **s2-42**(1), 230–265 (1937)

51. Wang, H.: Proving theorems by Pattern Recognition II. Bell Systems technical journal **40**, 1–41 (1961)

52. Wang, H.: Dominoes and the $\forall\exists\forall$ case of the decision problem. Mathematical Theory of Automata pp. 23–55 (1963)

53. Westrick, L.B.: Seas of squares with sizes from a $\Pi_1^0$ set. Israel Journal of Mathematics **222**(1), 431–462 (2017). DOI 10.1007/s11856-017-1596-6
54. Zinoviadis, C.: Hierarchy and expansiveness in 2d subshifts of finite type. In: Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, pp. 365–377 (2015)
54. Zinoviadis, C.: Hierarchy and expansiveness in 2d subshifts of finite type. In: Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, pp. 365–377 (2015)