¹

1 Introduction↩︎

For a group \(G\) and a finite set \(A\), a subshift is a closed, \(G\)-invariant subset \(X\) of the Cantor set \(A^G\). Every subshift is characterized by a collection of forbidden patterns: elements of \(A^F\) with finite \(F\subseteq G\) none of whose translates may appear in elements of \(X\). Three classes of subshifts gained prominence: those defined by a finite collection of forbidden patterns (subshifts of finite type, SFT); by a recursively enumerable collection (effective subshifts; we assume throughout that all groups are countable and have decidable word problem); and sofic shifts, see the next paragraph.

Furthermore, much can be learnt by considering maps between subshifts. By definition, a subshift \(X\subseteq A^G\) is sofic if it is a quotient of an SFT \(Y\subseteq B^G\) via a map \(B\to A\). If \(\phi\colon G\twoheadrightarrow Q\) is a quotient map then every subshift \(Y\subseteq B^Q\) may be pulled back to a subshift \(\phi^*(Y)\) on \(G\), whose elements are constant on all fibres of \(\phi\); and if \(\iota\colon H\hookrightarrow G\) is a subgroup inclusion then every subshift \(X\subseteq A^H\) may be induced to a subshift \(\iota_*(X)\) on \(G\) consisting of independent copies of \(X\) on each coset of \(H\). This is just the \(G\)-shift with same forbidden patterns as \(X\). We consider more generally \(G\)-systems, which are closed subsets of Cantor space endowed with a \(G\)-action.

Clearly the most desirable subshifts are the SFTs, then the sofic ones, and finally the effective ones. The situation we consider, restricted to subshifts, is in the following picture: \[\begin{tikzcd} 1\arrow{r} & H\arrow{r}{\iota} & G\arrow{r}{\phi} & Q\arrow{r} & 1\\ & \text{H-subshifts}\arrow{r}{\iota_*} & \text{G-subshifts} & \text{Q-subshifts}\arrow{l}[above]{\phi^*}\\ & \text{H-effectives}\arrow[hook]{u}\arrow[dashed]{r}[above]{?} & \text{G-sofics}\arrow[hook]{u} & \text{Q-effectives}\arrow[dashed]{l}[above]{?}\arrow[hook]{u} \end{tikzcd}\] and we study whether there are dotted arrows that complete the diagram (in which case they are uniquely determined as restrictions of \(\iota_*\) and \(\phi^*\)).

Several results in the literature may be interpreted as the construction of a rightmost dotted arrow; e.g. hochman:recursive?, aubrun-sablik:simulation?, durand-romashchenko-shen:1d2d? in the case \(1\to\Z\to\Z^d\to\Z^{d-1}\to1\) for \(d\ge1\), and barbieri-sablik:semidirect? for \(Q\)-effective systems in split extensions \(1\to\Z^2\to G\to Q\to1\); see also barbieri:simulation?. The reason behind such results is that the extra \(\Z\) component(s) may be used as “time”, in which to run Turing machine computations. For this reason, such results are often called “simulation theorems”.

If \(Q\) is non-amenable and the extension is a direct product, barbieri-sablik-salo:soficity? constructs a leftmost dotted arrow. If \(Q\) is amenable, though, we should not expect there to be such a map:

We recover that for \(1\to\Z\to\Z^2\to\Z\to1\) there are \(\Z\)-effective subshifts that do not induce to \(\Z^2\)-sofic subshifts; it is actually conjectured in guillon-jeandel:icc? that only sofic \(\Z\)-shifts may induce to a sofic \(\Z^2\)-sofic subshift. We shall soon see that sometimes a large subclass of \(H\)-effectives may be induced to \(G\).

In the extreme case that \(H=1\) (or similarly \(Q=1\)), our question asks whether all \(G\)-effective subshifts are sofic, in which case \(G\) is called self-simulable. This happens for instance if \(G=F_2\times F_2\), and in numerous other cases, see barbieri-sablik-salo:selfsimulable?.

Let us assume that \(G\) is amenable, so self-simulation is ruled out, and positive answers to our question entail an infinite “time” component \(H\). The critical case seems naturally to be a “small” infinite, finitely generated \(Q\), and an infinite, locally finite \(H\), namely an infinite subgroup all of whose finitely generated subgroups are finite. This is the situation that we address in this article, in a specific but possibly generic example, the lamplighter group \({\mathcal{L}}\). It is the extension \[\begin{tikzcd} 1\arrow{r} & {\displaystyle\bigoplus_{\Z+\frac{1}{2}}\Z/2}\arrow{r}{\iota} & {\mathcal{L}}\arrow{r}{\phi} & \Z\arrow{r} & 1. \end{tikzcd}\] (The group \(\Z\) acts on the \((\Z+\frac{1}{2})\)-indexed sum by shifting; see §2.1 for a few words on this strange-looking convention.) Our first main result concerns effective \(G\)-systems, analogous to \(G\)-shifts except that the alphabet is a Cantor set \(A^\omega\) rather than a finite set (see §2.2 for details):

(In particular, if \(X\) is a subshift, \(\phi^*(X)\) is a sofic \({\mathcal{L}}\)-subshift.) The kernel of \(\phi\) is the locally finite group \({\mathcal{S}}=(\Z/2)^{(\Z+\frac{1}{2})}\), which further decomposes as \({\mathcal{S}}={\mathcal{H}}\times{\mathcal{V}}\) for \({\mathcal{H}}= (\Z/2)^{(-\N-\frac{1}{2})}\) and \({\mathcal{V}}= (\Z/2)^{(\N+\frac{1}{2})}\). We denote by \(\eta\colon {\mathcal{S}}\to {\mathcal{H}}\) the natural projection. We can also simulate Turing machines within \({\mathcal{V}}\), proving the following result which is the main ingredient in the proof of Theorem 2, and in view of Observation 1 is probably the most that can be hoped for: denoting by \(\iota^-\colon{\mathcal{H}}\hookrightarrow{\mathcal{L}}\) the inclusion, there exists an effective \({\mathcal{H}}\)-subshift \(X\) such that \((\iota^-)_*(X)\) is not sofic, and an effective \({\mathcal{S}}\)-subshift such that \(\iota_*(X)\) is not sofic.

(In particular, if \(X\) is a subshift, \(\iota_*\eta^*(X)\) is a sofic \({\mathcal{L}}\)-subshift.) We deduce a number of corollaries for the lamplighter group. The domino problem for a group \(G\) asks for an algorithm that, upon input a finite collection of forbidden words, determines whether the corresponding SFT is non-empty.

(The best result known beforehand was that the seeded domino problem, asking for an algorithm deciding, given a finite collection of forbidden words and a cylindrical set, whether the corresponding SFT intersects it non-trivially bartholdi-salo:ll?).

The best result known beforehand was that there exists a non-empty subshift without periodic points cohen:lamplighters?, namely in which each \({\mathcal{L}}\)-orbit is infinite. We also provide an explicit construction, based on Kari’s transducer method kari:smallwang?, of a strongly aperiodic SFT with \(1488\) legal size-\(4\) patterns, and based on the same method a proof of the undecidability of the tiling problem.

1.1 Strategy↩︎

We develop the theory of substitutional subshifts on locally finite groups such as \({\mathcal{S}}\). It is somewhat analogous to substitutional subshifts on \(\Z\) or \(\Z^2\), though we do not have a general theory containing both. Keeping in mind Mozes’s result mozes:tilings? that every substitutional \(\Z^2\)-subshift is sofic, we prove related statements about \({\mathcal{S}}\)-subshifts. We then use substitutional subshifts to define a “scaffolding” on which to build simulations. As a side effect, we prove the following variant of Theorem 3:

The starting point in the proof of Theorem 3 is that when \(X\subseteq A^{\mathcal{H}}\) is a substitutive subshift, \((\iota^-)_*(X)\) is sofic. This allows simulating tiling systems independently on all \({\mathcal{S}}\)-cosets.

The next step in the proof is an adaptation of the construction by Durand-Romashchenko-Shen of self-similar tilesets durand-romashchenko-shen:fpa? from the theory of plane tilings to the locally finite case. Let us briefly recall the idea. Given a tileset \(\sigma\) on a group \(G\), we construct another tileset \(\tau(\sigma)\), whose tiles are bigger than the tiles of \(\sigma\), and which “implements” \(\sigma\), in the sense that \(\tau(\sigma)\) encodes a program checking whether a tuple of colours represents a tile of \(\sigma\). If the construction \(\sigma\mapsto\tau(\sigma)\) is algorithmic, then it admits a fixed point \(\sigma=\tau(\sigma)\), essentially a “Quine” (a program that prints itself) in the realm of subshifts. More precisely, this is a “self-similar” program, checking that it runs itself on arbitrarily large tiles, and performing on the side any desired calculation. In this manner arbitrary Turing machines may be simulated, by having them run on tiles of all sizes. We devote Section 5.3 to an outline the fixed point construction for our tiling systems, and Section 9 to an implementation of this scheme using a “universal tile set”, including some engineering details that we could not find elsewhere.

The geometry of the grid \([0,2^n-1]\times[0,2^n-1]\) in \(\Z^2\) and that of \((\Z/2)^n\times(\Z/2)^n\) are very different; nevertheless, we show that the natural bijection between these two sets, given by binary encoding, allows Turing machine calculations to be represented in both cases.

Rather than relying on general fixed-point properties, we actually construct the self-similar tileset. This has the benefit of giving us control on the entropy of the construction, which is quite low (in particular, sublinear).

2 Definitions and notations↩︎

For a group \(H\) and a set \(S\) we write \(H^{(S)}\) for the group of functions \(f\colon S \to H\) whose support \(\{s \in S \mid f(s) \neq 1\}\) is finite, under the pointwise product \((f \cdot f')(s) = f(s) \cdot f'(s)\).

If furthermore \(G\) is a group acting on \(S\), the wreath product \(H\wr_S G\) is the extension \(H^{(S)}\rtimes G\), with action \((f\cdot g)(s)=f(g s)\) of \(G\) on \(H^{(S)}\). When \(S=G\) with action by left translation, we simply write \(H\wr G\).

All the groups we consider are assumed to be effectively countable: there is a bijection between the group and \(\omega\) such that, via this bijection, the multiplication table \(\omega\times\omega\to\omega\) is computable.

2.1 The lamplighter group↩︎

The only wreath product we will consider in this article is the “lamplighter group” \({\mathcal{L}}=(\Z/2)\wr\Z\). It is convenient to set \(\mathbb{E}=\Z+\frac{1}{2}\), identified with the unit intervals with integer endpoints, and to write \({\mathcal{L}}= (\Z/2)^{(\mathbb{E})}\rtimes\Z\).

The name “lamplighter group” comes from the following interpretation. There is a lamp at every integer-plus-a-half position on the line, and each lamp may be ON or OFF. The lamplighter stands at an integer position. An element of the lamplighter group is a task for the lamplighter: she may move up and down the line an integer number of steps, and in doing so she may toggle a lamp she passes next to.

Seen from the perspective of the lamplighter, there is a natural action of \({\mathcal{L}}\) on the Cantor space of lamp configurations \((\Z/2)^{\mathbb{E}}\), which we call the lamp action; her motions amounts to shifting lamp configurations, possibly toggling the lamp that passes between positions \(\tfrac12\) and \(\tfrac{-1}2\).

Evidently every such task is a composition of elementary tasks (and their inverses), which are of two kinds: \(a\) “move up one step”, and \(b\) “move up one step, flipping the lamp encountered along the way”. (This explains our at first sight strange convention for the lamp positions: if they were also at integral positions, there would be ambiguity as to whether the departure or arrival lamp is to be flipped). Thus \(\{a,b\}\) is a generating set for \({\mathcal{L}}\), and in fact \({\mathcal{L}}\) admits a presentation \[{\mathcal{L}}=\langle a,b\mid (a^nb^{-n})^2\;\forall n\ge1\rangle.\] Using these generators, the Cayley graph of \({\mathcal{L}}\) (namely, the graph with vertex set \({\mathcal{L}}\) and edges from \(g\) to \(ag\) and to \(bg\) for every \(g\in{\mathcal{L}}\)) looks as in Figure 1, with edges \(a\) in green and \(b\) in red.

We single out important subgroups of \({\mathcal{L}}\): first, there is a natural map \(\phi\colon{\mathcal{L}}\to\Z\), extracting the movement of the lamplighter. Its kernel is \({\mathcal{S}}=(\Z/2)^{({\mathbb{E}})}\), which naturally decomposes as \({\mathcal{S}}={\mathcal{H}}\times{\mathcal{V}}\) with \({\mathcal{H}}=(\Z/2)^{(-\N-\frac{1}{2})}\) and \({\mathcal{V}}=(\Z/2)^{(\N+\frac{1}{2})}\).

Even though the group \({\mathcal{S}}\) is locally finite and therefore very far from the grid \(\Z^2\), its representation in the Cayley graph of Figure 1 appears like a grid, represented by the overlaid dashed blue edges (which may connect arbitrarily distant edges in the Cayley graph). We refer to \({\mathcal{S}}\) as the “sea level” of the Cayley graph, with \({\mathcal{H}}\) and \({\mathcal{V}}\) respectively the “horizontal” and “vertical” directions.

In fact, when coding configurations on the sea-level, we prefer to use the four directions North, South, West, East, based on the standard map orientation (North pointing up), viewing the sea-level “from above”. The Up and Down directions refer to movement of the lamplighter, assuming the street is oriented up-down.

We finally name some group homomorphisms. We denote by \(\iota\colon{\mathcal{S}}\hookrightarrow{\mathcal{L}}\) the natural inclusion, and write similarly \(\iota^-\colon{\mathcal{H}}\hookrightarrow{\mathcal{L}}\) and \(\iota^+\colon{\mathcal{V}}\hookrightarrow{\mathcal{L}}\). There is a natural projection \(\eta\colon{\mathcal{S}}\twoheadrightarrow{\mathcal{H}}\).

The Cayley graph of the lamplighter group belongs to a family of graphs called Diestel-Leader graphs. The full binary tree is the two-way infinite tree \(\mathcal{T}_2\), namely the \(3\)-regular tree oriented with constant out-degree \(1\). It comes naturally with a height function \(\beta\colon\mathcal{T}_2\to\Z\), compatible with the edge orientation. Then the Cayley graph in Figure 1 may be described by its vertex set \(\{(x,y)\in\mathcal{T}_2^2\mid\beta(x)+\beta(y)=0\}\), with an edge from \((x,y)\) to \((x',y')\) precisely when there is an edge from \(x\) to \(x'\) and an edge from \(y'\) to \(y\).

More generally, the Diestel-Leader graph \(\mathsf{DL}(p,q)\) has vertex set \(\{(x,y)\in\mathcal{T}_p\times\mathcal{T}_q\mid\beta(x)+\beta(y)=0\}\) and edges as above. It may also be described directly as follows as an edge-labeled graph: its vertex set consists of pairs \((x,n)\) with \(n\in\N\) and \(x\colon(\Z+\tfrac12)\to\Z\) of finite support, taking values in \(\{0,\dots,p-1\}\) at positions \(<n\) and values in \(\{0,\dots,q-1\}\) at positions \(>n\). There is an edge labeled \((x,y)\) from \(((\dots,x,\dots),n)\) to \(((\dots,y,\dots),n+1)\) with the ‘\(x\)’ and ‘\(y\)’ at position \(n+\tfrac12\). If \(p=q\), then this graph is the Cayley graph of \(\Z/p\wr\Z\); edges with label \((x,y)\) correspond to the generator “shift and add \(y-x\) to the lamp just crossed” of \(\Z/p\wr\Z\). In all cases, this labeling \(\mathsf{DL}(p,q)\) is at least as rich as the Cayley graph labeling, so all our claims easily extend to graph subshifts on \(\mathsf{DL}(p,q)\).

2.2 Subshifts, induction and pullback↩︎

Let \(G\) be a group. A subshift on \(G\) is a closed, \(G\)-invariant subset of \(A^G\), for a finite set \(A\); the action of \(G\) on \(A^G\) is given by \((g x)(h)=x(h g)\). For a finite set \(F\subseteq G\) and \(p\in A^F\) called a forbidden pattern we define \[S_p=\{x\in A^G\mid gx\restriction_F \neq p\quad\forall g\in G\},\] namely the subshift of those configurations on \(G\) that contain no translate of the pattern \(p\). A subshift of finite type (SFT) is a finite intersection of \(S_p\)’s. A sofic shift is a factor of a subshift of finite type (on a possibly different alphabet \(B\)) by a coding map \(B\to A\). An effective subshift is an intersection of \(S_p\)’s for a recursively enumerable sequence of forbidden patterns \(p\).

More generally, an (effective) Cantor system is an (effective) subshift, but with the finite set \(A\) replaced by a Cantor set \(A^\omega\), and with patterns only checking finitely many coordinates: a pattern is \(p\in (A^n)^F\) for some \(n\in\N\) and \(F\subseteq G\) finite, with corresponding \[S_p=\{x\in(A^\omega)^G\mid\forall g\in G:\exists f\in F:(g x)(f)\notin p(f)A^\omega\}.\] A Cantor \(G\)-system \(K\) is isomorphic to a subshift precisely when it is expansive, that is, there is a neighbourhood of the diagonal in \(K\) such that whenever \(x\neq y\in K\) the orbit \(\{(g x,g y)\mid g\in G\}\) escapes that neighbourhood.

A subshift of almost finite type (AFT) is the factor of an SFT by a covering map that is almost everywhere \(1\)-to-\(1\): there exists an SFT \(Y\) with covering map \(\pi\colon Y\to X\) such that the set of points in \(X\) with unique preimage has full measure with respect to every invariant Borel probability measure on \(X\). This definition does not require minimality of \(X\), but in that case implies that the set of points in \(X\) with unique preimage is comeagre (dense \(G_\delta\)). See hochman:recursive?*page 134 for a discussion.

If \(K\) is a finite abelian group, and \(X, Y\) are \(G\)-dynamical systems for some group \(G\), we say that \(X\) is a \(K\)-extension of \(Y\) if there is a bijection \(f\colon X \to Y \times K\) and a cocycle \(\eta\colon G \times Y \to K\) such that if \(f(x) = (y,k)\) then \(gx = (k + \eta(g, x), gy)\). Observe in particular that \(X\) is then an extension of \(Y\) with all fibers of cardinality \(\#K\). Now generalizing the idea of the previous paragraph, we say \(Y\) is almost \(K\)-to-\(1\) if there is a \(K\)-extension of \(Y\) which is AFT. (This is indeed a direct generalization: if \(1\) denotes the trivial group, an \(1\)-to-\(1\) extension is just a topological conjugacy, so almost \(1\)-to-\(1\) still means AFT in the new sense.)

Consider two groups \(F,G\) and a homomorphism \(\phi\colon F\to G\). Then, on the one hand, \(G\)-systems induce \(F\)-systems by pull-back: if \(G\curvearrowright Y\), set \(\phi^*(Y) = Y\) as a set, with \(F\)-action \(f\cdot y=\phi(f)\cdot y\). On the other hand, \(F\)-systems induce \(G\)-systems by induction: if \(F\curvearrowright X\), set \(\phi_*(X)=\{y\colon G\to X\mid y(\phi(f) g)=f y(g)\;\forall f\in F,g\in G\}\), with natural action \((g\cdot y)(g')=y(g' g)\).

Let us consider these operations for subshifts, namely \(Y\subseteq B^G\) and \(X\subseteq A^F\). In case \(\phi\) is surjective, the pull-back \(\phi^*(Y)\) is again a subshift, \[\label{eq:pullback} \phi^*(Y)=\{y\circ\phi\in B^F\mid y\in Y\}.\tag{1}\] In case \(\phi\) is injective, the induction of \(X\) is again a subshift, \[\label{eq:induction} \phi_*(X)=\{y\in A^G\mid \forall g\in G: y(\phi(-) \cdot g)\in X\};\tag{2}\] the verification is straightforward, the embedding \(\phi_*(X)\hookrightarrow A^G\) being given by \((y\colon G\to X)\mapsto(g\mapsto y(g)(1))\).

We briefly note that the pull-back \(\phi^*(Y)\) of a \(G\)-system by an injective map \(\phi\) is called a subaction; the pull-back of a subshift has no reason to be expansive, e.g.the pull-back of any infinite subshift to the trivial subgroup. The literature sometimes mentions “projective subactions” of subshifts; again for \(\phi\) injective and \(Y\subseteq B^G\), this is the \(F\)-shift given by 1 . It is the factor of the subaction given by restriction to a single copy of \(\phi(F)\) in \(B^G\).

We found out that there was a wide diversity in the simulation literature, where results of the following form are stated: “consider a subgroup \(H\le G\) satisfying ’’. Then every effective \(H\)-subshift \(X\) is a factor of a projective \(H\)-subaction \(X\) of a sofic \(G\)-shift”. In all the cases we witnessed, it turned out that \(H\) was also a quotient of \(G\), and the proofs actually gave the stronger statement that the pull-back of \(X\) is sofic. See aubrun-sablik:simulation?, barbieri-sablik:semidirect?, crumiere-sablik-schraudner:speed?, hochman:recursive?, barbieri:simulation? for the articles we have found in the literature that actually prove more than they claim. We exclusively use pull-backs and induction in this text, hoping this clarifies the setting somewhat.

3 Subshifts on locally finite groups↩︎

Consider a finite group \(F\), and its restricted product \({\mathcal{H}}=F^{(\N)}\), the group of finitely-supported functions \(\N\to F\). There is a natural map \(\sigma\colon {\mathcal{H}}\to {\mathcal{H}}\), the one-sided shift: \(\sigma(f_0,f_1,\dots)=(f_1,\dots)\). For every \(N \subset \N\), we can naturally consider \(F^{(N)}\) as a subgroup of \(F^{(\N)}\) (for finite \(N\) we may drop the parentheses). For \(n \in \N\) we write \(F^n\) for \(F^{\{0,1,...n-1\}}\). For \(f\in F,n\in\N\) we denote by ‘\(f_{@n}\)’ the element of \({\mathcal{H}}\) with a single ‘\(f\)’ in position \(n\).

With every \(x\in X_\tau\) is associated one or more branching directions \(b\in F^\N\): if \(x\in b_{@0}\tilde{\tau}(X_\tau)\), say \(x=b_{@0}\tilde{\tau}(x')\) for some \(b\in F,x'\in X_\tau\), and \((b',b'',\dots)\) is a branching direction of \(x'\), then \((b,b',b'',\dots)\) is a branching direction of \(x\).

Let \({\mathcal{H}}_n=\ker(\sigma^n) \cong F^n\) be the subgroup of \({\mathcal{H}}\) consisting of the first \(n\) factors; it is generated by all \(f_{@0},\dots,f_{@(n-1)}\) with \(f\in F\). Naturally \({\mathcal{H}}=\bigcup_{n\in\N}{\mathcal{H}}_n\). It is easy to see that, for \(m\ge n\), the values of \(\tilde{\tau}^n(x)\) on \({\mathcal{H}}_m\) depend only on those of \(x\) on \({\mathcal{H}}_{m-n}\). Thus \(X_\tau\) is also the topological closure of the \({\mathcal{H}}\)-orbit of fixed points of \(\tilde{\tau}\).

We think of \(\tau\) as a non-deterministic function, and when \(\#\tau(a) = 1\) for all \(a\), we write \(\tau(a) = \{b\}\) simply as \(\tau(a) = b\). This should not cause confusion.

There is a straightforward visualization of substitutional shifts via coset trees. The collection \(\bigsqcup_{n\ge0}{\mathcal{H}}_n\backslash {\mathcal{H}}\) of all cosets of \({\mathcal{H}}_n\) in \({\mathcal{H}}\) naturally forms a “corooted binary tree” \(\mathscr T_F\), with leaves the cosets of \({\mathcal{H}}_0=1\) and an edge between \({\mathcal{H}}_n h\) and \({\mathcal{H}}_{n+1}h\) for all \(n\in\N,h\in {\mathcal{H}}\). Since \({\mathcal{H}}_n\backslash {\mathcal{H}}\cong {\mathcal{H}}\) via \(\sigma^n\), we may also write the vertex set of \(\mathscr T_F\) as \({\mathcal{H}}\times\N\), with an edge between \((h,n)\) and \((\sigma(h),n+1)\) for all \(h\in H,n\in\N\).

Elements of \(X_\tau\) may then be given by parse trees. Consider pairs \((b,x)\) with \(b\in F^\N\) an infinite sequence of elements of \(F\) and \(x\colon\mathscr T_F\to A\) a labeling of the corooted \(\#F\)-regular tree. There is a natural action of \({\mathcal{H}}\) on such pairs, in which \({\mathcal{H}}\) acts trivially on \(F^\N\) and acts on \(\mathscr T_F\) by right multiplication on cosets; this last action reads \((g x)(h,n)=x(h\sigma^n(g),n)\) in the notation above. Again writing \({\mathcal{H}}\times\N\) the vertices of \(\mathscr T_F\), set \[X_\tau'=\{(b,x)\mid (x((f b_n)_{@0}h,n))_{f\in F}\in\tau(x(\sigma h,n+1))\text{ for all }h\in {\mathcal{H}},n\in\N\}.\] In effect, we are storing in \(X_\tau'\) an entire prehistory of applications of the substitution \(\tau\), as well as making explicit as \(b\) a choice of branching direction of \((b,x)\).

Subshifts of finite type, or sofic shifts, are entirely uninteresting on \({\mathcal{H}}\) since \({\mathcal{H}}\) is locally finite. However, quotients of substitutional subshifts under letter encodings \(A\to B\), and intersections with full shifts \(A_0^{\mathcal{H}}\) for some \(A_0\subset A\), are of great interest, as we shall soon see.

3.1 Almost odometric subshifts↩︎

There is a factor map \(X'_\tau\twoheadrightarrow F^\N\) mapping \((b,x)\) to the branching direction \(b\); this map is equivariant with respect to the action of \({\mathcal{H}}\) on \(X'_\tau\) and the natural action of \({\mathcal{H}}\) on its closure \(F^\N\), which we call the odometer.

For example, the Thue-Morse subshift from Example [ex:tm] is not odometric, because it is not even faithful. An example that gets closer, with \(F=\Z/2\), is \(\tau(t) = (t, t+1)\) on the alphabet \(\Z/3\). In this example, the natural odometer is a factor: from \(x\in X_\tau\) we recover \(b_n\) from \(x(1_{@n})-x(0)-1\). There is a natural action of \(\Z/3\) on \(X_\tau\) by addition of a constant, and which acts freely on fibres. Presumably no factor map is almost \(1\)-to-\(1\), though we have not shown this. The following example will be important for us:

It is the \({\mathcal{H}}\)-analogue of the “period-doubling”, or “ruler”, subshift, generated by the infinite word \(0100010101000100\dots\) with \(n\)th digit the parity of the largest power of \(2\) dividing \(n\). As a \(\Z\)-shift, it is a quotient of the Thue-Morse subshift by \(\Z/2\), but as an \({\mathcal{H}}\)-shift it is quite different:

4 Subshifts on the lamplighter group↩︎

We briefly recall that elements of the lamplighter group \({\mathcal{L}}\) may be represented as pairs \((s,n)\) with \(s\colon{\mathbb{E}}\to\Z/2\) finitely supported and \(n\in\Z\). We also recall the maps \(\iota\colon{\mathcal{S}}\hookrightarrow{\mathcal{L}}\) and \(\iota^-\colon{\mathcal{H}}\hookrightarrow{\mathcal{L}}\) and \(\iota^+\colon{\mathcal{V}}\hookrightarrow{\mathcal{L}}\) and \(\eta\colon {\mathcal{S}}\hookrightarrow {\mathcal{H}}\) and \(\phi\colon {\mathcal{L}}\twoheadrightarrow\Z\).

In this section we prove several variants of the claim “substitutive \({\mathcal{S}}\)-subshifts induce to sofic shifts on \({\mathcal{L}}\)”:

We also consider a slight variant of substitutional subshifts:

Of these, Proposition [prop:equalbranchingstructures] will be used as black box in our first proof of Theorem 3 (combined with the analogous results for the other embedding \(\iota^+\) of \({\mathcal{V}}\) in \({\mathcal{L}}\), at positions \(-\frac{1}{2}-\N\); direct products; intersections with subalphabets, and quotients). All these variants have very close proofs.

We finally prove the following result, which while not directly used for anything, is the starting point for our construction of a “small” aperiodic tileset in §4.3:

4.1 Marking corooted binary trees↩︎

We recall that tilesets on \({\mathcal{L}}\) are described by their neighbourhood: “spiders” specify legal edge colours on the neighbouring edges in directions \((a,b,a^{-1},b^{-1})\) of each vertex; and “tetrahedra” specify legal vertex colours at vertices \(\{v, a v, b^{-1}a v, b v\}\) along each relation \(b^{-1}a b^{-1}a v=v\). Note that the set of valid tetrahedra that eventually appear in the SFT is closed under the flip \((x,y,z,w) \leftrightarrow (z,w,x,y)\) which describes the same tetrahedron but viewed from vertex \(b^{-1}a v\) rather than from \(v\); if we only specify one orientation of a tetrahedron, the interpretation is that the other one is also allowed. We describe a spider tile as a list \((c_a,c_b,c_{a^{-1}},c_{b^{-1}})\) of colours, in that order.

Consider first the tileset \(\Theta_0\) with edge colours \(C_0=\Z/3\) and allowed spiders \((c,c,c+1,c)\) and \((c,c,c,c+1)\) for all \(c\in C_0\): \[\Theta_0=\{(c,c,c+1,c), (c,c,c,c+1)\mid c\in C_0\}.\] Thus at each vertex there is a single edge in the \(\phi\)-decreasing direction that is distinguished, namely the one with colour one more (modulo 3) than its three neighbours. We can also view the configurations as vertex colourings, by colouring every vertex \(v\) of the Cayley graph of \({\mathcal{L}}\) by the \(c\) appearing three times on the edges touching \(v\). This mapping from edge colourings to vertex colourings is obviously injective, since the colour of an edge is determined by its endpoint in the decreasing \(\phi\)-direction.

Recall from §3 that the corooted binary tree has as vertex set \(\N\times\N\), with edges connecting \((m,n+1)\) to \((2m,n)\) and \((2m+1,n)\) for all \(m,n\in\N\). Its leaves are \(\N\times\{0\}\).

One configuration in this SFT comes from the vertex colouring \(x\colon{\mathcal{L}}\to C_0\) defined by \[x(s,n)=\#\{k>n:s_k=1\}\bmod 3\quad\text{ for all }s\in(\Z/2)^{(\mathbb{E})},n\in\Z.\] As a typical model of a corooted binary tree appearing in this colouring, consider the span of the vertices \(\{(s,n)\mid n\le0,s(k)=0 \; \forall k>n\text{ except }s(\frac{1}{2})=1\}\), which is coloured \(1\). Note that its leaves are naturally identified with the subgroup \({\mathcal{H}}\), via the bijection between \({\mathcal{H}}\) and \(\N\) mentioned in Example [ex:tm]. There is, additionally, one full binary tree, \(\{(s,n)\mid s(k)=0 \; \forall k>n\}\) which is coloured \(0\).

These corooted binary trees will serve as parse trees for the induced shifts, in the proofs of the propositions. We may mark the non-leaf vertices of each tree with a finite amount of data \(B\) so that all vertices at same height share this data: set \(C_{1,B}=C_0\times B\), and allow spider colourings \(((c,b),(c,b),(c+1,b'),(c,b))\) and \(((c,b),(c,b),(c,b),(c+1,b'))\) at each spider for all \(c\in C_0,b,b'\in B\), calling the resulting tileset \(\Theta_{1,B}\). Consider now a vertex \(v\) which is a non-leaf in a tree \(\mathcal{T}\). The edge at \(v\) which does not belong to \(\mathcal{T}\) is a leaf of a new corooted binary tree \(\mathcal{T}'\), and it carries the data \(b'\) which uniformly colours \(\mathcal{T}'\); thus all vertices at same height as \(v\) in \(\mathcal{T}\), which are all the leaves of \(\mathcal{T}'\), share the data \(b'\).

In the SFTs of this section, the trees are quite wild, and the full dynamics are difficult to describe. In Section 5.7, we tame the trees, by running \(\Theta_0\) simultaneously up- and downward, and synchronizing the two processes. This is only strictly needed for our strongest simulation result, but may be of independent interest to some readers.

4.2 A simple \({\mathcal{S}}\)-aperiodic tile set↩︎

It seems that tile sets with no nontrivial \({\mathcal{S}}\)-periods are quite common, and in our search for strongly aperiodic tile sets, we found many of them. In this section, we exhibit the simplest one we know.

Let \(\Delta_{\text{count}}\) be the following set \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/jbkzvmgl.png}\label{/}\end{figure}\tag{3}\] of three tetrahedra (already closed under the permutation \((1 \; 3)(2 \; 3)\)).

To check that this is indeed the smallest example, we note first there is no nontrivial SFT with smaller alphabet, which would have size \(1\). The number of tetrahedra is also optimal, in that one can quickly work through all pairs (and singletons) of tetrahedra closed under the permutation \((1 \; 3)(2 \; 4)\), and conclude that the only non-trivial example implements the Thue-Morse substitution in the sense of Example [ex:tm], and the resulting SFT has exactly two configurations.

4.3 Aperiodic tilesets and undecidability↩︎

We now use the tilesets constructed above to solve two problems: the construction of a strongly aperiodic tileset, namely one all of whose tilings have trivial isotropy group, and the proof of undecidability of the tiling problem. These are direct proofs of, respectively, Corollary 5(1) and Corollary 4 from the Introduction. (This section is independent from the proofs of our main simulation results, whose proofs begin in the following section).

The method, for both problems, is to represent in \({\mathcal{L}}\) an infinite binary tree by \(\Z\)-translates of \({\mathcal{H}}\), and to use \({\mathcal{V}}\) and trees in the opposite direction to connect vertices at the same height. In this manner, we realize in \({\mathcal{L}}\) a union of “discrete hyperbolic planes”: the \(1\)-skeleton of the tiling of \(\mathbb{H}^2\) by pentagons with vertex set \(2^\Z(\Z+i)\).

We then apply the technique of Kari kari:revisited?, storing an element of \(\R\) or \(\R^2\) on each translate of \({\mathcal{H}}\), represented as an average (Beatty sequence); and forcing by the tileset each such element to be an affine image of the previous one. The existence of aperiodic piecewise-affine maps on \(\R\), respectively the undecidability of the mortality problem for piecewise-affine maps on \(\R^2\), let one conclude the proofs.

We have elected to represent the tilesets by tetrahedra; we are therefore considering vertex colourings, by a set \(C\) of colours; and a tileset is a subset \(\Delta\) of \(C^{\{1,a,a b^{-1},b\}}\), with entries written in that order. It determines the subshift \[X_\Delta=\{x\colon{\mathcal{L}}\to C\mid (x(v),x(v a),x(v a b^{-1}),x(v b))\in\Delta\text{ for all }v\in{\mathcal{L}}\}.\] Note that if \((c_1,c_2,c_3,c_4)\in\Delta\) then we may assume without loss of generality \((c_3,c_4,c_1,c_2)\in\Delta\) (by applying the condition to \(v a b^{-1}\)); we only specify half of the allowed tiles, assuming implicitly that they are completed by the above switch operation.

The proofs of these two results begin in the same manner. As colours \(C\) we consider a product \(C=\Z/2 \times I^3\times A\times B^2\), for some finite sets \(I,A,B\). The slots are respectively called the count, instruction, value and carry.

In the count slot, we allow the SFT from the previous section: \[\label{eq:count} \Delta_{\text{count}} = \{ (1, 1, 2, 1), (2, 1, 1, 1), (1, 2, 1, 2) \}.\tag{4}\] The role of this component is simply to ensure that no configuration is \({\mathcal{S}}\)-periodic (Lemma [lem:SimpleAperiodic]) in our “small” aperiodic tile set. It is likely that the other components also automatically ensure \({\mathcal{S}}\)-aperiodicity.

Consider next the instruction slot. In it, we allow \[\Delta_{\text{instruction}} = \{((w,x,z),(x,y,w),(w,y,z),(x,y,z))\mid w,x,y,z\in I\}.\] This has the effect of specifying an element in \(I\) across every level \(\phi^{-1}(n)\). Indeed view the numbers \(w,x,y,z\) on the four faces of the tetrahedron. The value \(y\) propagates in the second coördinate along an upwards-growing tree, the value \(z\) propagates in the third coördinate along a downwards-growing tree, and the values \(w,x\) are copies along removed edges respectively from an upwards- or downwards-growing tree. It follows that the first coördinate is constant across every level. For a colour \(c\) we call that first coördinate \(i(c)\in I\).

The value slot is simply an element of some set \(A\), written \(v(c)\), and we allow \[\Delta_{\text{value}} = \{(\ell,m,n,m)\mid \ell,m,n\in A\}.\] In words, we force the two values at the top of a tetrahedron to be identical. In the carry slot, we allow \[\Delta_{\text{carry}} = \{((q,r),(q,s),(r,s),(s,q))\mid q,r,s\in B\}.\] This has the effect of specifying an element between any two neighbouring vertices on a column of every level. Indeed on each downwards-growing binary tree two values are propagated, a “front” and a “back” one. Across every vertex, the \((q,s)\) values are turned into a \((q,r)\) and an \((r,s)\) value. (The “\((s,q)\)” in the last position is there because the meaning of “front” and “back” are reversed at that node). For a colour \(c\) we respectively call \(p^<(c)\) and \(p^>(c)\) the first and second coördinates of its carry slot.

For now we have not specified any constraint between the tree, instruction, value and carry slots. This we do as follows. Consider a vector space \(V=\R\) or \(\R^2\), and a family of affine transformations \(f_i(x)=M_i x+b_i\) on \(V\), one for each \(i\in I\). Let \(A,B\) be finite subsets of \(V\). We allow tetrahedron colourings \[\Delta=\Big\{(c_1,c_a,c_{a b^{-1}},c_b)\mid f_{i(c_1)}(v(c_a))+p^<(c_1)=\frac{v(c_1)+v(c_{a b^{-1}})}{2} + p^>(c_{a b^{-1}})\Big\}.\] In words, we force each tetrahedron to map the value on top, via \(f_{i(c_1)}\), to the average of the values on the bottom, give or take some carries.

These tiling constraints mean the following: on every column of every level, there are some values in \(V\). Assume that these values have a well-defined average; then every such average is the \(f_i\)-image of the average above it.

5 From effective subshifts to sofic shifts↩︎

We now proceed to the proof of our main results. We introduce a variant of the classical Wang tilings adapted to our locally finite groups. Recall that \({\mathcal{S}}\) denotes the elementary abelian group \((\Z/2)^{\mathbb{E}}\), and write \({\mathcal{H}}_n=(\Z/2)^{\{-1/2,\dots,1/2-n\}}\) and \({\mathcal{V}}_n=(\Z/2)^{\{1/2,\dots,n-1/2\}}\) and \({\mathcal{S}}_n={\mathcal{H}}_n\times{\mathcal{V}}_n\). For any bit sequence \(b\in(\Z/2)^{\mathbb{E}}\) we have bijections \(\eta_b\colon{\mathcal{H}}_n\to\{0,\dots,2^n-1\}\) and \(\nu_b\colon{\mathcal{V}}_n\to\{0,\dots,2^n-1\}\) given by \[\label{eq:etanu} g\in{\mathcal{H}}_n\mapsto\sum_{i=-1/2}^{1/2-n}(g_i\oplus b_i)2^{-1/2-i},\qquad g\in{\mathcal{V}}_n\mapsto\sum_{i=1/2}^{n-1/2}(g_i\oplus b_i)2^{-1/2+i}.\tag{5}\] Taken together, \(\eta_b\times\nu_b\) gives a bijection \({\mathcal{S}}_n\to\{0,\dots,2^n-1\}^2\).

Equivalently via the bijection \(\eta_b\times\nu_b\), a Wang tower is a tower of tilings of squares \(\{0,\dots,2^n-1\}^2\) in such a manner that each square is contained in one of the four quadrants of the next one. Yet equivalently, it is a tiling of a plane, half-plane or quadrant. Thus a Wang tileset admits a tower if and only if it tiles the plane; though for a given Wang tileset the space of Wang towers is only vaguely related to the space of Wang tilings of the plane, so these notions should be treated as distinct.

Our argument proceeds in two steps: firstly, we show that every Wang tileset may be encoded into a sofic shift on \({\mathcal{L}}\), in such a manner that the configurations visible on cosets of \({\mathcal{S}}\) are precisely the Wang towers. We then show how arbitrary effective shifts may be encoded by Wang towers.

5.1 From Wang tilesets to sofic shifts↩︎

Let \(B\subseteq D^4\) be a Wang tileset. We prove here that there is a subshift of finite type on \({\mathcal{L}}\) that, on every coset of \({\mathcal{S}}\), projects to a Wang tower for \(B\).

Choose an almost odometric substitution \(\tau_0\colon A_0\to{\mathscr P}(A_0^2)\), consider the alphabet \(A=A_0\times B^2\) and define the substitution \(\tau\colon A\to{\mathscr P}(A^2)\) by \[\tau\colon(a,(b,b')) \mapsto \{((\tau_0(a)_1, (b,b'')), (\tau_0(a)_2, (b'',b'))) \mid b'' \in B\}.\]

By Proposition [prop:equalbranchingstructures], there is a sofic shift \(Z_1 \subseteq A^{\mathcal{L}}\) with \(Z\restriction_{\mathcal{S}}= Y_\tau\). Recall from Definition [defn:ytau] that \(Y_\tau\) is the \({\mathcal{S}}\)-subshift in which each \({\mathcal{H}}\)-coset contains an element of \(X_\tau\), and the branching directions of all these elements are synchronized. Switching the roles of \({\mathcal{H}}\) and \({\mathcal{V}}\), there is a sofic shift \(Z_2\) whose restriction to \({\mathcal{S}}\) is the \({\mathcal{S}}\)-subshift in which each \({\mathcal{V}}\)-coset contains an element of \(X_\tau\), again with synchronized branching directions.

Consider a configuration in \(Z_1\), and specifically the contents on one of the subgroups \({\mathcal{H}}_n\). After appropriate translation in \({\mathcal{L}}\), we may assume that the first component of the configuration in \({\mathcal{H}}_n\) is \(\tau_0^n(a)\in A_0^{{\mathcal{H}}_n}\) for some \(a \in A\). We refer to passing to this unique shift as normalization. Since \(\tau\) is uniquely decodable, only the standard branching direction (corresponding to the lexicographic order) can produce this content, so the second component (in \((B^2)^{{\mathcal{H}}_n}\)) also uses the standard branching direction. We perform the exact same normalization for a configuration in \(Z_2\).

Projecting to the second component, every node in \({\mathcal{S}}\) contains symbols \((b,b')\in B^2\) coming from \(Z_1\) and \((b''',b'')\in B^2\) coming from \(Z_2\). We add the constraint \(b = b'''\) to our SFT, and declare \(b\) to be the symbol at the node, and \(b'\) and \(b''\) to be respectively the symbols at the east and north neighbours. One can easily check that \(\tau\) precisely transfers this information. We thus impose the additional constraints \(b_E=b'_W\) and \(b_N=b''_S\).

5.2 From effective subshifts to Wang tilesets↩︎

Let \(X\subseteq C^{\mathcal{H}}\) be any effective subshift. We shall construct a Wang tileset whose horizontal configurations represent \(X\).

Let us say a few words about what general subshifts on \({\mathcal{H}}\) look like. By definition, they are topologically closed subsets of \(C^{\mathcal{H}}\) that are closed under the action of the locally finite group \({\mathcal{H}}\). They are defined by forbidden patterns, which can be taken to have domains \({\mathcal{H}}_n\). Unlike on \(\Z\), where the different shifts of a pattern overlap by different amounts, with our \({\mathcal{H}}_n\)-domain convention two forbidden patterns cannot overlap nontrivially without having full overlap. On the other hand,, a single forbidden pattern with domain \({\mathcal{H}}_n\) has \(2^n\) different orientations in which we check for it, in each \({\mathcal{H}}_n\)-coset. We begin with an informal discussion of the construction. Our Wang tileset will be a product, where on the bottom layer we have a symbol \(aa' \in A^2\), in the middle layer we have a symbol \(c \in C\), and on the top layer we have a large number of tiles used to implement everything we need. The bottom layer is simply matched against the configuration in the underlying substitutional subshift from the previous section. The \(C\)-component is what we will project to in the end, so our logic should check that the contents of this comes from \(\eta^*(X)\) with \(X\) the effective subshift we started with. Thus, we should check that the \(C\)-values remain equal when moving in the south and north directions, which we can easily do with Wang tile rules directly by adding another layer (on this layer, send the colour \(c\) south and north, and simply send \(0\) west and east).

We will construct a Wang tileset in which each configuration on a large enough square splits into “macrotiles of level \(k\)”, which further split into macrotiles of level \(k-1\), and so on (the tiles themselves are thought of as level-\(0\) macrotiles). On the macrotiles of level \(k\), we overlay a power of the substitution \(\tau \times \tau\) (aligned with the position of the macrotile). The macrotiles should also have access to at least some values on the \(C\)-component, and should be capable of performing universal computation on these values. We then simply enumerate the forbidden patterns of \(X\) so that every forbidden pattern \(p \in C^{{\mathcal{H}}_m}\) gets enumerated in all large enough squares \({\mathcal{S}}_n\), and in these squares we check that we do not see the pattern \(p\) nor any of its \({\mathcal{H}}_n\)-shifts in the part of the pattern on the \(C\)-component that we have access to. It is also important that every \({\mathcal{H}}_n\)-coset is considered by arbitrarily large macrotiles.

Of course the Wang tiles do not have direct access to the group, so by checking the \({\mathcal{S}}_n\)-shifts of \(p\), what we really mean is that a square on \({\mathcal{S}}_n\) will shift \(p\) with respect to its own numbering, interpreting the horizontal positions on the square in binary and taking the natural bijection with \({\mathcal{H}}_n\).

We claim that if we perform such a construction, we are done. To see this, first note that indeed a forbidden pattern \(p\) of \(X\) cannot appear anywhere: in a normalized configuration on \({\mathcal{S}}_n\) large enough that a large square is constructed there, we explicitly check that \(p\) does not appear if it fits the area the square considers, and by assumption every area is considered by some macrotile. In a non-normalized configuration we of course check the same constraint, since if the normalizing shift is \(h^{-1}\) then we are simply checking against translates all \(gh \cdot p, g \in {\mathcal{H}}_n\) instead of all translates \(g \cdot p, {\mathcal{H}}_n\), and this is the same set. Conversely, if \(x \in X\), then no matter what the substitutive structure is, we can simply overlay the macrotiles according to the substitutive structure, and write \(x_h\) as the \(C\)-colour at every element of \(\eta^{-1}(h)\) and none of the forbidden patterns will match with the contents of \(x\).

There are two known ways to implement this general plan, the Aubrun-Sablik construction (based on Robinson tiles) and the fixed-point tilesets of Durand-Romashenko-Shen. We will use the latter, describing it at a high level in the next subsection and in more detail in §9.

5.3 The fixed point construction↩︎

In this section, we outline the fixed point construction of durand-romashchenko-shen:fpa?, durand-romashchenko-shen:1d2d? in our setting. Consider two Wang tilesets \(B,B'\) and an integer \(N\ge2\). A simulation of \(B\) by \(B'\) is an injective map \[S\colon B\to\{\text{tilings of \{1,\dots,N\}^2 by }B'\}\] preserving side matchings and such that every \(B'\)-tiling is uniquely decomposable into \(N\times N\)-squares, called macrotiles. Consider a \(B'\)-tiling \(x\) all of whose \(N\times N\)-squares are in the image of \(S\), and let \(S^{-1}(x)\) denote the \(B\)-tiling obtained by replacing each such square by its \(S\)-preimage. Every tile in \(x\) is called a child of the tile in \(S^{-1}(x)\) it corresponds to, while that tile is called its parent.

A simulation of \(B\) may be produced as follows. Imagine that \(B\) is represented as an algorithm testing \(B(d_N,d_E,d_S,d_W)\) rather than as a subset of \(D^{\{N,E,S,W\}}\), and that this algorithmic description is succinct, i.e.consumes much less space than \(\#D^4\). Then the \(N\times N\)-representations of \(B'\) could consist of a universal Turing machine with some binary encoding of \(D\) on its four sides, and a data area containing the program computing \(B\). This universal Turing machine could even perform some side calculations for us in its spare time.

The construction may then be iterated: \(B'\) may be simulated by \(B''\), using \(N'\times N'\) grids, etc. Furthermore, all these tilesets may be assumed to contain the same universal Turing machine, and execute the same program: a part of the program should ensure that the data area on the simulated tile contains the same program as the original tile.

This is, in effect, a concrete realisation of Kleene’s fixed point theorem, that asserts that for every computable map \(\pi\colon\{\text{programs}\}\righttoleftarrow\) there exists a program \(p\) such that \(p\) and \(\pi(p)\) are equivalent.

For our purposes, the side calculations to be performed by the universal Turing machine are to enforce a given effective subshift \(X\subseteq C^{\mathcal{H}}\). Recall from the previous section that the original tileset contains a ‘\(C\)’ field to store, on each column, a coördinate of \(C^{\mathcal{H}}\). Macrotiles have access to larger and larger segments of coördinates, namely longer and longer subwords of elements of \(C^{\mathcal{H}}\), and can test them against a \(\Pi^0_1\) condition.

The discussion in §§5.4,5.5 is very similar to the one in durand-romashchenko-shen:1d2d?*Sections 3–5, though we make some slightly different choices already at a high level. In §5.6 we deal with effective systems rather than subshifts (namely \(C\) is the Cantor set \(\{0,1\}^\omega\) rather than a finite set; its bits are fed one after the other to the tileset in a “Toeplitz” manner). This requires some new ideas (although compared to many other existing fixed-point constructions, including ones found in durand-romashchenko-shen:fpa08?, they are not particularly difficult). For the “standard part” of the discussion, §§5.4,5.5, we give in the appendix (Section 9) a more complete argument with “explicit UTM details”.

5.4 The basic construction↩︎

Let \(n_1, n_2, \dots\) be a sequence of numbers; we will describe a tile set for each level \(k = 1, 2,\dots\). Ultimately, we will only implement the tile set for \(k = 1\), and the \(k\)th tile set appears only through \(k-1\) layers of simulation, but it is useful to at first think of all these tile sets as of the same nature, with \(k\) just acting as a parameter.

Initially, we have our tiles of level \(k\) remember a position in \(\{0,\dots,2^{n_k}-1\}^2\). Recall that our tilesets have access to finitely many bits of their address, coming from the substitution (e.g.the period-doubling substitution from Example [ex:pd] on both \({\mathcal{H}}\) and \({\mathcal{V}}\)) using which they are built. We synchronize our tiles with the lowest level of the substitution, so that our tilings split into macrotiles. Furthermore, these tiles will share a symbol sub, and we check that the base substitution agrees with sub, in the sense that the contents of the block indeed are a \(n_k\)th substitutive image of this symbol. Note that at this point, our tiling system admits a unique tiling assuming the base substitution is \(2\)-stepwise recognizable (every \(2 \times 2\)-block has a unique desubstitution, by Lemma [lem:pd]). We will also need to synchronize a symbol psub, which represents the symbol on the next level (its “correctness” will be checked later).

Next, we overlay, on top of our tiles, “wires” that allow transmitting information between neighbouring macrotiles. For this we add a new layer to our tiles. On the south borders of our macrotiles, the westmost \(4 t_k\) tiles will carry a bit on this layer, and using local rules we transmit the first (respectively second, third, fourth) \(t_k\) bits to the corresponding area in the neighbouring macrotile on the west (respectively north, east, south). The drawing of the wires can be essentially arbitrary, the only requirement is that it is computationally easy to describe as a function of \(k\).

The value of \(t_k\) should be large enough to allow sending all the color information. We need \(\mathcal{O}(n_k)\) bits for the colors to send the position, and it turns out that all the other information (sub, psub, …) requires very few bits in comparison, so \(\Theta(n_k)\) will suffice for everything.

Next, on yet another layer of the SFT we overlay a computation of a universal computational device \(M\), in the sense that successive rows, starting from the bottommost one, will contain successive computational steps of \(M\). The idea is that the computation of \(M\) makes our macrotiles simulate the macrotiles of level \(k+1\) (including the computation of \(M\), of course). Then our macrotiles will, as desired, merge into macrotiles of level \(k+1\), which then merge into macrotiles of level \(k+2\), and so on. After all is said and done, we will set \(k=1\) and obtain in this manner the desired SFT.

In the implementation section, we will use a “universal tile set” as \(M\) (as it is easier to work with), but a more standard choice is to use a universal Turing machine. A universal Turing machine takes as input a word of the form \(\texttt\%p\texttt\#w\texttt\$\), where the word \(p\) describes an arbitrary computational procedure (another Turing machine), which will then be simulated on the input word \(w\). Furthermore, the simulation should not take an excessive amount of time. There exist UTM for which the simulation always takes polynomial time in the computational complexity \(t\) of \(p\) (our universal tile set performs the simulation in time \(t \log t\)). As stated, the input \(\texttt\%p\texttt\#w\texttt\$\) will be written on the south row of the macrotile, on a new layer, and \(M\) performs its computation above this.

After the wire contents, we have many other pieces of information that need to be stored on the bottom row, and we make canonical choices about what is stored where: some area contains a number \(k + 1\) telling us the level of the tile set; some area of length \(\mathcal{O}(n_{k+1})\) is used for the position of the higher level macro tile; for macrotiles that are part of wires we need to have one bit available for wire transmission; we need a constant number of bits for simulating \(M\) itself; and of course the program \(p\) has to be written somewhere as well. Finally, all the information is synchronized with the neighbours. Note that for this to be possible, we need the growth constraint that \(2^{n_k}\) is much larger than \(n_{k+1}\).

The above description is straightforward to turn into a program for \(M\): In all cells, we perform the calculations to check whether we are on a wire, and transmit bits accordingly, and we check that the parent macrotile is simulating \(M\) correctly. We also synchronize the level \(k\) (i.e.if the present cell is supposed to code a bit of this level number, we check that the number is indeed incremented by one) and check the value of psub (by checking that sub is indeed what appears in the present position, when psub is substituted \(n_k\) times). Note that \(M\) is fixed, so simulating it amounts to part of \(p\) describing a simulation of \(M\) itself.

On the bottom row, there is a little more to do. What \(M\) should do (i.e.what \(p\) should require it to do) in the level-\(k\) tile is to read the current horizontal position of the present tile in the parent (level-\((k+1)\)) tile, and depending on this position check that the colours sent northward correctly initialize the computation. If we are in the program area (describing \(p\)), we should send the corresponding position of \(p\). To do this, \(M\) will read the corresponding symbol of \(p\) from the tape.

The other information is initialized similarly. For example, if the coördinates described by the wire bits are in the area describing the current macrotile level, we should check that a bit of the number \(k+1\) is indeed written there. If we are in the area containing a bit of sub, we should check that it contains the correct bit of psub.

We now obtain an infinite sequence of simulations. In particular, note that, assuming unique recognizability of the substitution, all the symbols sub are correct.

5.5 Remembering sequences of bits↩︎

Let us now explain how to remember finite subwords from an initial sequence overlaid on top of our configuration. The sequence is vertically constant, and horizontally can be arbitrary. First, we decide for each macrotile a set of columns that fit inside it, and which it is “responsible for”. The important things are that this choice is natural (so that we can describe it quickly with a Turing machine), that it does not grow too quickly, and that it does tend to infinity. Our choice is that a macrotile which is at height \(h\) in its parent tile (note that we can read its position from the wire contents) is responsible for the columns inside it, which belong in the natural block of size \(2^k\) containing the position \(h\). One could of course also just take the \(h\)th such block, but this is (ever so slightly) more complicated to implement.

To make sure that some block is indeed considered by a macrotile, we should have \(2^{n_k} > \prod_{i < k}2^{n_i}\), or equivalently \(n_k > \sum_{i < k} n_i\). The choice \(n_k = 4^{k+c}\) works for this. Note that \(n_{k+1} = 4^{k+1+c}\) is certainly \(o(2^{4^{k+c}})\), so the growth constraint discussed in the previous section is satisfied. The macrotile will know the word it is responsible for, in a variable word. Similarly as with the substitution symbol, we should also also know the word of the parent pword, so we can check its value is consistent with the actual word the parent is responsible for. Of course, to check such information, the tiles on level \(k\) must know the height at which the parent is in its grandparent of level \(k+2\), in a variable ppos. It is easy to check that with our choice of the sequence \((n_k)_k\), we have plenty of space for this information.

The check of consistency of pword is easy: We check if the column the present macrotile is on – when translated to the internal coördinates of the parent tile, are contained in the interval (which is exactly twice longer) that the parent considers. This calculation is straightforward, as we have access to our own position (in the wires), know the position of the parent in the grandparent, and we have simple formulas for all the sizes involved and the choice of the column a macrotile of a particular level is responsible for.

Note that, as we have added new information to our tiles, we need to ensure its consistency. So again macrotiles that sit on the bottom of their parent tile, if they are in a position describing a bit of word, we check consistency with the word pword, and similarly for ppos (checked against wire contents).

Now, consider the tile set obtained by setting \(k = 1\) initially, and initially having the correct bit pairs on the tapes of the macrotiles of level \(1\) (pairs because \(2^1 = 1\)) ensured by the SFT rule. An easy induction shows that on every level, on every level the word in the word variable of a macrotile of level \(k\) is indeed the word it believes it is. Finally, we can use a little bit of time to check an arbitrary constraint on this word.

5.6 Remembering infinitely many bits↩︎

Finally, let us consider effective \({\mathcal{H}}\)-systems, namely \(X\subseteq C^{\mathcal{H}}\) with \(C=\{0,1\}^\omega\). For each sequence \(b\in C^{\mathcal{H}}\) to be checked for inclusion in \(X\), each coördinate \(b_g\) is a sequence \((b_{g,0},b_{g,1},\dots)\) of bits.

Instead of vertically constant sequences, we store each \(b_g\) on a column as a Toeplitz sequence: at height \(i=2^j(2k+1)\) we store \(b_{g,j}\). In other words, in all natural \(2\)-blocks, the top symbol is \(b_{g,0}\). Then out of the bottom bits, the ones that are in the top half of natural \(4\)-blocks are all \(b_{g,1}\), and we continue recursively. The contents of different columns are independent (apart for sharing the underlying substitutive structure). This is easy to achieve with the substitution machinery built in Section 4.

We show in this section that we can in a sense remember all these bits, simultaneously on every column. We will then combine this with ideas used in the previous section to get access to multiple columns at once, which then allows performing arbitrary computation on the entire set of sequences.

To do this, we argue similarly as we did with word and pword in the previous section. Now, each macrotile is responsible for a single column col and contains all the bits in that column of the macrotile in a list called bits, and we also know the corresponding information pcol, pbits. We need to remember exactly \(\ell_i\mathrel{\vcenter{:}}=\sum_{i \leq k} n_i\) bits in bits, where \(L_k\mathrel{\vcenter{:}}=2^{\ell_i}\) is the size of the \(k\)-level macrotile (in absolute number of cells per side, assuming we are actually dealing with the first level tile set). The first \(\ell_k-1\) bits are exactly \(b_0 b_1 ... b_{\ell_k-2}\), and the last one – the bit on the southmost row – can in principle represent any \(b_i\) with \(i\geq\ell_k-1\). We call this the high-level bit.

We need to make a minor modification to how we pick the column we are responsible for. Namely, previously the macrotile of level \(k\) at height \(h\) in its parent tile was responsible for the bits in the (word that the) column \(h\) (belonged to), and we did not have a separate col variable. We cannot do the same now: Suppose a macrotile of level \(k\) is responsible for the \(j\)th column. Then in particular, it needs to know the bit in this column on the bottom row (the high-level bit \(b_i\)). This bit is of course known to a single macrotile of level \(k-1\) inside it, namely the one on the bottom row. Thus, on the bottom row, the \((k-1)\)-macrotile containing the \(j\)th column of its parent tile must itself be responsible for that column.

To combat this, at all “key heights”, namely whenever ypos is zero or a power of \(2\), the column of responsibility is changed to be the \(j\)th in all tiles. As we explain later, it is important (for getting an almost \(1\)-to-\(1\) extension) that at other heights the column of responsibility is chosen based on the height only, so on these columns we set \(\texttt{col} \equiv \texttt{ypos} \bmod L_{k-1}\). By our choice of \(n_k\), note that \(\texttt{ypos}\bmod L_{k-1}\) does reach every value at non-special heights (for example, in the last quarter of the heights). Just as with word and pword, the information between a child and a parent’s bit information is synchronized whenever the column of responsibility is the same.

A bit of intelligence is needed to do this synchronization, namely we should check which bit we are responsible for, using the Toeplitz structure: The tile at the key height \(0\) will synchronize its high-level bit with the high-level bit of its parent. The tile at key height \(2^h\) will synchronize its high-level bit with the \((h + \ell_{k-1})\)th bit of pbits. At non-key heights, we should look at the position of the last \(1\) in the binary representation of col and then use the same formula to figure out which bit we are responsible for.

Next, now that each tile knows all the bits of one column inside it, it is not difficult to adapt the construction of the previous section to propagate words instead of individual symbols. We can mostly forget the details of the previous construction, except the fact that we remember the bits coded on a particular column.

As in the previous section, let us again have each tile be responsible for the contents of a sequence of columns inside it, but now it is a word of length \(2^k\) over the alphabet \(\{0,1\}^k\), where a single symbol represents the bits \(b_0, ..., b_{k-1}\) of a particular column. We call this area the stripe of responsibility. We want the level to “drag behind” the bits process, so we take the stripe of responsibility to be simply the stripe that contains the pyposth column of the grandparent, if it is inside the present tile, and otherwise we do not have a stripe of responsibility. Let us call the information psword (for stripe word of the parent).

To ensure that the bits of psword are correct, we use bits: we observe that the growth of the depth up to which we are responsible for on the stripe of responsibility is small enough that every tile of level \(k-1\) already knows all bits up to this level on its column of responsibility (without looking at the high-level bit). Thus, any tile that is responsible for the column containing the grandparent’s pypos column (and one exists if said column intersects the parent tile at all, since col goes through every column) can actually supply these bits.

Finally, having access to the stripe words, we can easily verify an arbitrary condition on them.

5.7 The SFT \(X_{\mathrm{tree}}\) on \({\mathcal{L}}\)↩︎

In this section, we introduce and study in detail an SFT \(X_{\mathrm{tree}}\), which is a very efficient implementation of the idea from Section 4.1. The idea is to run two copies of the SFT with spiders \(\Theta_0\), one upward and one downward, and synchronize them, although we elect to introduce this SFT through tetrahedra instead. It is by far the most interesting “small, naturally occurring” SFT we have found on the lamplighter group, and thus may be of independent interest. However, only our strongest statements actually need the results of this section.

In \(X_{\mathrm{tree}}\), the vertices of \({\mathcal{L}}\) are coloured by the set \(C_0=(\Z/3)^2\), and the allowed tetrahedra are \[\Delta_{\mathrm{tree}} = \{((t,u),(t,u),(t,u+1),(t+1,u)) \mid (t,u) \in C_0\}\] (as usual, in the order \((v, a v, b^{-1}a v, b v)\)) for each \((t,u) \in C_0\). This gives a total of \(9\) tetrahedra, and as is our convention, we include also the other orientations, to get a total of \(18\). More pictographically (the lamps are explained below) this is \[\begin{tikzpicture}[scale=0.9] \foreach\label/\o/\a/\ab/\b/\shift/{\mathcal{L}}in {(first orientation; ``lamp off'')/{(t,u)}/{(t,u)}/{(t,u+1)}/{(t+1,u)}/0cm/\large\faLightbulbO,(second orientation; ``lamp on'')/{(t,u+1)}/{(t+1,u)}/{(t,u)}/{(t,u)}/6cm/\tikz{\node at (0,-0.05){\large\textcolor{orange}{\faLightbulbO}};\foreach\a in {-30,0,...,210} {\draw[orange] (\a:0.14) -- (\a:0.25);}}} { \begin{scope}[xshift=\shift] \coordinate[label={below:\scriptstyle\o}] (A) at (0,0); \coordinate[label={below right:\scriptstyle\ab}] (B) at (1.5,1); \coordinate[label={above:\scriptstyle\a}] (C) at (-1.1,2); \coordinate[label={above:\scriptstyle\b}] (D) at (1.1,2); \draw (A) -- (B) -- (D) -- (A) -- (C) -- (D); \draw[dashed] (B) -- (C); \node at (0,2.9) {\label}; \node at (0.3,1.2) {{\mathcal{L}}}; \end{scope} } \end{tikzpicture}\]

In addition to the mental picture of trees, explained in the previous section, another important intuition to keep in mind is that the left component is counting lamps that are on below the head, modulo \(3\), and the right component counts the lamps that are on above the head. Since this is a subshift, it cannot know the “real” orientation of the lamplighter group, so at each node, either \(a\) or \(b\) will correspond to flipping a lamp (but as we will see, this orientation will be consistent throughout the group). For example, when moving upwards, i.e.from \(v\) to \(av\) or \(bv\), exactly one choice will move upward and leave a lamp lit on the edge it traverses, and this corresponds to the edge of the tetrahedron whose vertices are labeled \((t,u)\), \((t+1,u-1)\) (since one more lamp is now on on the left, and one less on the right). In the figure, we have included a lamp, which indicates whether the light “at the tetrahedron” is on, from the perspective the front bottom node \(v\).

We will prove the following properties of \(X_{\mathrm{tree}}\):

• It has similar structure as the SFT coming from \(\Theta_0\), i.e.for every \({\mathcal{V}}\)-coset we can interpret it as the frontier of a corooted binary tree. (Lemma [lem:WeeTheta])

• It is nonempty. (Lemma [lem:WeeNonempty])

• Every configuration in it is \({\mathcal{S}}\)-aperiodic. (Lemma [lem:WeeAperiodic])

• It is of zero entropy. (Lemma [lem:WeeZeroEntropy])

• It is a \((\Z/3)^2\)-extension of the lamp action (see §2.1) of the lamplighter group. (Proposition [prop:WeeTechnical])

• It is minimal and uniquely ergodic. (Corollary [cor:Wstrictlyergodic])

As a corollary, we obtain also that the action of the lamplighter group on the space of lamps is sofic, but not SFT, see Corollary [cor:lampactionsofic].

(Some of these statements imply the others, but this list follows the order in our exposition.)

To begin the study, consider the first coördinate \(t\). Projecting to this coordinate, \(X_{\mathrm{tree}}\) is, in the language of tetrahedra, the same subshift as the tileset \(\Theta_0\) above: keeping all edges in \({\mathcal{L}}\) whose \(t\)-coördinate are equal produces a union of binary trees growing “downwards” (in negative \(\phi\)-direction). More precisely, a direct calculation proves the following lemma (noting that the existence of a block map does not require the subshift to be nonempty).

Similarly, the second coördinate \(u\) serves to mark binary trees growing “upwards”, and the combination of both marks two families of binary trees. The additional property is that the removed edges are the same for the upwards and downwards families. As hinted above, a priori this could mean the subshift is empty (in which case the previous lemma would be trivial). We show that it is not empty.

Aperiodicity in the \({\mathcal{S}}\)-direction appears to be very common for SFTs on the lamplighter group, in that we found many examples with this property (which did not lend themselves to proving full strong aperiodicity) before finding \(X_{\mathrm{tree}}\).

We now proceed to the main structure theorem for \(X_{\mathrm{tree}}\).

Intuitively, the cocycle simply describes how the “sum of lamps” changes under action of \(g\), on both sides of the street. The cocycle value is \[(\text{number of differences on left}, \text{number of differences on right}).\]

In the following statement, recall that a subshift is strictly ergodic if it is minimal and uniquely ergodic.

6 Proofs of the main statements↩︎

The constructions from the previous section are all that is needed to complete the proofs of our main statements, which we recall for convenience:

Recall that \(\Pi^0_1\) is the complexity class of problems that can be (computably, many-one) reduced to the complement of the halting problem of Turing machines. A problem is \(\Pi^0_1\)-hard if the converse holds, and \(\Pi^0_1\)-complete if it is \(\Pi^0_1\) and \(\Pi^0_1\)-hard; see e.g. rogers:computability?.

Recall that the Kolmogorov complexity of a string \(s\in\{0,1\}^n\) is the minimal length of a Turing machine computing \(s\). Naturally \(\{0,1\}\) may be replaced by any finite alphabet \(A\), and \(n\) may be replaced by any finite set, for example the subset \(\bigcup_{k=0}^n\{a,b\}^k\) of \({\mathcal{L}}\).

The following theorem is not new, but we obtain a new proof of it, illustrating the generality of simulation methods. Recall that the sunny-side-up shift on a group \(G\) is the set of configurations \(x\in\{0,1\}^G\) with at most one ‘\(1\)’.

We finally prove that substitutive \({\mathcal{S}}\)-subshifts are sofic. This is analogous to what happens on the plane. We explain how to obtain this from the fixed point argument, only sketching the differences with the proof of Theorem 3.

We finally rule out in a quite general setting a possible strengthening of Theorem 3:

7 Baumslag-Solitar groups↩︎

We expect that a similar simulation theory could be developed on the amenable Baumslag-Solitar groups, whose Cayley graphs, instead of being horocyclic products of two trees, are horocyclic products of a tree and a hyperbolic tiling. In this section, we show that at least some simulation results can be obtained for Baumslag-Solitar groups by simulating the lamplighter group in them. We concentrate on the group \[\mathrm{BS}\mathrel{\vcenter{:}}= \mathrm{BS}(1, 2) = \langle a, b \mid a^b = a^2 \rangle.\]

We recall an SFT from esnay-moutot:bs?. For \(c \in \{0, 1\}\) define the substitution \(\tau_c\colon\{0, 1\} \to \{0, 1\}^2\) by \(\tau_c(1) = 00\), \(\tau_0(0) = 01\), \(\tau_1(0) = 10\). Let us define an SFT \(Y\) on \(\mathrm{BS}\) over the alphabet \(\{0, 1\} \times \{0, 1\}\) with the following allowed patterns on \(\{1, a\}\): \[\{ (1 \mapsto (c, *); a \mapsto (c, *)) \mid c \in \{0, 1\} \},\] and the following allowed patterns on \(\{1,a,b\}\): \[\{ (b \mapsto (c, d); 1 \mapsto (*, \tau_c(d)_0); a \mapsto (*, \tau_c(d)_1)) \mid c, d \in \{0, 1\} \}\] (note that here we define two SFTs by allowed patterns and take their intersection).

A detailed study of this SFT can be found in esnay-moutot:bs?*§3. The crucial point is that on each \(\langle a \rangle\)-coset we have a substitutive configuration for one of the two substitutions, and the \(\langle a\rangle\)-cosets above (= translated by \(b\)) contain its desubstitutions under \(\tau_0\) and \(\tau_1\) respectively. Here is a typical picture of a configuration in \(Y\):

We can easily interpret every connected component from every configuration in this SFT as a Cayley graph of the lamplighter group: the generator \(b\) of \(\mathrm{BS}\) corresponds directly to the generator \(b\) of \({\mathcal{L}}\), and the generator \(a\) of \({\mathcal{L}}\) corresponds to either \(a b\) or \(a^{-1}b\), depending on the first bit the configuration at the end of the edge. This is illustrated in Figure 2. In the terminology of bartholdi-salo:ll?, we obtain the following:

Every configuration in \(Y\) defines a graph, which generically is the Cayley graph of \({\mathcal{L}}\). In countably many cases, the graph will consist of two disjoint copies of the Cayley graph of \({\mathcal{L}}\).

We now detail the construction of a \(\mathrm{BS}\)-SFT starting from a \({\mathcal{L}}\)-SFT. Let \(\Theta\subseteq A^{\{e, a, b^{-1} a, b\}}\) be a set of forbidden tetrahedra on the lamplighter group, defining an SFT \(Z\). Define an SFT \(X \subset Y \times A^B\) by adding to \(Y\) the following forbidden patterns: \[\{ (1 \mapsto (*, *, z); b \mapsto (0, *, x); a \mapsto (*, *, w); ba \mapsto (1, *, y)) \mid \forall (x,y,z,w) \in T \}.\] It is easy to see that the natural projection \(\pi_Y\colon X \to Y\) is surjective, and for a configuration \(y \in Y\), there is a natural correspondence between \(Z\) and the configurations of \(X\) in \(\pi^{-1}(y)\). We deduce the following results.

8 Open questions↩︎

For concreteness, we have concentrated on the lamplighter group, but the methods generalize directly to at least some groups. In particular, there is no difficulty in extending all the constructions to \(K \wr \Z\) for a finite group \(K\).

On the other hand, it would be useful to have more flexible tools to understand subshifts on groups such as \(\Z \wr \Z\) or \(K \wr \Z^2\), for which our method does not immediately extend. Definitely the undecidability of the domino problem and existence of aperiodic SFT’s are not in doubt, but the questions of which effective systems pull back to sofic shifts may be more subtle.

There is a general construction, that of horocyclic products, which may be the natural direction for generalizing our construction. Consider two graphs \(\mathscr G_1,\mathscr G_2\) each endowed with a Busemann function: a height function \(\eta_i\colon V(\mathscr G_i)\to\Z\) that varies at most by \(1\) along edges; and form the graph \(\mathscr G\) with vertex set \(\{(v_1,v_2)\in V(\mathscr G_1)\times V(\mathscr G_2)\mid\eta_1(v_1)+\eta_2(v_2)=0\}\), and with an edge from \((v_1,v_2)\) to \((w_1,w_2)\) whenever (\(v_1=v_2\) or there is an edge from \(v_1\) to \(v_2\)) and (\(w_1=w_2\) or there is an edge from \(w_1\) to \(w_2\)).

Considering \(\mathscr G_1=\mathscr G_2\) the ternary tree with \(\eta(v)\) the “distance to infinity” along a chosen ray in the tree, we obtain the Cayley graph of \({\mathcal{L}}\). There are other interesting examples: take as before for \(\mathscr G_1\) the ternary tree, and let \(\mathscr G_2\) be the (\(1\)-skeleton of the) tiling of \(\mathbb{H}^2\) by hyperbolic pentagons with vertex set \(2^\Z(\Z+i)\); the Busemann function is \(\eta(2^n(m+i))=n\). Then the horocyclic product is essentially the Cayley graph of the Baumslag-Solitar group \(\mathrm{BS}\), which fits in an exact sequence \[\begin{tikzcd} 1\arrow{r}& \Z[1/2]\arrow{r}& \mathrm{BS}(1,2)\arrow{r}{\psi}& \Z\arrow{r}& 1\end{tikzcd}\] (More precisely, half the edges have to be shifted one position horizontally.) Here we showed that one can interpret this as the lamplighter group to translate results from the lamplighter group to it, but perhaps a better method would be to have a uniform construction for such horocyclic products.

A uniform approach would certainly help in understanding induction in the context of \(\mathrm{BS}(1,2)\). The induction of an \(\langle a \rangle\)-subshift is not necessarily \(\mathrm{BS}\)-sofic by Observation 1. However, the analogue of Theorem 3 to \(\mathrm{BS}\) would ask to pull back effective \(\Z[1/2]/\Z\)-subshifts to \(\Z[1/2]\) and then induce them to \(\mathrm{BS}\), expecting to obtain sofic \(\mathrm{BS}\)-subshifts in this manner.

It is also possible to define the horocyclic product of more than two graphs: given graphs \(\mathscr G_i\) for \(i\in\{1,\dots,n\}\), each with a Busemann function \(\eta_i\), their horocyclic product has as vertex set \(\{(v_1,\dots,v_n)\in V(\mathscr G_1)\times\cdots\times V(\mathscr G_n)\mid \eta_1(v_1)+\cdots+\eta_n(v_n)=0\}\), with an edge from \((v_1,\dots,v_n)\) to \((w_1,\dots,w_n)\) when \(v_i=w_i\) for all \(i\) except at most \(2\), which are joined by an edge.

For example, the horocyclic product of three copies of the ternary tree is the Cayley graph of a finitely presented group containing the lamplighter group; see baumslag:fpmetabelian? and bartholdi-n-w:horo?.

We finish with some questions about possible dynamics of SFTs. The first one may be solvable by combining our techniques with existing fixed-point techniques, but certainly requires more thought:

Our construction is heavily based on a very rigid “odometric skeleton”, and our systems always have a non-trivial equicontinuous factor. This prevents many types of dynamical behaviors. In the case of \(\Z^d\) with \(d \geq 2\) one can perform the fixed-point construction without a rigid skeleton by allowing macrotiles of less rigid shapes, see e.g. westrick:tcpe?. In our lamplighter case, we have no idea how to perform a similar feat, and expect, for example, the following question to be difficult (here, fancy fixed-point tricks are not helpful, as the skeleton is already in place when we start using the fixed-point method).

For a group \(G\), we call a \(G\)-system topologically mixing if for any nonempty open sets \(U, V\), there exists a finite subset \(C \subset G\) such that \(\forall g \notin C: gU \cap V \neq \emptyset\).

Our transducer construction relies on subshifts such as \(Y\), for which we introduced \(X_{\mathrm{tree}}\); the construction would be simplified without it.

9 Implementation details for remembering single bits↩︎

9.1 Universal tileset↩︎

In this section, we describe a tileset that allows the simulation of arbitrary Turing machines. One can think of this tileset as being a “universal” (non-deterministic four-headed) Turing machine which simulates arbitrary deterministic two-headed Turing machines; universality is in quotes, because typically a universal machine simulates all machines of the same type. Though the machine is non-deterministic, it is unambiguous, meaning that every row of the tiling has a unique “successor” row above it.

In the informal descriptions, we will talk about tiles receiving and sending signals, since many of the signals can be thought of as being sent due to some event, and then triggering actions elsewhere. Formally, these signals are realized as local consistency rules, since the “computation” takes place instantaneously.

The tileset Turing machine has four heads \(A,B,C,D\); we call \(A,B\) the simulator heads, and \(C,D\) the simulated heads.

Since the tileset has to eventually be implemented on a Turing machine, and all but the lowest level of the construction will actually always be using it in encoded form, we directly work in terms of codings.

We use the alphabet \(S = (\{0,1,2\} \times \{0,1,2,3\}) \sqcup \{\texttt@,\texttt\#,\texttt\%,\texttt\$\}\), and fix an encoding of \(S\) in \(4\) bits: \((2a_1+a_0,2b_1+b_0) \in \{0,1,2\} \times \{0,1,2,3\}\) is encoded as \(a_1a_0b_1b_0\), and \((\texttt@,\texttt\#,\texttt\%,\texttt\$)\) are respectively encoded as \(1100, 1101, 1110, 1111\). We refer to elements of \(\{\texttt@,\texttt\#,\texttt\%,\texttt\$\}\) as special symbols. We also identify trits \(\texttt 0,\texttt 1,\texttt 2\) with the respective elements \((0,0),(1,0),(2,0)\) of \(S\). We strive to use teletype to represent elements of \(S\). Thus every element of \(S\) automatically has an encoding in \(S^4\), see the tag \(\langle\texttt{symbol}\rangle\)below.

We will encode by \(S^9\) the south and north colours of the universal tileset, and by \(S^{63}\) the west and east colours (in practice, these symbols come from a much smaller subalphabet). The parsing of the \(9\) symbols used as south and north colours is described by the following grammar (we roughly use Backus normal form enhanced with regular expressions and mathematical notation in this and all descriptions that follow). \[\begin{array}{l@{\texttt{ := }}l} \langle\texttt{NS colour}\rangle& \langle\texttt{phase}\rangle\;\langle\texttt{symbol}\rangle\;\langle\texttt{A}\rangle\;\langle\texttt{B}\rangle\;\langle\texttt{C}\rangle\;\langle\texttt{D}\rangle\\ \langle\texttt{bit}\rangle& \texttt 0\mid\texttt 1\\ \langle\texttt{trit}\rangle& \texttt 0\mid\texttt 1\mid\texttt 2\\ \langle\texttt{phase}\rangle& \langle\texttt{trit}\rangle\\ \langle\texttt{symbol}\rangle& \langle\texttt{bit}\rangle^4\\ \langle\texttt{A}\rangle,\langle\texttt{B}\rangle,\langle\texttt{C}\rangle,\langle\texttt{D}\rangle& \langle\texttt{bit}\rangle \end{array}\]

The interpretations are as follows: The phase trit is consistent over rows, i.e.is shared by the south colours of every tile in the same row. Each simulated computation step will consist of first taking a single step in phase \(0\), in which we read the instruction encoded on the tape, write new symbols, and move the heads; then taking one or more steps in phase \(1\) in which the simulator heads jump to the next instruction and check that this guess is correct. Phase \(2\) will be entered when a special symbol is read by the simulator head, and signifies acceptance. We will refer to the various components of the colour by the nonterminals used in the grammar, e.g.\(\langle\texttt{phase}\rangle\), \(\langle\texttt{symbol}\rangle\), etc.

We will be considering tilings of square areas of size \(2^n \times 2^n\) (eventually, this universal tileset will be used on one of the layers of a macrotile, and the \(2^n \times 2^n\) area is precisely the macrotile), and we also describe some additional constraints that should hold on the borders. We implicitly require that everything conforms to the grammars; again this is enforced by finitely many local rules.

On the tiles comprising the north border of the square area, the only constraint is that the \(\langle\texttt{phase}\rangle\)trit of the south colour must contain the symbol 2.

We now describe the constraints on the south border of a valid tiling of a \(2^n \times 2^n\) square, which are meant to begin the computation. The \(\langle\texttt{phase}\rangle\)bit is required to be 0in all the south colours on the south border. The south border \(\langle\texttt{symbol}\rangle\)s, when concatenated, form a word in \(((\texttt 0\mid\texttt 1)^4)^{2^n}\) and therefore in \(S^{2^n}\) by the prescribed encoding of \(S\); and this word should obey \(\langle\texttt{tape}\rangle\)in the following grammar, for some number \(t\) depending on the simulated tileset (and in particular not fixed): \[\begin{array}{l@{\texttt{ := }}l} \langle\texttt{tape}\rangle& \texttt@\;\langle\texttt{program}\rangle\;\texttt\%\;\langle\texttt{data}\rangle\;\texttt\$\;\texttt 2^*\\ \langle\texttt{program}\rangle& \langle\texttt{instr}\rangle\;\langle\texttt{cmd}\rangle^*\\ \langle\texttt{cmd}\rangle& \texttt\#\;\langle\texttt{id}\rangle\;(\langle\texttt{instr}\rangle\mid\langle\texttt{fail}\rangle\mid\langle\texttt{ok}\rangle)\\ \langle\texttt{id}\rangle& \langle\texttt{bit}\rangle^t\\ \langle\texttt{instr}\rangle& \langle\texttt{CDinstr}\rangle\;\langle\texttt{id}\rangle\\ \langle\texttt{CDinstr}\rangle& \langle\texttt{Cread}\rangle\;\langle\texttt{Cwrite}\rangle\;\langle\texttt{Cmove}\rangle\;\langle\texttt{Dread}\rangle\;\langle\texttt{Dwrite}\rangle\;\langle\texttt{Dmove}\rangle\\ \langle\texttt{fail}\rangle& \texttt 2\texttt 0\\ \langle\texttt{ok}\rangle& \texttt 2\texttt 1\\ \langle\texttt{Cread}\rangle,\langle\texttt{Dread}\rangle& \langle\texttt{symbol}\rangle\\ \langle\texttt{Cwrite}\rangle,\langle\texttt{Dwrite}\rangle& \langle\texttt{symbol}\rangle\\ \langle\texttt{Cmove}\rangle,\langle\texttt{Dmove}\rangle& \langle\texttt{JL}\rangle\mid\langle\texttt{ML}\rangle\mid \langle\texttt{stay}\rangle\mid \langle\texttt{MR}\rangle\mid \langle\texttt{JR}\rangle\\ \langle\texttt{JL}\rangle& \texttt 1\texttt 0\texttt 0\texttt 0\texttt 0\\ \langle\texttt{ML}\rangle& \texttt 0\texttt 1\texttt 0\texttt 0\texttt 0\\ \langle\texttt{stay}\rangle& \texttt 0\texttt 0\texttt 1\texttt 0\texttt 0\\ \langle\texttt{MR}\rangle& \texttt 0\texttt 0\texttt 0\texttt 1\texttt 0\\ \langle\texttt{JR}\rangle& \texttt 0\texttt 0\texttt 0\texttt 0\texttt 1\\ \langle\texttt{data}\rangle& (S\setminus\{\texttt@,\texttt\#,\texttt\$\})^* \text{(to be further restricted later)} \end{array}\]

The head \(A\) should start at the bottom left corner on @, \(B\) one step to the right (in the beginning of the first \(\langle\texttt{instr}\rangle\)), and heads \(C,D\) on top of the leftmost %. This just means that the \(\langle\texttt{A}\rangle\),\(\langle\texttt{B}\rangle\),\(\langle\texttt{C}\rangle\),\(\langle\texttt{D}\rangle\)bits have value 1in exactly the tiles on these positions of the tape. The tags \(\langle\texttt{JL}\rangle\), \(\langle\texttt{ML}\rangle\), \(\langle\texttt{MR}\rangle\), \(\langle\texttt{JR}\rangle\)stand for “jump left”, “move left”, “move right”, “jump right”, respectively.

We start by a high-level description of the behavior of the machine, and in this manner explain the interpretation of the \(\langle\texttt{cmd}\rangle\)expressions in \(\langle\texttt{tape}\rangle\). We use the symbol #to separate commands. Each such command contains an identifier \(\langle\texttt{id}\rangle\), which is just a bit string and serves as a unique identifier for a state of the simulated machine. The \(\langle\texttt{id}\rangle\)s should all be of the same length \(t\) (though it would suffice for correct functioning that they form a prefix code). This is followed by \(\langle\texttt{instr}\rangle\), \(\langle\texttt{fail}\rangle\)or \(\langle\texttt{ok}\rangle\). The meaning of \(\langle\texttt{fail}\rangle\)is to halt the computation (by a tiling error), while \(\langle\texttt{ok}\rangle\)initiates phase \(2\). The more interesting (and typical) instruction is \(\langle\texttt{instr}\rangle\). Here, in state \(0\) the west and east colours should memorize \(\langle\texttt{CDinstr}\rangle\), check it against the \(\langle\texttt{symbol}\rangle\)s that the heads \(C,D\) are seeing, and rewrite the symbols and move the heads according to these instructions (we do all of this in a single row), continuing with the new \(\langle\texttt{id}\rangle\)identifier. The meaning of \(\langle\texttt{ML}\rangle\), \(\langle\texttt{stay}\rangle\)and \(\langle\texttt{MR}\rangle\)is to move the head by \(-1,0,1\) respectively. The meaning of \(\langle\texttt{JL}\rangle\)and \(\langle\texttt{JR}\rangle\)is that the head directly jumps to the nearest special symbol in the direction stated.

The behavior of the heads \(A,B\) is as follows. At the beginning of phase \(0\), the head \(B\) should be standing on the symbol of some \(\langle\texttt{cmd}\rangle\)immediately to the right of the #\(\langle\texttt{id}\rangle\)part, except in the very beginning, when it is on the first \(\langle\texttt{instr}\rangle\); this is in fact just a hack to get the computation started. The sweep reading \(\langle\texttt{CDinstr}\rangle\)should drop the \(A\) head at the start of the \(\langle\texttt{id}\rangle\)to the right of \(\langle\texttt{CDinstr}\rangle\). The \(A\) and \(B\) heads that were in the south colours when entering phase \(0\) simply disappear (or one may think that \(A\) “jumps” over \(\langle\texttt{CDinstr}\rangle\); new \(B\)s will be born non-deterministically). Phase \(0\) always takes just one step, and the next phase after phase \(0\) is always \(1\). In the beginning of phase \(1\), any number of \(B\) heads appear to the right of #-symbols. In the beginning of phase 1, we should then have the \(A\) head at the beginning of some \(\langle\texttt{id}\rangle\)at the end of an \(\langle\texttt{instr}\rangle\), and should have any number of \(B\) heads on the tape. We will now check, using the west and east colours, that there is in fact exactly one \(B\) head on the row (barring a tiling error), and that the \(\langle\texttt{id}\rangle\)it reads at the beginning of the \(\langle\texttt{cmd}\rangle\)is precisely the \(\langle\texttt{id}\rangle\)read by \(A\). This takes exactly \(t\) steps. Note that there is no marker that tells us when we are done in the \(\langle\texttt{cmd}\rangle\); we do not need one because the \(A\) head knows the \(\langle\texttt{id}\rangle\)is over when it hits a special symbol. (All the \(\langle\texttt{id}\rangle\)s are of the same length \(t\), but our tileset cannot not know what this \(t\) is, as we are describing a fixed tileset.)

After phase \(1\) (meaning \(A\) is about to move to a special symbol) we enter phase \(0\) (if we guess the computation continues) or phase \(2\). In the latter case, we check that there is an \(\langle\texttt{ok}\rangle\)on the tape at the \(B\) head, and we simply stay in phase \(2\) until the end of the computation. There is no special behavior to account for encountering a \(\langle\texttt{fail}\rangle\), so encountering it leads to a tiling error (as desired). (We could alternatively simply enter a loop, and thus hit the north border without being in state \(2\).)

We now explain the west and east colours in more detail, and the rules that govern them. This will also make some of the statements from the previous paragraphs more precise. The west and east colours follow the following grammar:

\[\begin{array}{l@{\texttt{ := }}l} \langle\texttt{WE colour}\rangle& \texttt 0\;\langle\texttt{phase 0}\rangle\mid \texttt 1\;\langle\texttt{phase 1}\rangle\mid \texttt 2\;\langle\texttt{phase 2}\rangle\\ \langle\texttt{phase 0}\rangle& \langle\texttt{tinstr}\rangle\;\langle\texttt{ginstr}\rangle\;\langle\texttt{C mvsig}\rangle\;\langle\texttt{D mvsig}\rangle\;\langle\texttt{A birth}\rangle\;\langle\texttt{B birth}\rangle\\ \langle\texttt{ginstr}\rangle& \langle\texttt{CDinstr}\rangle\\ \langle\texttt{tinstr}\rangle& ((\langle\texttt{bit}\rangle^*\;\texttt 2^+)\cap\langle\texttt{trit}\rangle^{26})\mid\langle\texttt{CDinstr}\rangle\\ \langle\texttt{A birth}\rangle& \langle\texttt{bit}\rangle\\ \langle\texttt{B birth}\rangle& \langle\texttt{bit}\rangle\\ \langle\texttt{C mvsig}\rangle& \langle\texttt{bit}\rangle^4\\ \langle\texttt{D mvsig}\rangle& \langle\texttt{bit}\rangle^4\\ \langle\texttt{phase 1}\rangle& \langle\texttt{trit}\rangle^2\;\langle\texttt{A birth}\rangle\;\langle\texttt{B birth}\rangle\;\texttt 2^{58}\\ \langle\texttt{phase 2}\rangle& \langle\texttt{trit}\rangle\;\texttt 2^{61} \end{array}\] Here, \(\langle\texttt{ginstr}\rangle\), \(\langle\texttt{tinstr}\rangle\)stand respectively for “guessed instruction” and “true instruction”, \(\langle\texttt{C mvsig}\rangle\)stands for “\(C\) movement signal”. Note that we reuse some nonterminals from the previous grammars.

The first symbol of the colour tells us the phase, and the first constraint is that it matches the phase in the south symbol.

Let us start by explaining the constraints of phase \(2\), which is the easiest. Here, we suppose that \(B\) is standing on top of an \(\langle\texttt{ok}\rangle= \texttt 2\texttt 1\) (if \(B\) is on a bit, we should be in phase \(0\)). We should thus check that the symbol under \(B\) is 2, and we should check that the next symbol is 1. This is checked using the first trit of \(\langle\texttt{phase 2}\rangle\): on the west border we require that this first trit is 2. In a cell with \(B\) in it (i.e.with \(\langle\texttt{B}\rangle= \texttt 1\) in the south colour) we check that it receives 2from the west, has 2as the tape symbol (i.e. we have \(\langle\texttt{symbol}\rangle=\texttt{1000}\) in the south colour), and sends 1to the east. We check that a cell receiving 1from the west has no \(B\), has 1as tape symbol in the south colour, and sends 0to the east. Cells receiving 0from the west must not contain \(B\)-heads. We check that any cell receiving 2or 0from the west just sends it to the east if \(B\) is not in the cell. At the east end we check that the trit is 0. As for the south and north colours, we copy all the rest of the content verbatim. We also check that head \(A\) is on a special symbol (though this is not strictly necessary for correct functioning).

It clearly follows that we can tile a row in phase \(2\) if and only if there is a unique \(B\)-head, and it is standing on the leftmost symbol of a 2``1-subword. Other phases will fail in such a situation (as we see below) so we must then preserve the phase, and in fact copy this row until the northmost row (where there are no forbidden patterns, since the north border accepts rows in phase \(2\)). Note that we check for phase \(2\) on the south border of the northmost row, so that there is at least one row that checks the \(B\)-on-a-2``1constraint and we are not just non-deterministically sending a phase \(2\) signal to the north at the last minute.

We now proceed to phase \(1\). Here the first two bits are used to compare what the \(A\) and \(B\) heads are seeing. The \(\langle\texttt{A birth}\rangle\)and \(\langle\texttt{B birth}\rangle\)signals are used to give birth to a new head. On the west end, we require 2``2in the first two trits, and 0``0in \(\langle\texttt{A birth}\rangle\) \(\langle\texttt{B birth}\rangle\). At a cell containing the head \(A\), we check that the first trit is 2and change it to the bit coded in the \(\langle\texttt{symbol}\rangle\)in the south colour (and we check that it is indeed a bit). The \(\langle\texttt{A birth}\rangle\)bit in the east colour is 1if and only if we have \(A\) in this cell. At a cell containing \(B\) we do the same but for the second trit. Cells that receive the \(\langle\texttt{A birth}\rangle\)or \(\langle\texttt{B birth}\rangle\)signal from the west will send an \(A\) or \(B\) head to the north. Finally, at the east end we check that the first two trits are 0``0or 1``1.

It is clear that we we can tile a row in phase \(1\) if and only if \(A,B\) are on equal bits (and there is exactly one head of each type), and in the row above we will have \(A\) and \(B\) heads entering the cells one step to the right. As for the south and north colours, cells not receiving \(\langle\texttt{A birth}\rangle\)or \(\langle\texttt{B birth}\rangle\)from the west will send no \(A,B\) heads north. Heads \(C,D\) are just copied directly, and so are all tape symbols. The next row can be in any phase (though only one guess will succeed), so we make no requirements on the north phase bits.

In phase \(0\), which is the most complicated one, we check that \(A\) is on a special symbol, \(B\) is on a bit, and we read the instruction to the right of \(B\), and according to this instruction, read and write with \(C,D\) and change the tape. More precisely, we have the following constraints. On the west end, \(\langle\texttt{tinstr}\rangle\)must contain \(\texttt 2^{26}\), \(\langle\texttt{Cmove}\rangle\)and \(\langle\texttt{Dmove}\rangle\)must both contain 0000, \(\langle\texttt{A birth}\rangle\), \(\langle\texttt{B birth}\rangle\)must both contain 0(intuitively meaning, no heads come from, or enter, the non-existing cell to the left of the leftmost one).

While we have \(\texttt 2^{26}\) in \(\langle\texttt{tinstr}\rangle\), we simply copy it from west to east. When we encounter \(B\), we start reading bits from the current south \(\langle\texttt{symbol}\rangle\)(checking they are indeed bits), always writing them on the leftmost 2in \(\langle\texttt{tinstr}\rangle\)before sending the adjusted colour to the east. When we rewrite the last 2to a bit, we have successfully read a \(\langle\texttt{CDinstr}\rangle\)from the tape and we send an \(\langle\texttt{A birth}\rangle\)signal to the east (i.e.set \(\langle\texttt{A birth}\rangle= 1\) on the east colour). Once \(\langle\texttt{tinstr}\rangle\)contains no 2s, we again simply copy it from west to east on each step. Also, we check that once \(\langle\texttt{tinstr}\rangle\)is no longer \(\texttt 2^{26}\) we do not see any \(B\) heads. On the east end we check \(\langle\texttt{tinstr}\rangle= \langle\texttt{ginstr}\rangle\). If head \(C\) (respectively \(D\)) is present, we check that the \(\langle\texttt{symbol}\rangle\)on the south colour is equal to \(\langle\texttt{Cread}\rangle\)(respectively \(\langle\texttt{Dread}\rangle\)); if not, we produce a tiling error. We may (but don’t have to) send \(\langle\texttt{B birth}\rangle\)signals to the east from any cell with south \(\langle\texttt{symbol}\rangle\) equal to #, i.e.we only impose \(\langle\texttt{B birth}\rangle=0\) when the south \(\langle\texttt{symbol}\rangle\)is not #.

In the north and south directions, we by default simply copy the current tape symbol from south to north, except if \(C\) or \(D\) is present; we then instead write the symbol in \(\langle\texttt{Cwrite}\rangle\)and/or \(\langle\texttt{Dwrite}\rangle\)(and if both \(C\) and \(D\) are present and require conflicting writes we trigger a tiling error). We introduce \(A\) and/or \(B\) if and only if \(\langle\texttt{A birth}\rangle\)and/or \(\langle\texttt{B birth}\rangle\)is present on the west. As for \(C,D\), we do the same. We send a \(C\) north if and only if there is a \(C\) head in the current cell and \(\langle\texttt{Cmove}\rangle\)of \(\langle\texttt{ginstr}\rangle\)contains 00100 (the stay command); or there is no \(C\), but there is a 0010 in \(\langle\texttt{C mvsig}\rangle\)meaning “move right”, coming in from the west; or there is no \(C\), but there is a 0100 in \(\langle\texttt{C mvsig}\rangle\)meaning “move left”, coming in from the east; or 0001 meaning “jump right” (respectively 1000 meaning “jump left”) in \(\langle\texttt{C mvsig}\rangle\)on the west (respectively east) and the current cell contains a special symbol. If there is no special symbol, we just propagate the signals 1000 or 0001 forward, checking that west and east contents agree.

This concludes the high-level (but complete) description of the tileset. We now explain how to use the tileset to perform universal computation of any deterministic two-headed Turing machine (one can also perform non-deterministic computation with this tileset, but we do not, and the claims about unambiguity of course need not be correct if we do).

The machines we simulate have two heads (\(C,D\)) which cannot sense each other’s presence directly, but have shared state, and can also accept or fail by moving to a special state. They can read the tape content and rewrite it (under the cell), move around, and jump to the next or previous special symbol. If the machine to be simulated has \(k\) states, we pick \(t = \lceil \log k \rceil\) and pick a binary string of length \(t\) for each state. After the initial @-symbol, let us agree to put an instruction of the form ‘\(\texttt{1110} \; \texttt{1110} \; \texttt{00100} \; \texttt{1110} \; \texttt{1110} \; \texttt{00100} \; \texttt 0^t\)’, where \(\texttt 0^t\) is the identification of the initial state; this means that, when it is booted, the machine checks that heads \(C,D\) are above a %and starts at state \(\texttt 0^t\). Then, for each transition (in the machine to be simulated) from state \(q\) to state \(q'\) where head \(C\) reads symbol \(r\), head \(D\) reads symbol \(r'\), the heads write \(w,w'\) respectively, and the move instructions (stays, moves or jumps) are \(j, j'\), we include \[\label{eq:cmd} \texttt\#\;[q]\;[r]\;[w]\;[j]\;[r']\;[w']\;[j']\;[q']\tag{7}\] as one of the \(\langle\texttt{cmd}\rangle\)s in \(\langle\texttt{tape}\rangle\), where the brackets denote the natural encoding in the grammar of \(\langle\texttt{tape}\rangle\), namely \(j\in\langle\texttt{Cmove}\rangle\), \(j'\in\langle\texttt{Dmove}\rangle\), etc. For an accept state, we use an ‘#\(\langle\texttt{ok}\rangle\)’ type \(\langle\texttt{cmd}\rangle\). To fail, we can similarly use ‘#``0’, or we can simply not simulate the transition at all; both choices lead to a tiling error.

9.2 The fixed-point construction in detail↩︎

We list some conventions we follow and numerical choices:

• For simplicity we assume that the simulated subshift \(X\) is over binary alphabet.

• The responsibility zones of macrotiles of level \(k\) are of length \(2^k\) and the \(i\)th tile is responsible for the \(\lfloor i/2^k \rfloor\)th such zone, which of course corresponds to a natural \({\mathcal{H}}_k\)-block. In this manner, many tiles are responsible for the same block, but this leads to particularly simple calculations.

• Instead of a computation zone at the center, we simply start the computation at the south border of the macrotile, and the entire macrotile is used as a computation area.

• The neighbour colours are stored to the right of the program (starting after the first %symbol), in order \(N,S,W,E\) or \(S,N,W,E\) depending on the parity of the y-coördinate of the position of the macrotile in its parent. (The first thing we will do in our program is to swap these back in software if the y-coördinate is odd, after which the order is always \(N,S,W,E\).)

• Tiles will be referred to as macrotiles of level \(0\). For \(k>0\), macrotiles of level \(k\) will consist of \(2^{n_k}\) tiles of level \(k-1\), with \(n_k = 4^{k + c}\) for a suitable constant \(c\). We expect \(c = 1\) to suffice, meaning macrotiles of level \(1\) already have side length \(65536\). The actual size of the macrotile of level \(k\) (measured in macrotiles of level \(0\)) is \(L_k = \prod_{1\leq i \leq k} 2^{4^{i+c}} \leq 2^{4^{k+1+c}}\), meaning there are more macrotiles of level \(k\) in a macrotile of level \(k+1\) than there are tiles in a macrotile of level \(k\). Note that \(L_k\) is a power of \(2\), so a macrotile is of the shape \({\mathcal{H}}_\ell \times {\mathcal{V}}_\ell\) for some \(\ell\).

• We define \(t_k = 4^{k + 4 + c}\); this will be used as the length of “packets” exchanged between macrotiles.

• We assume that the uniquely decodable substitution \(\tau\colon A \to A^2\) has \(\#A=2\), so elements of \(A \times A\), encoding \({\mathcal{V}}\) and \({\mathcal{H}}\) configurations of \(\tau\), can be conveniently encoded as \(\langle\texttt{symbol}\rangle\)s in \((\texttt 0\mid\texttt 1)^4\).

• Great care is taken so that computations are done in tiny morsels; in particular, each cell only takes care of a small part of the checking.

The macrotile of level \(k\) consists of macrotiles of level \(k-1\). The macrotiles of level \(k-1\) should be thought of as a tileset with two layers. From the point of view of level \(k\), its level-\((k-1)\) macrotiles come from a tileset of constant size, but with complex rules governing the allowed patterns. At level \(1\), this is simply enforced by SFT rules, but in general the job of the \((k-1)\)-macrotiles is to ensure the correct structure on level \(k\). The first layer of a level-\((k-1)\) macrotile simulates a tile of the universal tileset from the previous section, and the second carries individual symbols along “wires”.

We are ready to explain how we program the universal Turing machine of the previous section. The data portion in the south colours of the \((k-1)\)-macrotiles on the southmost row of a \(k\)-macrotile is split into a fixed number (\(4\cdot9+10=46\)) of %-separated tritfields. They are of the following form, with the number of 2’s at the end of \(\langle\texttt{tape}\rangle\)adjusted so the total length of the expression is \(2^{n_k}\), and the number of 2’s at the end of \(\langle\texttt{packet}\rangle\)adjusted so the total length of the packet is \(t_k\): \[\begin{array}{l@{\texttt{ := }}l} \langle\texttt{data}\rangle& \begin{array}[t]{l} \langle\texttt{NSWE}\rangle\;\texttt\%\;\langle\texttt{k}\rangle\;\texttt\%\;\langle\texttt{c}\rangle\;\texttt\%\;\langle\texttt{pos}\rangle\;\texttt\%\;\langle\texttt{ppos}\rangle\\ \texttt\%\;\langle\texttt{word}\rangle\;\texttt\%\;\langle\texttt{pword}\rangle\;\texttt\%\;\langle\texttt{subst}\rangle\;\texttt\%\;\langle\texttt{psubst}\rangle \end{array}\\ \langle\texttt{NSWE}\rangle& \langle\texttt{N}\rangle\;\texttt\%\;\langle\texttt{S}\rangle\;\texttt\%\;\langle\texttt{W}\rangle\;\texttt\%\;\langle\texttt{E}\rangle\\ \langle\texttt{N}\rangle,\langle\texttt{S}\rangle,\langle\texttt{W}\rangle,\langle\texttt{E}\rangle& \langle\texttt{packet}\rangle\cap S^{t_k}\\ \langle\texttt{k}\rangle& \texttt 0^k\\ \langle\texttt{c}\rangle& \texttt 0^c\\ \langle\texttt{pos}\rangle& \langle\texttt{xpos}\rangle\;\texttt\%\;\langle\texttt{ypos}\rangle\\ \langle\texttt{xpos}\rangle,\langle\texttt{ypos}\rangle& (\texttt 0\mid\texttt 1)^{4^{k+1+c}}\\ \langle\texttt{ppos}\rangle& \langle\texttt{pxpos}\rangle\;\texttt\%\;\langle\texttt{pypos}\rangle\\ \langle\texttt{pxpos}\rangle,\langle\texttt{pypos}\rangle& (\texttt 0\mid\texttt 1)^{4^{k+2+c}}\\ \langle\texttt{word}\rangle& (\texttt 0\mid\texttt 1)^{2^k}\mid \texttt 2^{2^k}\\ \langle\texttt{pword}\rangle& (\texttt 0\mid\texttt 1)^{2^{k+1}}\mid \texttt 2^{2^{k+1}}\\ \langle\texttt{subst}\rangle,\langle\texttt{psubst}\rangle& \langle\texttt{symbol}\rangle\\ \langle\texttt{packet}\rangle& \langle\texttt{pword}\rangle\;\texttt\%\;\langle\texttt{pos}\rangle\;\texttt\%\;\langle\texttt{ppos}\rangle\;\texttt\%\;\langle\texttt{wire}\rangle\;\texttt\%\;\langle\texttt{simu}\rangle\;\texttt\%\;\langle\texttt{psubst}\rangle\;\texttt\%\;\texttt 2^*\\ \langle\texttt{wire}\rangle& (\texttt 0\mid\texttt 1\mid\texttt 2)^4\\ \langle\texttt{simu}\rangle& \langle\texttt{NS colour}\rangle\;\texttt 2^{54}\mid \langle\texttt{WE colour}\rangle \end{array}\]

Here \(\langle\texttt{ppos}\rangle\), \(\langle\texttt{pword}\rangle\)refer to the position and word of a macrotile’s parent (one level higher). The “beams” or “packets” sent along the \(\langle\texttt{packet}\rangle\)regions are of great importance, and will be detailed later. If a beam points to outside of a macrotile, \(\langle\texttt{pword}\rangle\)is simply the \(0\)-word. \(\langle\texttt{simu}\rangle\)serves to simulate the universal tileset, by propagating \(\langle\texttt{NS colour}\rangle\)or \(\langle\texttt{WE colour}\rangle\)which follows the grammar of the previous section.

We turn to the program \(\langle\texttt{program}\rangle\)to be run on our universal Turing machine, ultimately a list of \(\langle\texttt{cmd}\rangle\)as in 7 , namely the transcription of a two-headed deterministic Turing machine into the format understood by the universal tileset. Instead of giving the transitions, we explain the (many, easy) feats that the Turing machine must perform. Our task is to write a program that checks that, if every level-\(k\) macrotile executes correctly \(\langle\texttt{program}\rangle\)according to its position \(\langle\texttt{pos}\rangle\), then every level-\((k+1)\) macrotile also follows \(\langle\texttt{program}\rangle\), and its data is consistent with its children in the obvious way (the \(k\)-level macrotiles directly contain some information about the parent, such as the parent word \(\langle\texttt{pword}\rangle\), and we simply check the consistency of these).

This is at the heart of the self-reference we wish to implement: the program and data are encoded in the \(\langle\texttt{symbol}\rangle\)fields of the south border of each level-\(k\) macrotile, namely words in \(S^*\). Each macrotile also behaves as a single tile, and has in each (N,S,W,E) direction a “beam”, which contains in particular a symbol (its \(\langle\texttt{wire}\rangle\))

First, the Turing machine will swap the north and south neighbour data beams if the vertical position \(\langle\texttt{ypos}\rangle\)is odd. This (like everything else) is easy enough that one can directly describe how the simulated two-headed Turing machine does it: we use \(32\) right jumps to get \(D\) to the %-symbol just after \(\langle\texttt{pos}\rangle\), then move one step backwards to read its parity, and branch to different states of the Turing machine. If the parity is even, we jump \(C\) and \(D\) leftwards (again through a fixed number of %s) to get back to the initial symbol. Otherwise, we jump \(C\) and \(D\) leftwards (still a fixed number of %s) to the beginnings of the \(\langle\texttt{S}\rangle\)beam and \(\langle\texttt{N}\rangle\)beam, respectively, and then have both heads step right. Now, in a single sweep over these areas, we can swap their contents using our two heads.

Next, we perform a sequence of consistency checks. First of all, we check that in the \(\langle\texttt{simu}\rangle\)areas of all packets we have an element of the universal tileset. This means that our Turing machine must check the logic described in the previous section. If the \(\langle\texttt{pos}\rangle\)of our macrotile is on one of the borders, we also check the border conditions for the tiles of the universal tileset. This is just a finite list of conditions, which was implicitly listed in the previous section. We describe some of the details involved in the above paragraphs. First of all, we must be able to check whether we are on a boundary; for this we must check whether the \(\langle\texttt{xpos}\rangle\)(respectively \(\langle\texttt{ypos}\rangle\)) of our own data is equal to \(0\) or to \(2^{n_{k+1}} - 1 = 2^{4^{k+1+c}} - 1\), as the present macrotile of level \(k\) is a cell in a level \(k+1\) macrotile which is of size \(2^{4^{k+1+c}}\). This amounts to checking if the word \(\langle\texttt{xpos}\rangle\)(respectively \(\langle\texttt{ypos}\rangle\)) equals \(\texttt 0^{4^{k+1+c}}\) or \(\texttt 1^{4^{k+1+c}}\).

On the boundaries we perform some constant number of checks. The only difficulty is the south border, where the checks refer to specific positions of the heads. We check that \(\langle\texttt{phase}\rangle= \texttt 0\) (easy), that \(A\) is present (in the packet \(\langle\texttt{S}\rangle\)) if and only if \(\langle\texttt{xpos}\rangle= 0\), that \(B\) is present if and only if \(\langle\texttt{xpos}\rangle= 1\), and that \(C,D\) are present if and only if we are on the first %. We will (below) ensure that the program is the same, so it is easy to figure out where the %is, just having \(C\) walk along the program and increment a counter with \(D\), and check if this counter value is \(\langle\texttt{xpos}\rangle\)when \(C\) reaches %. Note that we can have \(D\) write the counter directly on top of the \(\langle\texttt{xpos}\rangle\)area, since our alphabet is \(\{0,1,2\} \times \{0,1,2,3\}\), so it is easy to compare these numbers. (It is in such places that it is convenient to have a second component in \(S\), giving us effectively a scratch area along every field of \(\langle\texttt{data}\rangle\)).

We are now ready to discuss the fixed-point part of the construction. What the macrotiles of level \(k\) need to ensure is that the the data on the south row in \(\langle\texttt{simu}\rangle\)in the macrotile of level \(k+1\) is as expected, and wire bits are propagated correctly. Then the next macrotile will also be sending information correctly and performing the calculations on the correct data, and we get by induction that all levels work similarly. We start with \(\langle\texttt{simu}\rangle\). Let us describe things checked on the south border, namely what the level \(k\) macrotile checks about the symbols in its south beam \(\langle\texttt{S}\rangle\)in case \(\langle\texttt{ypos}\rangle= 0\). We describe the checks in order from left to right.

We can check that the program is correct in the same way as we checked for the %-symbol after it when placing \(C,D\): while walking along the program with \(C\), if the counter incremented by \(D\) hits the value in \(\langle\texttt{xpos}\rangle\), we check that the south packet has the same symbol on the tape as \(C\) is reading. The symbols that are part of the program are nothing special, so \(C\) can read them just fine, and it is easy to locate \(\langle\texttt{simu}\rangle\)of the south packet for comparison. (This is sometimes called the “magic trick” of the fixed-point argument.) Also, we check that if we are on the position exactly after the program (where we enforced \(C,D\) already), then the symbol is indeed %.

If \(\langle\texttt{xpos}\rangle\)belongs to the \(\langle\texttt{NSWE}\rangle\)area of the next macrotile, we just check that the symbols belong to \(\{\texttt 0,\texttt 1,\texttt 2,\texttt\%\}\), and %’s appear in the correct positions. (There are many consistency checks on the values, but these are checked by the macrotile of level \(k+1\), as described later, so the macrotiles of level \(k\) need not worry about them.) To go over this area and perform the checks, we must increment our counter by \(4t_{k+1} + 4\). It is easy to increment a scratch binary counter (stored using the second component of \(S\) within \(\langle\texttt{xpos}\rangle\)) by \(t_{k+1} = 4^{k + 4 + c} = 2^{2k+2c+8}\): simply use one head to walk over the \(\langle\texttt{k}\rangle\)and \(\langle\texttt{c}\rangle\)areas twice, then perform \(8\) more steps, and then add \(1\). Each time the binary counter is incremented, check that if it equals \(\langle\texttt{xpos}\rangle\)then the symbol in the south colour is %, and otherwise it is a trit.

We then check that the parent \(\langle\texttt{k}\rangle\)and \(\langle\texttt{c}\rangle\)values are correct, namely \(\text{parent}\langle\texttt{k}\rangle= k+1\) and \(\text{parent}\langle\texttt{c}\rangle= c\). For this, beginning with the counter value we already have on \(\langle\texttt{xpos}\rangle\)(which should be where the \(\langle\texttt{k}\rangle\)-area begins in the parent tile) we have the \(C\) head walk on the tape over \(\langle\texttt{k}\rangle\)while incrementing the counter. At the end we take one extra step to increase by one the \(\langle\texttt{k}\rangle\)-value in the parent tile. Then we do the same with \(\langle\texttt{c}\rangle\). Again if the counter value equals \(\langle\texttt{xpos}\rangle\)then we check we have the correct value 0or %in the \(\langle\texttt{symbol}\rangle\)of \(\langle\texttt{simu}\rangle\)of \(\langle\texttt{S}\rangle\).

Next we check that that the parent’s own position on tape is correct. If \(\langle\texttt{xpos}\rangle\)represents a bit string in this area, we simply check this bit string against \(\langle\texttt{data}\rangle\).\(\langle\texttt{ppos}\rangle\). (The operator \(.\) refers to indexing parts of a field, so this means the \(\langle\texttt{ppos}\rangle\)-component inside the \(\langle\texttt{data}\rangle\) field.) What this means in practice is that we increment the counter while walking with \(C\) on \(\langle\texttt{data}\rangle\).\(\langle\texttt{ppos}\rangle\), and if the counter equals \(\langle\texttt{xpos}\rangle\)then we check that \(\langle\texttt{S}\rangle\).\(\langle\texttt{simu}\rangle\).\(\langle\texttt{symbol}\rangle\)has the same bit as our \(\langle\texttt{data}\rangle\).\(\langle\texttt{ppos}\rangle\). Next we skip over the parent.\(\langle\texttt{ppos}\rangle\)area (by incrementing the counter by \(4^{k+c+2}\)), as we have no idea what its value should be, and only check that if \(\langle\texttt{xpos}\rangle\)is in this area, the symbol is a bit, except at the exact middle where it must be an %.

Next we similarly check the parent’s \(\langle\texttt{word}\rangle\), namely compare it with \(\langle\texttt{pword}\rangle\). Then we check parent.\(\langle\texttt{subst}\rangle\)against \(\langle\texttt{psubst}\rangle\). For parent.\(\langle\texttt{pword}\rangle\)and parent.\(\langle\texttt{psubst}\rangle\)again we only check the alphabet constraints.

We then check that at the end we have a $symbol and then only 2s. This is straightforward, we just scan for (the encoding of) $in \(\langle\texttt{S}\rangle\).\(\langle\texttt{simu}\rangle\).\(\langle\texttt{symbol}\rangle\)if \(\langle\texttt{xpos}\rangle\)’s value is exactly the expected length of \(\langle\texttt{data}\rangle\)of the parent, and if it is larger, we check that the symbol encoded is 2.

We then check that the data in the beams \(\langle\texttt{NSWE}\rangle\)is consistent with the data in \(\langle\texttt{data}\rangle\). First we check that \[\langle\texttt{E}\rangle.\langle\texttt{pos}\rangle= \langle\texttt{N}\rangle.\langle\texttt{pos}\rangle= \langle\texttt{data}\rangle.\langle\texttt{pos}\rangle\equiv \langle\texttt{W}\rangle.\langle\texttt{pos}\rangle+1 = \langle\texttt{S}\rangle.\langle\texttt{pos}\rangle+1\pmod{2^{n_{k+1}}}.\] We then check \(\langle\texttt{I}\rangle.\langle\texttt{ppos}\rangle= \langle\texttt{data}\rangle.\langle\texttt{ppos}\rangle\) if \(I \in \{\texttt N,\texttt S,\texttt W,\texttt E\}\) is an edge that is not on the boundary of the macrotile. We do the same for \(\langle\texttt{psubst}\rangle\), and finally check that after all these entries there are only trailing 2s.

The only non-trivial part to check about the \(\langle\texttt{NSWE}\rangle\)beams is that \(\langle\texttt{wire}\rangle\)contents are correct. What makes this non-trivial is that the wires make some turns, and we have to figure out whether the current macrotile is part of a wire or not. We follow the picture below (note that each macrotile checks that its parent looks like this, by routing according to its position in this picture) when \(\langle\texttt{pypos}\rangle\)is even; when \(\langle\texttt{pypos}\rangle\)is odd, the beam that goes up is from the \(\langle\texttt{S}\rangle\)zone.

We now explain the arithmetic of making these signals move correctly. There are of course many alternative ways of routing the signals, but the one we chose has the advantage of being easy to implement in linear time. The following rules ensure that the \(\langle\texttt{wire}\rangle\)symbol is either the correct one transmitted along a wire, or 2222 to indicate “no wire”.

First, let us attach the ends of wires correctly. We assume \(\langle\texttt{ypos}\rangle= 0\). Suppose first that \(\langle\texttt{pypos}\rangle\)is even. If \(\langle\texttt{xpos}\rangle\)points to the parent.\(\langle\texttt{N}\rangle\)area (which we already know how to check) then our north packet’s \(\langle\texttt{wire}\rangle\)bit should be equal to the \(\langle\texttt{simu}\rangle\).\(\langle\texttt{symbol}\rangle\)of the south packet, and the south wire symbol should be 2222. If \(\langle\texttt{xpos}\rangle\)points to the parent.\(\langle\texttt{S}\rangle\)area then instead the south wire symbol should equal the south colour’s \(\langle\texttt{simu}\rangle\).\(\langle\texttt{symbol}\rangle\)and the north wire symbol should be 2222. On the west and east, we copy data to the north wire bits. If \(\langle\texttt{xpos}\rangle\)points somewhere else and \(\langle\texttt{ypos}\rangle= 0\), then the north and south wire bits carry 2222. If \(\langle\texttt{pypos}\rangle\)is odd we do the same but with the roles of north and south exchanged.

We then propagate the data along the wires, and make sure that there is no additional information passed on edges not part of wires (otherwise our extension would have additional entropy). If \(\langle\texttt{ypos}\rangle>0\) and \(\langle\texttt{xpos}\rangle\)is not in the parent.\(\langle\texttt{W}\rangle\)or parent.\(\langle\texttt{E}\rangle\)areas, then we just check that the north and south bits agree. For the west beam, if \(\langle\texttt{xpos}\rangle\)is in the parent.\(\langle\texttt{W}\rangle\)area, we compute \(h = \langle\texttt{xpos}\rangle- \text{parent}.\langle\texttt{W}\rangle.\text{start}\), namely how far \(\langle\texttt{xpos}\rangle\)is within the parent.\(\langle\texttt{W}\rangle\)area. If \(\langle\texttt{pypos}\rangle<h\) then we copy the south wire symbol to north, and send 2222 west and east. If \(\langle\texttt{pypos}\rangle= h\) then we copy south to west and send 2222 north and east. If \(h < \langle\texttt{pypos}\rangle< t_{k+2}\) then we copy east to west and send 2222 south and north. If \(\langle\texttt{pypos}\rangle\geq t_{k+1}\) then we send 2222 in all four directions. For the east beam, the same calculation is performed but pointing in the east direction.

We next check that the substitution is correctly implemented, namely that \(\langle\texttt{data}\rangle\).\(\langle\texttt{subst}\rangle\)is consistent with \(\langle\texttt{data}\rangle\).\(\langle\texttt{psubst}\rangle\). For this we have to actually compute the \(n_{k+1}\)th power of the substitution on \(\langle\texttt{psubst}\rangle\), and check that our \(\langle\texttt{subst}\rangle\)is indeed what is expected in the \(\langle\texttt{pos}\rangle\)position of \(\tau^{n_{k+1}}(\langle\texttt{psubst}\rangle)\). In practice, we memorize \(\langle\texttt{psubst}\rangle\)in a state of our Turing machine, and put heads \(C,D\) respectively at the beginnings of \(\langle\texttt{xpos}\rangle\)and \(\langle\texttt{ypos}\rangle\)by using a constant number of jumps. Each time both heads read a symbol we know which of the four quadrants we stepped into, and we can deduce the substituted symbol. In this manner, after a single sweep over \(\langle\texttt{xpos}\rangle\)and \(\langle\texttt{ypos}\rangle\)we know what the \(\langle\texttt{subst}\rangle\)symbol should be.

Finally, we make sure that all macrotiles have access to the same word in the subshift \(X\) under consideration; this means that \(\langle\texttt{word}\rangle\)should be consistent with \(\langle\texttt{pword}\rangle\). For this, let us introduce the notation \(\lfloor m\rfloor_k\) for the integer \(\lfloor m/2^k\rfloor2^k=m-(m\%2^k)\); in binary, this is obtained from the representation of \(m\) by clearing its lowest \(k\) bits. The present tile’s \(\langle\texttt{word}\rangle\)contains by induction the symbols in the columns in the interval \([\lfloor\langle\texttt{ypos}\rangle\rfloor_k,\lfloor\langle\texttt{ypos}\rangle+1\rfloor_k[\) counting from the left border (along level-\(0\) tiles of course), if this interval fits inside the tile. Otherwise we are not responsible for anything and simply require that \(\langle\texttt{word}\rangle\)is a string of 2s. Similarly the parent is responsible for the columns \([\lfloor\langle\texttt{pypos}\rangle\rfloor_{k+1},\lfloor\langle\texttt{pypos}\rangle+1\rfloor_{k+1}[\) inside itself. We first translate our interval to the parent level by adding \(L_k\langle\texttt{xpos}\rangle\), recalling that \(L_k = \prod_{1\leq i \leq k} 2^{4^{i+c}} \leq 2^{4^{k+1+c}}\) is the size of the present macrotile. This number is very easy to construct: we simply run a \(4\)-ary counter on the \(\langle\texttt{k}\rangle\;\texttt\%\;\langle\texttt{c}\rangle\) area with one head while moving the other head left, and whenever we detect a new carry, we add a bit in that position (and propagate a possible carry).

In practice, since the responsibility zones on our level are delimited by multiples by \(2^k\) and those on the parent level by multiples of \(2^{k+1}\), we just need to check whether \(L_k\langle\texttt{xpos}\rangle+\lfloor\langle\texttt{ypos}\rangle\rfloor_k=\lfloor\langle\texttt{pypos}\rangle\rfloor_{k+1}\) or \(L_k\langle\texttt{xpos}\rangle+ \lfloor\langle\texttt{ypos}\rangle+1\rfloor_k = \lfloor\langle\texttt{pypos}\rangle+1\rfloor_{k+1}\), both of which are straightforward. To detect the former condition, we check whether \(\langle\texttt{word}\rangle\)equals the left half of \(\langle\texttt{pword}\rangle\), and to detect the latter, we check whether \(\langle\texttt{word}\rangle\)equals the right half of \(\langle\texttt{pword}\rangle\).

All of this was bookkeeping to make sure that macrotiles of all levels perform the same computation. We finally have some time to do actual work: we run \(k\) steps of computation of the Turing machine defining the \({\mathcal{H}}\)-subshift \(X\), to obtain at most \(k\) forbidden patterns, all of length at most \(k\). We make sure that none of the subwords of \(\langle\texttt{word}\rangle\)is one of these forbidden patterns.

---

1. L.B. gratefully acknowledges partial support from the ERC AdG grant 101097307↩︎