# Groups with self-simulable zero-dimensional dynamics

Sebastián Barbieri, Mathieu Sablik and Ville Salo

###### Abstract.

We say that a finitely generated group $\Gamma$ is (dynamically) self-
simulable if every effectively closed action of $\Gamma$ on a closed subset of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ is the topological factor of a
$\Gamma$-subshift of finite type. We show that self-simulable groups exist,
that any direct product of non-amenable finitely generated groups is self-
simulable, that under technical conditions self-simulability is inherited from
subgroups, and that the subclass of self-simulable groups is stable under
commensurability and quasi-isometries of finitely presented groups.

Some notable examples of self-simulable groups obtained are the direct product
$F_{k}\times F_{k}$ of two free groups of rank $k\geq 2$, non-amenable
finitely generated branch groups, the simple groups of Burger and Mozes,
Thompson’s $V$, the groups $\operatorname{GL}_{n}(\mathbb{Z})$,
$\operatorname{SL}_{n}(\mathbb{Z})$, $\operatorname{Aut}(F_{n})$ and
$\operatorname{Out}(F_{n})$ for $n\geq 5$; The braid groups $B_{m}$ for $m\geq
7$, and certain classes of RAAGs. We also show that Thompson’s $F$ is self-
simulable if and only if $F$ is non-amenable, thus giving a computability
characterization of this well-known open problem. We also exhibit a few
applications of self-simulability on the dynamics of these groups, notably,
that every self-simulable group with decidable word problem admits a nonempty
strongly aperiodic subshift of finite type.

_Keywords:_ group actions, symbolic dynamics, effectively closed actions, non-
amenable groups, subshifts of finite type, Thompson’s groups.

_MSC2010:_ Primary: 37B10, Secondary: 37B05, 20F10.

##  1\. Introduction

A result which ensures that every “complicated” computable object from a class
can be embedded into a “simple” computable object from another class is called
a simulation theorem. A beautiful illustration is the result by Higman [29],
which states that every recursively presented group can be obtained as a
subgroup of a finitely presented group.

In the category of dynamical systems, an important simulation theorem due to
Hochman [30, Theorem 1.6] states that any effectively closed action of
$\mathbb{Z}$ on a subset of $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$
(roughly speaking, an action that can be approximated up to an arbitrary
precision by a Turing machine) can be realized as a topological factor of the
$(\mathbb{Z}\times\\{(0,0)\\})$-subaction of a $\mathbb{Z}^{3}$-subshift of
finite type.

Simulation theorems can shed light on complicated aspects of the “simple”
objects. In the setting of symbolic dynamics, the term “swamp of
undecidability” was coined by Lind [34] to describe the lack of simple
algebraic procedures to gain information about the properties of
multidimensional subshifts of finite type. It was only after the result by
Hochman and further developments [5, 24, 38, 46] that the origin of this swamp
of undecidability was truly understood. Namely, the existence of simple
algebraic descriptions can be proscribed due to the fact that every
effectively closed action of $\mathbb{Z}$ can be obtained as a topological
factor of a subaction of a multidimensional subshift of finite type; and
(expansive) effectively closed actions of $\mathbb{Z}$ can have arbitrary
effectively closed Medvedev degrees [38]. This intuitively means that the
“simplest” configurations in a multidimensional subshift of finite type may
already be quite complex in terms of computability.

Simulation results can be used as black boxes to obtain interesting results. A
wonderful illustration of this method is that the famous result proven
independently by Novikov and Boone [40, 13], which states that there exist
finitely presented groups with undecidable word problem, can be obtained as a
relatively simple corollary from Higman’s theorem. In fact, Higman’s theorem
can be used to prove something much stronger. Namely, the existence of a
universal finitely presented group, that is, one whose finitely generated
subgroups are up to isomorphism precisely all finitely generated recursively
presented groups (for a proof, see [35, Theorem 7.6]).

In recent work by two of the authors, two generalizations of Hochman’s theorem
have been developed for actions of arbitrary finitely generated groups. The
first one [9, Theorem 4.8] states that for any finitely generated group
$\Gamma$ and every semidirect product $\mathbb{Z}^{d}\rtimes_{\varphi}\Gamma$
with $d\geq 2$ and $\varphi$ a homomorphism from $\Gamma$ to
$\operatorname{GL}_{d}(\mathbb{Z})$, every effectively closed action of
$\Gamma$ on a subset of $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ can be
realized as a topological factor of the
$(\\{\vec{0}\\}\times\Gamma)$-subaction of a
$(\mathbb{Z}^{d}\rtimes_{\varphi}\Gamma)$ subshift of finite type. The second
one [8, Theorem 3.1] shows that for any triple of infinite and finitely
generated groups $\Gamma,H,V$, every effectively closed action of $\Gamma$ on
a subset of $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ can be realized as a
topological factor of the $(\Gamma\times\\{1_{H},1_{V}\\})$-subaction of a
$(\Gamma\times H\times V)$-subshift of finite type.

In this work we shall study groups where there is no need to take proper
subactions to recover the effectively closed dynamics. That is, groups whose
computable zero-dimensional dynamics are completely described as topological
factors of subshifts of finite type.

######  Definition 1.1.

We say that a group $\Gamma$ is dynamically self-simulable if every
effectively closed action $\Gamma\curvearrowright
X\subseteq\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ is a topological factor of
a $\Gamma$-subshift of finite type.

In what follows, we shall drop the prefix “dynamically” and say “self-
simulable group”. A more precise, albeit longer, name for this class of groups
would be “group with self-simulable zero-dimensional dynamics”. The reader
should bear in mind that the name “self-simulable” is always referring to the
zero-dimensional dynamics of the group. The name should be then considered as
an analogy to Hochman’s simulation result, with the caveat that both groups
involved coincide.

Both in Hochman’s original result and in the two subsequent generalizations,
the group which simulates the subaction is “large”. In the case of Hochman’s
result, $\mathbb{Z}^{3}$ cannot replaced by $\mathbb{Z}^{2}$: an unpublished
example by Jeandel, the horizontal shift action on the mirror shift, (see
Remark 3.6 or the paragraph after [3, Theorem 2.14] for the definition) shows
that there exist effectively closed $\mathbb{Z}$-actions which are not a
topological factor of a $(\mathbb{Z}\times\\{0\\})$-subaction of any
$\mathbb{Z}^{2}$-subshift of finite type. This suggests that in order to
obtain a dynamical simulation theorem one should require a strictly larger
group. Indeed, it is not hard to see that under mild computability
assumptions, there are effectively closed actions with infinite topological
entropy, and thus no amenable group satisfying the assumptions can be self-
simulable because topological entropy decreases under factor maps (see
Proposition 3.2).

In the case where the effectively closed action of $\mathbb{Z}$ is also
expansive, i.e. topologically conjugate to a subshift, the role of
$\mathbb{Z}^{3}$ in Hochman’s result can be replaced by $\mathbb{Z}^{2}$.
Specifically, a result proven independently by Aubrun and Sablik [5], and
Durand, Romashchenko and Shen [24] shows that every effectively closed
$\mathbb{Z}$-subshift is topologically conjugate to the
$(\mathbb{Z}\times\\{0\\})$-subaction of a sofic $\mathbb{Z}^{2}$-subshift.
However, even if we restrict the scope of a simulation theorem to cover only
expansive actions, it can be shown, under mild computability assumptions, that
no amenable group nor any group with infinitely many ends is self-simulable
[3] (See also Propositions 3.3 and 3.4). Moreover, there exist one-ended non-
amenable groups, such as $F_{k}\times\mathbb{Z}$ for $k\geq 2$ (see
Proposition 3.5) which are not self-simulable. We shall provide a series of
obstructions to self-simulability in Section 3.

The previous obstructions make it plausible to believe that self-simulable
groups may not exist at all. The main result of this article is that there is
a large family of non-amenable groups which are self-simulable.

######  Theorem 1.2.

The direct product $\Gamma=\Gamma_{1}\times\Gamma_{2}$ of any pair of finitely
generated non-amenable groups $\Gamma_{1}$ and $\Gamma_{2}$ is self-simulable.

In the case where the direct product $\Gamma$ is a recursively presented
group, a corollary of Theorem 1.2 is that the class of sofic
$\Gamma$-subshifts coincides with the class of effectively closed
$\Gamma$-subshifts. This answers a question of two of the authors [3, Section
3.4].

Seward proved in [45] that every action of a countable non-amenable group is
the topological factor of a subshift. Our result shows that there is a
subclass of non-amenable groups for which that subshift can always be chosen
of finite type as long as the action is effectively closed.

The proof of Theorem 1.2 is given in Section 5 and relies on two main
ingredients which can be summarized as follows

  * •

The first ingredient comes from a well-known characterization of non-
amenability: a group $\Gamma$ is non-amenable if and only if it admits a
$2$-to-$1$ surjective map $\varphi\colon\Gamma\to\Gamma$ for which
$g^{-1}\varphi(g)$ is in a fixed finite set $K$ for every $g\in\Gamma$. For a
fixed set $K$, we encode the space of all such maps in a $\Gamma$-subshift of
finite type that we call the paradoxical subshift, and use its configurations
to encode families of disjoint one-sided infinite paths indexed by the
elements of the group in a local manner. By taking the direct product of two
non-amenable groups, we are able to encode families of disjoint
$\mathbb{N}^{2}$-grids indexed by the elements of the group.

  * •

The second ingredient is the well-known fact that the space-time diagrams of
Turing machines can be encoded in $\mathbb{N}^{2}$ using Wang tiles. In
particular, given an effectively closed set
$X\subseteq\\{0,1\\}^{\mathbb{N}}$, we can define a finite set of Wang tiles
in such a way that the associated valid tilings of $\mathbb{N}^{2}$ correspond
to elements of $x$.

The rest of the proof essentially consists in showing that all of these
$\mathbb{N}^{2}$-grids can communicate their information locally. Contrary to
the other dynamical simulation results mentioned above, this construction does
not rely on any sort of hierarchical or self-similar structure. The
construction of the paradoxical subshift is given in Section 4, where we also
provide an effective version of Seward’s result in the case where the action
is effectively closed (Theorem 4.6).

Theorem 1.2 provides the first examples of self-simulable groups, however, the
result might strike as fairly artificial as every example is a direct product.
A natural question is whether we can obtain examples which are not direct
products through stability properties of the class of self-simulable groups.
The next two sections are devoted to this question.

In Section 6 we provide a general criterion for a group $\Gamma$ which
contains a self-simulable subgroup $\Delta$ to be self-simulable itself. More
precisely, we say that $\Delta$ is a mediated subgroup, if there exists a
finite generating set $T$ of $\Gamma$ such that for every $t\in T$ the
subgroup $\Delta\cap t\Delta t^{-1}$ is nonamenable. This condition can also
be described in terms of paradoxical path-covers which is what we use to prove
our results. With this notion we can show the following result.

######  Theorem 1.3.

Let $\Gamma$ be a finitely generated and recursively presented group which
contains a mediated self-simulable subgroup $\Delta$. Then $\Gamma$ is self-
simulable.

A consequence of this result is that any finitely generated and recursively
presented group which admits a normal self-simulable subgroup is self-
simulable (Corollary 6.12).

Next we study rigid classes of self-simulable groups. Namely, we show that
self-simulability is a commensurability invariant, and that it is preserved
under quasi-isometries of finitely presented groups.

######  Theorem 1.4.

Let $\Gamma_{1},\Gamma_{2}$ be two finitely generated groups which are
commensurable. Then $\Gamma_{1}$ is self-simulable if and only if $\Gamma_{2}$
is self-simulable.

######  Theorem 1.5.

Let $\Gamma_{1},\Gamma_{2}$ be two finitely presented groups which are quasi-
isometric. Then $\Gamma_{1}$ is self-simulable if and only if $\Gamma_{2}$ is
self-simulable.

The proof of Theorems 1.4 and 1.5 are given in Section 7. The latter is
essentially based on a construction of Cohen [20] which shows that quasi-
isometric finitely presented groups can be embedded in a cocycle-like manner
in subshifts of finite type on either group.

In Section 8 we employ the results obtained in the last sections to exhibit
several explicit examples of groups which are self-simulable. More precisely,
we show

######  Theorem 1.6.

The following groups are self-simulable.

  * •

Finitely generated non-amenable branch groups (Corollary 8.1).

  * •

The finitely presented simple groups of Burger and Mozes [15] (Corollary 8.2).

  * •

Thompson’s group $V$ and higher-dimensional Brin-Thompson’s groups $nV$
(Corollary 8.4).

  * •

The general linear groups $\operatorname{GL}_{n}(\mathbb{Z})$ and special
linear groups $\operatorname{SL}_{n}(\mathbb{Z})$ for $n\geq 5$ (Corollary
8.7).

  * •

The automorphism group $\operatorname{Aut}(F_{n})$ and outer automorphism
group $\operatorname{Out}(F_{n})$ of the free group on at least $n\geq 5$
generators (Corollary 8.10).

  * •

Braid groups $B_{n}$ on at least $n\geq 7$ strands (Corollary 8.11).

  * •

Right-angled Artin groups associated to the complement of a finite connected
graph for which there are two edges at distance at least $3$ (Corollary 8.13).

Furthermore, we show a conditional result on Thompson’s groups $F$ and $T$
(Corollary 8.5). Namely, that Thompson’s group $F$ is self-simulable if and
only if it is non-amenable, and that if $F$ is non-amenable then $T$ is self-
simulable. This has the interesting consequence of providing a computability
criterion for the well-known open problem of the amenability of $F$.

######  Theorem 1.7.

Thompson’s group $F$ is amenable if and only if there exists an effectively
closed action of $F$ which is not the topological factor of an $F$-subshift of
finite type.

In order to obtain the previous results, we produce a toolbox which provides
simple criteria to check that a group is self-simulable. We provide an
abstract set of orthogonality conditions (Lemmas 8.6 and 8.9) ensuring self-
simulability, which works for most of the groups we list. These roughly
generalize the idea of a group acting on a direct product, in such a way that
the subactions that act on a bounded number of coordinates generate the group,
and are non-amenable (for example, the general linear group is generated by
elementary matrices, and $\mathrm{GL}_{2}(\mathbb{Z})$ is non-amenable).

Another tool is Lemma 8.3 which states that if a finitely generated
recursively presented group acts faithfully on a zero-dimensional space such
that for every non-empty open set the subgroup of elements which act trivially
on the complement is non-amenable, then the group is self-simulable. We note
that it is a common theme in the theory of infinite groups that if a group
acts in a sufficiently complex way on small open sets, then we can say
something about the abstract group. In particular this is common in proofs of
simplicity of infinite groups, see [28, 25, 14, 37], and a similar assumption
appears in an important theorem of Rubin [44].

We also study a few dynamical consequences of self-simulability. Namely, in
Corollary 8.18 we show that every self-simulable group with decidable word
problem admits a nonempty strongly aperiodic subshift of finite type, that is,
one on which the group acts freely. This extends a classical result of Berger
[12], namely, that $\mathbb{Z}^{2}$ admits a nonempty strongly aperiodic
subshift of finite type, to a large new class of finitely generated groups.

A second application concerns a particular kind of subshift. Given a group
$\Gamma$, the sunny-side up subshift is the set of all configurations $x$ in
$\\{\mathtt{0},\mathtt{1}\\}^{\Gamma}$ where at most one element $g$ of the
group satisfies $x(g)=\mathtt{1}$. This subshift can be abstractly though of
as the translation action on the one-point compactification of $\Gamma$. We
show in Corollary 8.20 that the sunny-side up subshift is sofic for every
self-simulable group with decidable word problem.

In section 9 we present a few perspectives and questions we were not able to
solve ourselves. Particularly, we discuss potential dynamical properties of
the subshift of finite type extension and the class of self-simulable groups.

Acknowledgments: The authors wish to thank Nathalie Aubrun for many fruitful
discussions on a potential candidate for self-simulable group, which were a
guiding influence for many of the ideas in this paper. We also thank three
anonymous reviewers whose comments greatly improved the presentation of this
article, particularly shortening Section 7 considerably. S. Barbieri was
supported by the FONDECYT grant 11200037 and the ANR projects CoCoGro
(ANR-16-CE40-0005) and CODYS (ANR-18-CE40-0007). M. Sablik was supported by
ANR project Difference (ANR-20-CE40-0002) and the project Computability of
asymptotic properties of dynamical systems from CIMI Labex (ANR-11-LABX-0040).
V. Salo was supported by the Academy of Finland project 2608073211.

##  2\. Preliminaries

We denote by $\mathbb{N}$ the set of non-negative integers and use the
notation $A\Subset B$ to denote that $A$ is a finite subset of $B$.

We will begin with a short introduction to computability, mainly to set the
notation for the rest of the article. We refer readers interested in a more
in-depth introduction to [2, 47, 43].

A Turing machine $\mathcal{M}$ is given by a tuple

$\mathcal{M}=(Q,\Sigma,q_{0},q_{F},\delta),$

where $Q$ is a finite set of states, $\Sigma$ is a finite set called the tape
alphabet, $q_{0}\in Q$ and $q_{F}\in Q$ are the initial and final state
respectively and $\delta\colon Q\times\Sigma\to
Q\times\Sigma\times\\{-1,0,1\\}$ is the transition function.

Let us briefly describe the dynamics of Turing machines on one-sided tapes.
Let $\mathcal{M}$ be a Turing machine as above. Given $(q,x,n)\in
Q\times\Sigma^{\mathbb{N}}\times\mathbb{N}$, we interpret
$x\in\Sigma^{\mathbb{N}}$ as an infinite tape filled with symbols from
$\Sigma$, and $(q,n)\in Q\times\mathbb{N}$ as a working “head” which is on
position $n$ of the tape at state $q$. If $\delta(q,x(n))=(r,a,d)$ and
$n+d\geq 0$, then $\mathcal{M}(q,x,n)=(r,x^{\prime},n+d)$ where $x^{\prime}$
is the configuration which coincides with $x$ in $\mathbb{N}\setminus\\{n\\}$
and $x^{\prime}(n)=a$. If $n+d<0$ then $\mathcal{M}(q,x,n)=(q,x,n)$. In other
words, the head reads the symbol at position $n$, and according to its
transition function, changes said symbol to $a\in\Sigma$, changes its state to
$r\in Q$, and moves itself by $d\in\\{-1,0,1\\}$ if it can do it without
exiting the tape. A Turing machine accepts an input $x\in\Sigma^{\mathbb{N}}$
if starting from $(q_{0},x,0)$ it eventually reaches the final state $q_{F}$,
that is, there is $t\in\mathbb{N}$ so that
$\mathcal{M}^{t}(q_{0},x,0)\in\\{q_{F}\\}\times\Sigma^{\mathbb{N}}\times\mathbb{N}$.

Let $A$ be a finite set and denote by $\sqcup\notin A$ a blank symbol. Let
$\mathcal{M}$ be a Turing machine whose tape alphabet contains
$A\cup\\{\sqcup\\}$. We say that $\mathcal{M}$ accepts a word $w=w_{0}\dots
w_{n-1}\in A^{*}$ if it accepts the infinite word $x\in\Sigma^{\mathbb{N}}$
given by

$x(k)=\begin{cases}w_{k}&\mbox{ if }0\leq k<n\\\ \sqcup&\mbox{ if }n\leq
k.\end{cases}$

Let $L\subset A^{*}$ be a language. We say $L$ is recursively enumerable if
there exists a Turing machine $\mathcal{M}$ which accepts $w\in A^{*}$ if and
only if $w\in L$. We say that $L$ is co-recursively enumerable if
$A^{*}\setminus L$ is recursively enumerable. Finally, we say that $L$ is
decidable if it is both recursively and co-recursively enumerable.

######  Remark 2.1.

For all our purposes, we will only consider Turing machines which never move
the head outside of the tape. It is a straightforward exercise to show that
the notions of decidability do not change with this assumption.

On what follows we will informally refer to Turing machines which have several
inputs on different “tapes”. This situation can be easily modeled by choosing
as tape alphabet the direct product of the alphabets on each tape.

###  2.1. Group actions

For a group $\Gamma$, we denote its identity by $1_{\Gamma}$, and for a word
$w=w_{1}w_{2}\dots w_{k}\in\Gamma^{*}$, we denote by $\underline{w}$ the
element of $\Gamma$ which corresponds to multiplying all the $w_{i}$ from left
to right. If $\Gamma$ is finitely generated, we write $S_{\Gamma}$ for a
finite set of $\Gamma$ which generates $\Gamma$ as a monoid, that is, for
every $g\in\Gamma$ there is $w\in S_{\Gamma}^{*}$ such that $g=\underline{w}$.
We shall drop the subscript $\Gamma$ if the context is clear. For
$g,t\in\Gamma$, we write $g^{t}=t^{-1}gt$ as a shorthand for conjugation by
$t$. Throughout the article, we assume all groups are infinite unless stated
otherwise.

The word problem of a group $\Gamma$ with respect to $S\Subset\Gamma$ is the
language

$\texttt{WP}_{S}(\Gamma)=\\{w\in S^{*}:\underline{w}=1_{\Gamma}\\}.$

A finitely generated group $\Gamma$ is recursively presented (with respect to
$S\Subset\Gamma$) if $\texttt{WP}_{S}(\Gamma)$ is recursively enumerable. A
group is said to have decidable word problem (with respect to
$S\Subset\Gamma$) if $\texttt{WP}_{S}(\Gamma)$ is decidable. These notions do
not depend upon the choice of generating set $S$.

Let $\Gamma\curvearrowright X$ and $\Gamma\curvearrowright Y$ be (left)
actions by homeomorphisms of a group $\Gamma$ on two compact metrizable spaces
$X$ and $Y$. A map $\phi\colon X\to Y$ is called a topological morphism if it
is continuous and $\Gamma$-equivariant, that is, if $\phi(gx)=g\phi(x)$ for
every $g\in\Gamma$ and $x\in X$. A topological morphism which is onto is
called a topological factor map. If there exists a topological factor map
$\phi\colon X\to Y$ we say that $\Gamma\curvearrowright X$ is an extension of
$\Gamma\curvearrowright Y$ and that $\Gamma\curvearrowright Y$ is a factor of
$\Gamma\curvearrowright X$. If the topological morphism is a bijection, we say
that $\Gamma\curvearrowright X$ is topologically conjugate to
$\Gamma\curvearrowright Y$.

Given an action $\Gamma\curvearrowright X$ and a subgroup $H\leqslant\Gamma$,
the $H$-subaction of $\Gamma\curvearrowright X$ is the action
$H\curvearrowright X$ defined by the restriction of $\Gamma\curvearrowright X$
to $H$.

###  2.2. Effectively closed actions

Let $A$ be a finite set, for instance $A=\\{\mathtt{0},\mathtt{1}\\}$. For a
word $w=w_{0}w_{1}\dots w_{n-1}\in A^{*}$ we denote by $[w]$ the cylinder set
of all $x\in A^{\mathbb{N}}$ such that $x_{i}=w_{i}$ for $0\leq i\leq n-1$. We
endow $A^{\mathbb{N}}$ with the prodiscrete topology whose basis is given by
the cylinders $[w]$ for $w\in A^{*}$.

######  Definition 2.2.

A closed subset $X\subseteq A^{\mathbb{N}}$ is effectively closed if there
exists a Turing machine which accepts $w\in A^{*}$ on input if and only if
$[w]\cap X=\varnothing$.

Note that if $X$ is effectively closed and $[w]\cap X\neq\varnothing$, then
the Turing machine run on $w$ will just loop indefinitely. Intuitively, a set
$X$ is effectively closed if there is an algorithm which provides a sequence
of approximations of the complement of $X$ as a union of cylinders. The next
definition extends effectively closed sets by adding the action of a finitely
generated group on $X$.

Let $X\subseteq A^{\mathbb{N}}$, $\Gamma\curvearrowright X$ and $S$ be a
finite generating set of $\Gamma$ which contains the identity. Consider the
alphabet $B=A^{S}$ and for $y\in B^{\mathbb{N}}$ and $s\in S$ let
$\pi_{s}y=\\{y(n)(s)\\}_{n\in\mathbb{N}}\in A^{\mathbb{N}}$. The set
representation of $\Gamma\curvearrowright X$ determined by $S$ is the set
$Y_{\Gamma\curvearrowright X,S}\subseteq B^{\mathbb{N}}$ given by

$Y_{\Gamma\curvearrowright X,S}=\\{y\in B^{\mathbb{N}}:\pi_{1_{\Gamma}}y\in
X,\mbox{ and for every }s\in S,\pi_{s}y=s(\pi_{1_{\Gamma}}y)\\}.$

######  Definition 2.3.

Let $\Gamma$ be a group generated by $S\Subset\Gamma$ and $X\subseteq
A^{\mathbb{N}}$. An action $\Gamma\curvearrowright X$ is effectively closed if
the set representation $Y_{\Gamma\curvearrowright X,S}$ is an effectively
closed subset of $(A^{S})^{\mathbb{N}}$.

This definition is the natural generalization to finitely generated groups of
the definition of Hochman [30, Definition 1.2] for actions of
${\mathbb{Z}}^{d}$. Intuitively, an action $\Gamma\curvearrowright X$ is
effectively closed if there is a Turing machine which on input
$y\in(A^{S})^{\mathbb{N}}$ can detect whether $\pi_{1_{\Gamma}}y\notin X$, or
if there is $s\in S$ such that $\pi_{s}y\neq s(\pi_{1_{\Gamma}}y)$.

######  Remark 2.4.

Some authors use the term “effective action” to mean an action with is
faithful (i.e. that every $g\in\Gamma\setminus\\{1_{\Gamma}\\}$ acts non-
trivially). We do not use this term with this meaning. For instance, the
trivial action of any non-trivial group on an effectively closed set is an
effectively closed action which is not faithful.

While Definition 2.3 is exactly what we will use in our results, sometimes we
will make use of an equivalent statement which is useful for showing that a
particular action is effectively closed.

######  Definition 2.5.

Let $\Gamma$ be a group generated by $S\Subset\Gamma$ and $X\subseteq
A^{\mathbb{N}}$ be effectively closed. An action $\Gamma\curvearrowright X$ is
effective closed if there exists a Turing machine which on inputs $a\in A$,
$s\in S$, $n\in\mathbb{N}$ and $x\in X$, accepts if and only if $a=(sx)_{n}$.

A way to think about an effectively closed action is as an action such that
for every $s\in S$, there is a Turing machine with two tapes. One tape
contains all the symbols of some $x\in X$ in order and the other tape is
empty. The machine can use the other tape to perform computation and
sequentially produce the symbols of $sx$ while reading coordinates of $x$.
Notice that in order to output a symbol $(sx)_{n}$ the Turing machine only
visits finitely many positions of $x$.

######  Remark 2.6.

Every effectively closed action $\Gamma\curvearrowright X$ is continuous.
Indeed, if it were not continuous, there would exist $m\in\mathbb{N}$, $s\in
S$ so that for every $n\in\mathbb{N}$ there are $x^{n},y^{n}\in X$ such that
$x^{n}_{k}=y^{n}_{k}$ for every $k\leq n$ and
$(sx^{n})_{m}\neq(s{y^{n}})_{m}$. It follows that the algorithm computing
$(sx^{n})_{m}$ must take at least $n+1$ steps. Taking a limit point
$\bar{x}\in X$ of the sequence of $x^{n}$ yields a point for which the
algorithm cannot compute $\bar{x}_{m}$ in any number of steps, therefore
contradicting the assumption that $\Gamma\curvearrowright X$ is effectively
closed.

######  Remark 2.7.

In the definition of effectively closed action the Turing machine computes the
image of $x\in X$ under a generator $s\in S$ of $\Gamma$. The algorithm can of
course be adapted so that it computes the image of $x$ under any $w\in S^{*}$.
That is, there is a Turing machine which on input $w\in S^{*}$,
$n\in\mathbb{N}$ and $x\in X$ computes $(\underline{w}x)_{n}$. In particular
the notion of effectively closed action does not depend upon the choice of
generators, and it can be naturally be extended to countable groups which are
not finitely generated but whose elements can be recursively enumerated.

######  Remark 2.8.

In the definition of effectively closed action we may consider just
$A=\\{\mathtt{0},\mathtt{1}\\}$ and obtain the same class of actions up to
topological conjugacy. Indeed, every finite set $A$ can be coded as binary
words in $\\{\mathtt{0},\mathtt{1}\\}^{\lceil\log(|A|)\rceil}$ and thus we may
recode any action on a subset of $A^{\mathbb{N}}$ as an action on a subset of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ by replacing every symbol of $A$ by
its coding.

######  Remark 2.9.

There is a third equivalent notion of effectively closed action which is used
in [9, 8] and is an analogue of Definition 2.5 which only performs computation
on words. Namely, $\Gamma\curvearrowright X\subseteq A^{\mathbb{N}}$ is
effectively closed if the action is continuous and there exists a Turing
machine which on input $s\in S$ and $u,v\in A^{*}$ accepts if and only if
$[v]\cap s([u]\cap X)=\varnothing$. Notice that in this definition we assume
that the action is continuous.

The definition of effectively closed action does not require anything on the
acting group other than being finitely generated. However, in order to be able
to naturally construct actions which are effectively closed, we shall often
ask that the acting group is recursively presented or that it has decidable
word problem. To justify this, we shall show that even admitting a single
faithful effectively closed action imposes strong computability constraints on
the word problem of the acting group.

To this end, we remark that effectively closed sets are called $\Pi_{1}^{0}$
sets in the arithmetical hierarchy and their complements are called
$\Sigma_{1}^{0}$. The $\Sigma_{2}^{0}$ sets are those for which there is a
Turing machine with an oracle to $\Pi_{1}^{0}$ which accepts if the element
belongs to that set, see [43, Chapter 14] for further background.
$\Pi_{2}^{0}$ sets are the complements of those in $\Sigma_{2}^{0}$. In terms
of languages, the word problem of a group would be in $\Pi_{2}^{0}$ if there
is a Turing machine with an oracle to $\Pi_{1}^{0}$ which accepts a word on a
given set of generators if and only if it is not the identity of the group.

######  Proposition 2.10.

Suppose $\Gamma$ is a finitely generated group which admits an effectively
closed faithful action $\Gamma\curvearrowright X$. Then the word problem of
$\Gamma$ is in $\Pi_{2}^{0}$.

###### Proof.

Let $S$ be a set of generators for $\Gamma$ and $\Gamma\curvearrowright
X\subseteq\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ a faithful effectively
closed action. Consider the algorithm which on input $w\in S^{*}$, initializes
a variable $n=1$, enumerates all words $u\in\\{\mathtt{0},\mathtt{1}\\}^{n}$.
For each word, it calls the oracle to $\Pi_{1}^{0}$ to determine if $[u]\cap
X\neq\varnothing$. If this is not the case, it tries to compute the image
under $\underline{w}$ of any configuration
$x\in\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ such that $x_{0}\dots
x_{n-1}=u$. If at some point the algorithm requires coordinates of $x$ outside
of $\\{0,\dots,n-1\\}$, it increases the value of $n$ and restarts the
process. If at any point the algorithm computes a coordinate
$(\underline{w}x)_{m}\neq x_{m}$ then we know $\underline{w}x\neq x$ and thus
that $\underline{w}\neq 1_{\Gamma}$. Such an instance always exists due to the
action being faithful. ∎

In particular, the only effectively closed actions of a simple group whose
word problem is not on $\Pi_{0}^{2}$ would be the trivial actions on
effectively closed sets. Notice that there are countably many $\Pi_{2}^{0}$
sets, and therefore (as there are uncountably many non-isomorphic simple
finitely generated groups [41]) there are uncountably many finitely generated
groups which do not admit any nontrivial effectively closed action.

######  Remark 2.11.

If $\Gamma$ admits a faithful effectively closed action on
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$, then we can ignore the call to
$\Pi_{1}^{0}$ in the previous proof and conclude that the word problem of
$\Gamma$ is co-recursively enumerable.

###  2.3. Shift spaces

Let $A$ be a finite set and $\Gamma$ be a group. The set
$A^{\Gamma}=\\{x\colon\Gamma\to A\\}$ equipped with the left shift action
$\Gamma\curvearrowright A^{\Gamma}$ by left multiplication given by

$gx(h)=x(g^{-1}h)\qquad\mbox{ for every }g,h\in\Gamma\mbox{ and }x\in
A^{\Gamma},$

is the full $\Gamma$-shift. The elements $a\in A$ and $x\in A^{\Gamma}$ are
called symbols and configurations respectively. We endow $A^{\Gamma}$ with the
prodiscrete topology generated by the clopen subbase given by the cylinders
$[a]_{g}=\\{x\in A^{\Gamma}:x(g)=a\\}$ where $g\in\Gamma$ (we just denote by
$[a]$ the cylinder $[a]_{1_{\Gamma}}$). A support is a finite subset
$F\Subset\Gamma$. Given a support $F$, a pattern with support $F$ is an
element $p\in A^{F}$. We denote the cylinder generated by $p$ by
$[p]=\bigcap_{h\in F}[p(h)]_{h}$. Given two patterns $p,q$ we say that $q$
occurs in $p$ if $[p]\subseteq g[q]$ for some $g\in\Gamma$.

######  Definition 2.12.

A subset $X\subseteq A^{\Gamma}$ is a $\Gamma$-subshift if and only if it is
$\Gamma$-invariant and closed in the prodiscrete topology.

If the context is clear, we drop the $\Gamma$ from the notation and speak
plainly of a subshift. Equivalently, $X$ is a subshift if and only if there
exists a set of forbidden patterns $\mathcal{F}$ such that

$X=X_{\mathcal{F}}={A^{\Gamma}\setminus\bigcup_{p\in\mathcal{F},g\in\Gamma}g[p]}.$

Let us briefly recall that an action $\Gamma\curvearrowright X$ on a compact
metrizable space is expansive if there is a constant $C>0$ so that whenever
$d(gx,gy)<C$ for every $g\in\Gamma$ then $x=y$. It is a well known fact that
an action $\Gamma\curvearrowright X$ on a closed subset $X$ of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ is topologically conjugate to a
$\Gamma$-subshift if and only if the action is expansive [27].

######  Definition 2.13.

A subshift $X\subseteq A^{\Gamma}$ is a subshift of finite type (SFT) if there
exists a finite set of forbidden patterns $\mathcal{F}$ such that
$X=X_{\mathcal{F}}$.

It is clear that if we fix $F\Subset\Gamma$ and $\mathcal{L}\subseteq A^{F}$,
we may define a subshift of finite type $X\subseteq A^{\Gamma}$ by declaring
that $x\in X$ if and only if for every $g\in\Gamma$, $(x(gh))_{h\in
F}\in\mathcal{L}$. In other words, we may also define subshifts of finite type
by saying which patterns are allowed within a finite support.

######  Definition 2.14.

A subshift $Y\subseteq A^{\Gamma}$ is sofic if it is the topological factor of
a subshift of finite type.

It will be useful to describe topological morphisms between subshifts in an
explicit way. The following classical theorem provides said description. A
modern proof for actions of countable groups may be found in [18, Theorem
1.8.1].

######  Theorem 2.15 (Curtis-Lyndon-Hedlund [27]).

Let $\Gamma$ be a countable group, $A_{X}$ and $A_{Y}$ be two finite sets and
$X\subseteq A_{X}^{\Gamma},Y\subseteq A_{Y}^{\Gamma}$ be two
$\Gamma$-subshifts. A map $\phi\colon X\to Y$ is a topological morphism if and
only if there exists a finite set $F\Subset\Gamma$ and $\Phi\colon
A_{X}^{F}\to A_{Y}$ such that for every $x\in X$ and $g\in\Gamma$ then
$(\phi(x))(g)=\Phi((g^{-1}x)|_{F})$.

In the above definition, a map $\phi\colon X\to Y$ for which there is
$\Phi\colon A_{X}\to A_{Y}$ so that $(\phi(x))(g)=\Phi(x(g))$ for every
$g\in\Gamma$ is called a $1$-block map. If $Y$ is a sofic subshift, it is
always possible to construct an SFT $\widetilde{X}$ and a $1$-block
topological factor map $\widetilde{\phi}\colon\widetilde{X}\to Y$.
Furthermore, if $\Gamma$ is generated by a finite set $S$, one can ask that
the SFT $\widetilde{X}$ is nearest neighbor with respect to $S$, that is, it
is described by a set of forbidden patterns whose supports are of the form
$\\{1_{\Gamma},s\\}$ where $s$ is a generator of $\Gamma$. In particular, if
$A_{\widetilde{X}}$ is the alphabet of $\widetilde{X}$ and $1_{\Gamma}\in S$,
there is $\mathcal{L}\subseteq(A_{\widetilde{X}})^{S}$ such that
$\widetilde{x}\in\widetilde{X}$ if and only if
$(g\widetilde{x})|_{S}\in\mathcal{L}$ for every $g\in\Gamma$. A proof of this
elementary fact can be found in [7, Proposition 1.7].

###  2.4. Effectively closed subshifts

When working with subshifts it is often useful to give an explicit notion of
effectively closed in order to be able to work with the space $A^{\Gamma}$
instead of $A^{\mathbb{N}}$. In the case of $\mathbb{Z}$-subshifts, patterns
(with convex support) can be naturally identified with words, and thus it is
natural to think of effectively closed $\mathbb{Z}$-subshifts as those that
can be described by a recursively enumerable set of forbidden words. For a
general finitely generated group $\Gamma$, we need to codify patterns in such
a way that a Turing machine might perform computation on them. The following
formalism was introduced in [3].

######  Definition 2.16.

Let $\Gamma$ be a finitely generated group, $S$ a finite set of generators for
$\Gamma$ and $A$ an alphabet. A function $c\colon W\to A$ from a finite subset
$W\Subset S^{*}$ is called a pattern coding. The cylinder defined by a pattern
coding $c$ is given by

$[c]=\bigcap_{w\in W}[c(w)]_{\underline{w}}.$

A pattern coding can be thought of as pattern on free monoid $S^{*}$. It can
be represented on the tape of a Turing machine as a finite sequence of tuples
$\\{(w_{1},a_{1}),(w_{2},a_{2}),\dots,(w_{k},a_{k})\\}$ where $w_{i}\in
S^{*},a_{i}\in A$ and $c(w_{i})=a_{i}$. A set $\mathcal{C}$ of pattern codings
defines a $\Gamma$-subshift $X_{\mathcal{C}}$ by setting

$X_{\mathcal{C}}=A^{\Gamma}\setminus\bigcup_{g\in\Gamma,c\in\mathcal{C}}g[c].$

######  Definition 2.17.

A $\Gamma$-subshift $X$ is effectively closed by patterns if there exists a
recursively enumerable set of pattern codings $\mathcal{C}$ such that
$X=X_{\mathcal{C}}$.

A Turing machine which accepts a pattern coding $c$ if and only if
$c\in\mathcal{C}$ is said to define $X=X_{\mathcal{C}}$. Note that neither
$\mathcal{C}$ nor the Turing machine which defines $X$ are unique.

It is important to stress that, unintuitively, the property of being an
effectively closed subshift by patterns is weaker than the property of being
an effectively closed expansive action. For instance, the full $\Gamma$-shift
is a faithful action which is effectively closed by patterns for any group,
but by Proposition 2.10 there are groups which do not admit any faithful
effectively closed action. However, these two notions coincide whenever the
acting group is recursively presented.

######  Proposition 2.18.

Let $\Gamma$ be a finitely generated and recursively presented group. Then, up
to topological conjugacy, expansive effectively closed actions coincide with
subshifts which are effectively closed by patterns.

###### Proof.

In [9, Proposition 4.1] it is shown that every subshift which is the factor of
an effectively closed action is effectively closed by patterns, so that
direction holds regardless of the acting group. Conversely, if $\Gamma$ is
recursively presented and generated by $S\Subset\Gamma$, given a computable
bijection $\rho\colon\mathbb{N}\to S^{*}$ there is an algorithm which accepts
$(n,m)\in\mathbb{N}^{2}$ if and only if
$\underline{\rho(n)}=\underline{\rho(m)}$. This computable bijection and
algorithm can be used to encode configurations $x\in A^{\Gamma}$ as sequences
in $A^{\mathbb{N}}$ as
$x_{\underline{\rho(0)}}x_{\underline{\rho(1)}}x_{\underline{\rho(2)}}\dots$
and it can be shown that an algorithm to construct forbidden pattern codings
can be translated into an algorithm to enumerate the complement of the set
representation of the encoded action. The details of this construction are
given in [9, Theorem 4.3]. ∎

In consequence with Proposition 2.18, whenever we have a recursively presented
group we shall just say “effectively closed subshift” and omit the suffix “by
patterns”.

##  3\. Obstructions to self-simulability

In this brief section, we present classes of groups which are not self-
simulable by constructing examples of effectively closed actions which are not
factors of SFTs. As we mentioned before, our focus is on groups which are both
infinite and finitely generated. Let us justify that self-simulability is not
interesting on finite groups, or groups which are not finitely generated.

Let $\Gamma$ be a finite group. It is obvious that every subshift $X\subset
A^{\Gamma}$ is finite. In particular, the trivial action on an infinite
effectively closed set can not be the factor of a subshift on $\Gamma$, and
thus $\Gamma$ is not self-simulable. On the other hand, every
$\Gamma$-subshift is of finite type, and thus expansive effectively closed
actions of $\Gamma$ are trivially factors of SFTs.

While definition 2.5 can be extended naturally to countable groups with a
recursive presentation, we will see that non-finitely generated groups can
never be self-simulable for trivial reasons. Indeed, let us consider an
effectively closed set with two points (for instance the two constant maps in
$\\{0,1\\}^{\mathbb{N}}$). Notice that the trivial action of a group on a
finite set is always expansive and effective, and thus it is topologically
conjugate to an effectively closed subshift on that group. In particular, if
said trivial action were the factor of a subshift of finite type, it would be
topologically conjugate to a sofic subshift with two configurations. The
following proposition proscribes this possibility on non-finitely generated
groups.

######  Proposition 3.1.

Let $Y\subset A^{\Gamma}$ be a sofic $\Gamma$-subshift on a non-finitely
generated group $\Gamma$. Then $Y$ is either a singleton or uncountable.

###### Proof.

As $Y$ is sofic, there exists a $\Gamma$-subshift of finite type $X\subset
B^{\Gamma}$, $F\Subset\Gamma$ and $\Phi\colon B^{F}\to A$ such that
$\phi\colon X\to Y$ given by $\phi(x)(g)=\Phi(g^{-1}x|_{F})$ is a topological
factor map. As $X$ is of finite type, there is $T\Subset\Gamma$ and
$\mathcal{L}\subset B^{T}$ such that $x\in X$ if and only if
$gx|_{T}\in\mathcal{L}$ for every $g\in\Gamma$.

Let $S=F\cup T$ and denote by $H=\langle S\rangle$ the finitely generated
group induced by $S$. Let $\\{g_{i}\\}_{i\in I}$ be a set of representative of
left cosets of $H$ in $\Gamma$. As $\Gamma$ is not finitely generated, it
follows that $I$ is infinite.

Then $T$ and $\mathcal{L}$ above induce an $H$-subshift of finite type
$X^{\prime}\subset B^{H}$, while $X^{\prime}$, $F$ and $\mathcal{L}$ induce a
sofic $H$-subshift $Y^{\prime}\subset A^{H}$. We have that $y\in Y$ if and
only if for every $i\in I$ we have $(g_{i}^{-1}y)|_{H}\in Y^{\prime}$. From
this it follows that if $|Y^{\prime}|=1$, then $|Y|=1$, while if $Y^{\prime}$
has at least two configurations, the fact that $I$ is infinite yields that $Y$
is uncountable. ∎

Let us turn our attention back to infinite and finitely generated groups. We
will first show that amenability is an obstruction to self-simulability.
Recall that a group $\Gamma$ is amenable if for every $\delta>0$ and
$K\Subset\Gamma$ there is $F\Subset\Gamma$ such that

$|KF\triangle F|\leq\delta|F|,\textrm{ where }KF\triangle F=(KF\cup
F)\smallsetminus(KF\cap F).$

To every action $\Gamma\curvearrowright X$ of a countable amenable group on a
compact metrizable space $X$ we can associate a non-negative extended real
number $h_{\mathrm{top}}(\Gamma\curvearrowright X)$ called the topological
entropy of $\Gamma\curvearrowright X$. (See section 9 of [33]). It is well
known that if $\Gamma\curvearrowright Y$ is a factor of
$\Gamma\curvearrowright X$ then

$h_{\mathrm{top}}(\Gamma\curvearrowright X)\geq
h_{\mathrm{top}}(\Gamma\curvearrowright Y).$

For every recursively presented and finitely generated amenable group $\Gamma$
there are effectively closed actions with infinite topological entropy.
Indeed, let $S$ be a finite symmetric set of generators of $\Gamma$. Identify
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ with
$\\{\mathtt{0},\mathtt{1}\\}^{S^{*}\times\mathbb{N}}$ through a computable
bijection and let
$X\subseteq\\{\mathtt{0},\mathtt{1}\\}^{S^{*}\times\mathbb{N}}$ be such that
$x\in X$ if and only if for every $n\in\mathbb{N}$ and $w,w^{\prime}\in S^{*}$
such that $\underline{w}=\underline{w^{\prime}}$ we have
$x(w,n)=x(w^{\prime},n)$. Consider the action $\Gamma\curvearrowright X$ given
by

$(g(x))(w,n)=x(g^{-1}w,n)\mbox{ for every }g\in\Gamma,(w,n)\in
S^{*}\times\mathbb{N}.$

Where $g^{-1}w$ stands for any word in $S^{*}$ representing the element
$g^{-1}\underline{w}$.

We may think of this action as a full $\Gamma$-shift on an infinite alphabet.
A direct computation shows that this action has infinite topological entropy.
On the other hand, as $\Gamma$ is recursively presented it follows that the
set presentation of $\Gamma\curvearrowright X$ determined by $S$ is
effectively closed, and thus $\Gamma\curvearrowright X$ is an effectively
closed action.

######  Proposition 3.2.

Let $\Gamma$ be a finitely generated and recursively presented group. If
$\Gamma$ is self-simulable then it is non-amenable.

###### Proof.

Assume that $\Gamma$ is amenable. If $\Gamma\curvearrowright X$ is a subshift,
then $h_{\mathrm{top}}(\Gamma\curvearrowright X)<\infty$ (see Example 9.41 of
[33]). On the other hand, as $\Gamma$ is recursively presented there exist
non-expansive effectively closed actions with infinite topological entropy
which can thus never be factors of a subshift. ∎

The previous argument strongly relies on non-expansive actions. One might
wonder whether if one limits the notion of self-simulation to effectively
closed subshifts then it might be possible for amenable groups to be self-
simulable. A partial answer is that as long as the group has decidable word
problem then there are always effectively closed subshifts which are not
sofic. The proof is based on a counting argument and may be found in [3,
Theorem 2.16].

######  Proposition 3.3 (Theorem 2.16 of [3]).

Let $\Gamma$ be a finitely generated amenable group with decidable word
problem. There exists an effectively closed $\Gamma$-subshift which is not
sofic.

Recall that the number of ends of a finitely generated group is the limit as
$n$ tends to infinity of the number of connected components obtained by
considering its Cayley graph with respect to a generating set and removing all
elements of length $n$ with respect to the word metric induced by that
generating set. The free group $F_{k}$ of rank $k\geq 2$ is an example of a
group with infinitely many ends. The next proposition shows that these non-
amenable groups are not self-simulable.

######  Proposition 3.4 (Theorem 2.17 of [3]).

Let $\Gamma$ be a finitely generated group with decidable word problem and
infinitely many ends. There exists an effectively closed $\Gamma$-subshift
which is not sofic.

In views of Theorem 1.2 and Propositions 3.3 and 3.4 one might wonder if maybe
all it takes to be self-simulable is to be a $1$-ended non-amenable group. The
following result shows that this is not the case.

######  Proposition 3.5.

Let $k\geq 1$, $F_{k}$ be the free group of rank $k$ and
$\Gamma=F_{k}\times\mathbb{Z}$. There exists an effectively closed
$\Gamma$-subshift which is not sofic. In particular $F_{k}\times\mathbb{Z}$ is
not self-simulable.

###### Proof.

Denote the generators of $F_{k}$ by $a_{1},\dots,a_{k}$. Denote the elements
of $\Gamma$ as ordered pairs $(g,n)$ where $g\in F_{k}$ and $n\in\mathbb{Z}$.
Consider the alphabet $A=\\{\mathtt{1},\mathtt{2},\mathtt{\star}\\}$ and the
subshifts $X_{1},X_{2},X_{3}$ of $A^{\Gamma}$ given by

$X_{1}=\\{x\in A^{\Gamma}:\mbox{ if }x(g,n)=x(h,n)=\mathtt{\star}\mbox{ then
}g=h\\},$ $X_{2}=\\{x\in A^{\Gamma}:\mbox{ if }x(g,n)=\mathtt{\star}\mbox{
then }x(g,m)=\mathtt{\star}\mbox{ for every }m\in\mathbb{Z}\\},$
$X_{3}=\\{x\in A^{\Gamma}:\mbox{ if }x(g,n)=\mathtt{\star}\mbox{ then
}x(gh,n)=x(gh^{-1},n)\mbox{ for every }h\in F_{k}\\}.$

Let $X=X_{1}\cap X_{2}\cap X_{3}\subseteq A^{\Gamma}$. The subshift $X$
consists of all configurations on the alphabet $A$ such that if the symbol
$\mathtt{\star}$ occurs at some position $(g,n)$, then it occurs at position
$(g,m)$ for every $m\in\mathbb{Z}$, and does not occur at any other
$(g^{\prime},k)$ for $g^{\prime}\neq g$. Therefore if $\mathtt{\star}$ occurs,
it occurs solely on an infinite “pillar”. Moreover, if $\mathtt{\star}$
occurs, it acts as a mirror in the sense that the configuration is symmetric
with respect to taking inverses relative to the pillar, that is, for every
$h\in F_{k}$, we have that $x(gh,m)=x(gh^{-1},m)$ for every $m\in\mathbb{Z}$.
In other words, following $h$ or $h^{-1}$ from the pillar leads to the same
symbol. An illustration of part of a configuration in $X$ can be seen in
Figure 1.

$a_{1}$

$a_{2}$

$\mathtt{\star}$

$\mathtt{\star}$

$\mathtt{\star}$

$\mathtt{\star}$

$\mathtt{\star}$

$\mathtt{1}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{0}$

$\mathtt{0}$

$\mathtt{1}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{1}$

$\mathtt{1}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{1}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{1}$

$a_{1}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{0}$

$\mathtt{1}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{0}$

$\mathtt{1}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{\star}$

$\mathtt{\star}$

$\mathtt{\star}$

$\mathtt{\star}$

$\mathtt{\star}$

$\mathtt{0}$

$\mathtt{0}$

$\mathtt{1}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{1}$

$\mathtt{0}$

$\mathtt{0}$

$\mathtt{1}$

$\mathtt{1}$

Figure 1. Part of a configuration in $X$ for $\Gamma=F_{2}\times\mathbb{Z}$
(left) and $\Gamma=F_{1}\times\mathbb{Z}=\mathbb{Z}\times\mathbb{Z}$ (right).

It is straightforward to check that $X$ is effectively closed. Suppose that
$X$ is a sofic subshift. Then there exists a finite alphabet $A^{\prime}$, a
nearest neighbor subshift of finite type $Y\subseteq(A^{\prime})^{\Gamma}$,
and a $1$-block factor map $\phi\colon Y\to X$. Let $N$ be an integer such
that

$N>3\log_{2}(|A^{\prime}|).$

We claim that there exist two distinct configurations $y,y^{\prime}\in Y$ such
that

  1. (1)

$\phi(y)(1_{F_{k}},0)=\phi(y^{\prime})(1_{F_{k}},0)=\mathtt{\star}$.

  2. (2)

$y(1_{F_{k}},n)=y^{\prime}(1_{F_{k}},n)$ for every $n\in\mathbb{Z}$.

  3. (3)

There exists $n\in\\{1,\dots,N\\}$ such that
$\phi(y)(a_{1}^{n},0)\neq\phi(y^{\prime})(a_{1}^{n},0)$.

We argue by compactness. Let $m\in\mathbb{N}$ and let

$D_{m}=\\{(a_{1}^{n},k):n\in\\{1,\dots,N\\},k\in\\{0,\dots,m-1\\}\\},$
$H_{m}=\\{(1_{F_{k}},k):k\in\\{-m,\dots,2m-1\\}.$

Let $p\colon D_{m}\to\\{\mathtt{0},\mathtt{1}\\}$ be an arbitrary function. By
construction of $X$ there exists a configuration $x_{p}\in X$ such that
$x_{p}|_{D_{m}}=p$ and $x_{p}|_{H_{m}}$ is identically $\mathtt{\star}$. In
particular, for every such $p$ there must exist $y_{p}\in Y$ such that
$\phi(y_{p})=x_{p}$. Notice that as $N\geq 3\log_{2}(|A^{\prime}|)$, then

$|\\{\mathtt{0},\mathtt{1}\\}^{D_{m}}|=2^{Nm}>|A^{\prime}|^{3m}=|(A^{\prime})^{H_{m}}|.$

We deduce that there must exist two distinct $p,p^{\prime}\colon
D_{m}\to\\{\mathtt{0},\mathtt{1}\\}$ such that
$y_{p}|_{H_{m}}=y_{p^{\prime}}|_{H_{m}}$. Let $(a_{1}^{n},r)\in D_{m}$ such
that $\phi(y_{p})(a_{1}^{n},r)\neq\phi(y_{p^{\prime}})(a_{1}^{n},r)$, then the
configurations

$y_{m}=(1_{F_{k}},r)y_{p}\mbox{ and
}y^{\prime}_{m}=(1_{F_{k}},r)y_{p^{\prime}},$

given by

$y_{m}(g,n)=y_{p}(g,n-r)\mbox{ and
}y^{\prime}_{m}(g,n)=y^{\prime}_{p}(g,n-r)\mbox{ for every }(g,n)\in
F_{k}\times\mathbb{Z},$

satisfy that:

  1. (1)

$\phi(y_{m})(1_{F_{k}},0)=\phi(y^{\prime}_{m})(1_{F_{k}},0)=\mathtt{\star}$.

  2. (2)

$y_{m}(1_{F_{k}},k)=y^{\prime}_{m}(1_{F_{k}},k)$ for every
$k\in\\{-m,\dots,m\\}$.

  3. (3)

There exists $n\in\\{1,\dots,N\\}$ such that
$\phi(y_{m})(a_{1}^{n},0)\neq\phi(y^{\prime}_{m})(a_{1}^{n},0)$.

Any accumulation point of the sequence
$(y_{m},y^{\prime}_{m})_{m\in\mathbb{N}}$ yields a pair $y,y^{\prime}\in Y$
which satisfies the three properties above, thus proving our claim.

Let us now reach a contradiction. Let us define the configuration
$y^{*}\in(A^{\prime})^{\Gamma}$ given by

$y^{*}(g,n)=\begin{cases}y(g,n)&\mbox{ if }g\mbox{ as a reduced word begins
with }a_{1}\\\ y^{\prime}(g,n)&\mbox{ otherwise.}\end{cases}$

As $Y$ is a nearest neighbor subshift of finite type and
$y(1_{F_{k}},n)=y^{\prime}(1_{F_{k}},n)$ for every $n\in\mathbb{Z}$, it
follows that $y^{*}$ contains no forbidden patterns and thus $y^{*}\in Y$. On
the other hand, we have that $\phi(y^{*})(1_{F_{k}},0)=\mathtt{\star}$ and, as
there is $n\in\\{1,\dots,N\\}$ such that
$\phi(y)(a_{1}^{n},0)\neq\phi(y^{\prime})(a_{1}^{n},0)$, we have that
$\phi(y^{*})(a_{1}^{n},0)\neq\phi(y^{*})(a_{1}^{-n},0)$. Therefore
$\phi(y^{*})\notin X$, contradicting the fact that $\phi\colon Y\to X$ is a
factor map.∎

######  Remark 3.6.

The subshift $X$ in the proof of Proposition 3.5 is usually called the Mirror
shift when $k=1$.

With minor modifications to the proof above, one obtains the following more
general statement, we shall only give a general outline.

######  Theorem 3.7.

Let $\Gamma_{1},\Gamma_{2}$ be finitely generated groups. If $\Gamma_{1}$ is
multi-ended and $\Gamma_{2}$ is amenable, then the direct product
$\Gamma=\Gamma_{1}\times\Gamma_{2}$ is not self-simulable.

###### Proof sketch.

First let us argue that we can replace $\mathbb{Z}$ in the proof above by an
arbitrary finitely generated amenable group $\Gamma_{2}$. We can use the exact
same definition of $X_{1},X_{2},X_{3}$, and observe that $X$ is still
effectively closed (note that $X_{2}$ is in fact an SFT as long as
$\Gamma_{2}$ is finitely generated). By the amenability of $\Gamma_{2}$ we can
find a sequence $\\{C_{m}\\}_{m\in\mathbb{N}}$ such that if $B_{m}$ is the
ball of size $m$ in $\Gamma_{2}$ then $C_{m}$ satisfies $|C_{m}B_{m}|\leq
3|C_{m}|$. Replace in the proof, for each $m\in\mathbb{N}$, the sets $D_{m}$
and $H_{m}$ by the sets

$D_{m}=\\{(a_{1}^{n},h):n\in\\{1,\dots,N\\},h\in C_{m}\\},$
$H_{m}=\\{(1_{F_{k}},h):h\in C_{m}B_{m}\\}.$

Then we have

$|\\{\mathtt{0},\mathtt{1}\\}^{D_{m}}|=2^{N|F_{m}|}>|A^{\prime}|^{3|F_{m}|}\geq|A^{\prime}|^{|F_{m}B_{m}|}=|(A^{\prime})^{H_{m}}|.$

And the rest of the proof is analogous as for Proposition 3.5.

In generalizing $F_{k}$ to an arbitrary multi-ended group $\Gamma_{1}$, there
is an additional problem, namely when the word problem of $\Gamma_{1}$ is not
co-recursively enumerable it is not clear that the subshifts $X_{1}$ and
$X_{3}$ are effectively closed. In order to adapt them to this setting we use
the axial elements defined in [20]. We say $h\in\Gamma_{1}$ is _$k$ -axial_ if
it has infinite order and for the radius $k$-ball $B_{k}$, we have
$(h^{a}B_{k}:h^{b}B_{k}:h^{c}B_{k})$ for any integers $a<b<c$, where the
notation $(S:T:U)$ means that $S$ and $U$ lie in distinct connected components
of the Cayley graph of $\Gamma\setminus T$, for some fixed generating set. A
$k$-axial element exists in any multi-ended group, for any large enough $k$
(see [21] for a proof).

Now letting $h$ be any $k$-axial element (for any $k$), and picking

$X_{2}=\\{x\in A^{\Gamma}:\mbox{ if }x(g,n)=\mathtt{\star}\mbox{ then
}x(g,m)=\mathtt{\star}\mbox{ for every }m\in\Gamma_{2}\\},$ $X_{3}=\\{x\in
A^{\Gamma}:\mbox{ if }x(g,n)=\mathtt{\star}\mbox{ then
}x(gh^{i},n)=x(gh^{-i},n)\in\\{1,2\\}\mbox{ for every
}i\in\mathbb{Z}\setminus\\{0\\}\\}.$

and $X=X_{2}\cap X_{3}$, the argument above works with minor changes,
replacing $a_{1}^{n}$ by $h^{n}$. ∎

##  4\. The paradoxical subshift

The purpose of this section is to exploit the structure of finitely generated
non-amenable groups to construct a family of subshifts of finite type with a
remarkable structural property. More precisely, let $\Gamma$ be a finitely
generated non-amenable group. We shall construct a nonempty $\Gamma$-subshift
of finite type $\mathbf{P}$, which we call the paradoxical subshift, that has
the property that any configuration $\rho\in\mathbf{P}$ induces an injective
map from $\Gamma\times\mathbb{N}$ to $\Gamma$ which is “Lipschitz” on the
second component. In other words, the configuration assigns a one-sided path
with bounded jumps to every element of $\Gamma$, and the paths do not
intersect.

The existence of this subshift of finite type relies on the well-known
characterization of non-amenable groups by the existence of paradoxical
decompositions in terms of a convenient statement on the existence of bounded
surjective $2$-to-$1$ maps.

######  Proposition 4.1 (Theorem 4.9.2 of [18]).

A group $\Gamma$ is non-amenable if and only if there exists a $2$-to-$1$
surjective map $\varphi\colon\Gamma\to\Gamma$ and a finite set
$K\Subset\Gamma$ so that $g^{-1}\varphi(g)\in K$ for every $g\in\Gamma$.

The paradoxical subshift shall be the main tool in the proof of Theorem 1.2.
As an immediate application of this object, we shall provide at the end of
this section an alternative proof of a result of Seward [45] which states that
every action of a countable non-amenable group admits an extension which is a
subshift. Furthermore, we shall show that under certain computability
restrictions the subshift can always be picked effectively closed, see Theorem
4.6.

###  4.1. The paradoxical subshift

Given a countable group $\Gamma$ and a symmetric set $K\Subset\Gamma$ (that
is, so that $K=K^{-1}$), we define the alphabet
$A_{K}=K^{3}\times\\{\mathtt{G},\mathtt{B}\\}$. Given
$a=((a_{1},a_{2},a_{3}),\mathtt{t})\in A_{K}$, we write
$L_{\mathtt{G}}(a)=a_{1}$, $L_{\mathtt{B}}(a)=a_{2}$,
$R_{\mathtt{t}}(a)=a_{3}$ and $\mathtt{t}(a)=\mathtt{t}$. The value
$\mathtt{t}(a)\in\\{\mathtt{G},\mathtt{B}\\}$ is called the color of the
symbol $a\in A_{K}$, we interpret the color as being either green
($\mathtt{G}$) or blue ($\mathtt{B}$). The letters $L$ and $R$ stand for left
and right respectively.

######  Definition 4.2.

Let $\Gamma$ be a countable group and $K\Subset\Gamma$. The paradoxical
subshift is the $\Gamma$-subshift $\mathbf{P}\subseteq(A_{K})^{\Gamma}$
defined by the condition that $\rho\in\mathbf{P}$ if and only if for every
$g\in\Gamma$ if we have $\rho(g)=a$ then:

  1. (1)

$b=\rho(gL_{\mathtt{G}}(a))$ is of color G and
$R_{\mathtt{G}}(b)=(L_{\mathtt{G}}(a))^{-1}$,

  2. (2)

$c=\rho(gL_{\mathtt{B}}(a))$ is of color B and
$R_{\mathtt{B}}(c)=(L_{\mathtt{B}}(a))^{-1}$,

  3. (3)

If $d=\rho(gR_{\mathtt{t}}(a))$, then
$L_{\mathtt{t}}(d)=(R_{\mathtt{t}}(a))^{-1}$.

$ⓓ$$ⓐ$$ⓑ$$ⓒ$$\bigcirc$$\bigcirc$$\bigcirc$$\bigcirc$$R_{\texttt{G}}(a)$$L_{\texttt{G}}(a)$$R_{\texttt{G}}(b)$$L_{\texttt{B}}(a)$$R_{\texttt{B}}(c)$$L_{\texttt{G}}(d)$$L_{\texttt{G}}(b)$$L_{\texttt{B}}(b)$$L_{\texttt{G}}(c)$$L_{\texttt{B}}(c)$
Figure 2. The local structure of the paradoxical subshift. The two first
components of the alphabet are drawn with dashed arrows, while the third
component is drawn with a thick arrow. The three conditions in the definition
simply correspond to the property that following an arrow of a certain color
and then following the inverse arrow of the same color amounts to no movement
at all.

A representation of the paradoxical subshift is given on Figure 2, note that
it induces a directed graph where each vertex has exactly two different
ancestors, one labeled by $\mathtt{G}$ and another by $\mathtt{B}$. A finite
set of forbidden patterns which defines the paradoxical subshift is the set of
all patterns $p\in(A_{K})^{(K\cup\\{1_{\Gamma}\\})}$ so that at least one of
the three conditions in the definition is not satisfied for for
$g=1_{\Gamma}$. It follows that the paradoxical subshift is a
$\Gamma$-subshift of finite type.

######  Proposition 4.3.

Let $\Gamma$ be a non-amenable group. Then there exists a symmetric set
$K\Subset\Gamma$ containing the identity so that the paradoxical subshift
$\mathbf{P}$ is nonempty.

###### Proof.

As $\Gamma$ is non-amenable, Proposition 4.1 ensures that there exists a
$2$-to-$1$ surjective map $\varphi\colon\Gamma\to\Gamma$ and a finite set
$K\Subset\Gamma$ so that $g^{-1}\varphi(g)\in K$ for every $g\in\Gamma$.
Potentially taking a larger set $K$, we can assume that $K$ is symmetric and
contains the identity, and so $\varphi(g)^{-1}g\in K$ as well.

As $\varphi$ is $2$-to-$1$ and surjective, there is a partition
$\Gamma=\Gamma_{\mathtt{G}}\cup\Gamma_{\mathtt{B}}$ so that the restrictions
$\varphi_{\mathtt{G}}$ and $\varphi_{\mathtt{B}}$ of $\varphi$ to
$\Gamma_{\mathtt{G}}$ and $\Gamma_{\mathtt{B}}$ respectively are bijections
onto $\Gamma$. Let $\rho=\\{\rho(g)\\}_{g\in\Gamma}\in(A_{K})^{\Gamma}$ be
defined by

$\rho(g)=\begin{cases}\left(\left(g^{-1}\varphi_{\mathtt{G}}^{-1}(g),g^{-1}\varphi_{\mathtt{B}}^{-1}(g),g^{-1}\varphi(g)\right),\mathtt{G}\right)&\mbox{
if }g\in\Gamma_{\mathtt{G}}\\\
\left(\left(g^{-1}\varphi_{\mathtt{G}}^{-1}(g),g^{-1}\varphi_{\mathtt{B}}^{-1}(g),g^{-1}\varphi(g)\right),\mathtt{B}\right)\\\
\end{cases},$

Notice that letting $h=\varphi_{\mathtt{G}}^{-1}(g)$ we have
$\varphi(h)^{-1}h=(\varphi(\varphi_{\mathtt{G}}^{-1}(g)))^{-1}\varphi_{\mathtt{G}}^{-1}(g)=g^{-1}\varphi_{\mathtt{G}}^{-1}(g)\in
K$. Similarly, $g^{-1}\varphi_{\mathtt{B}}^{-1}(g)\in K$. This shows that
$\rho(g)\in A_{K}$ for every $g\in\Gamma$. It is a straightforward computation
to show that $\rho$ satisfies the three conditions in Definition 4.2.∎

Given a color $\mathtt{t}\in\\{\mathtt{G},\mathtt{B}\\}$, denote by
$\overline{\mathtt{t}}$ the opposite color. We can associate to each
$g\in\Gamma$ a continuous map
$\gamma_{g}\colon\mathbb{N}\times\mathbf{P}\to\Gamma$ by following the left
arrows of the opposite color as that of $\rho(g)$ as follows:

$\gamma_{g}(n,\rho)=\begin{cases}gL_{\overline{\mathtt{t}}}(\rho(g))&\mbox{ if
}n=0\mbox{ and }\rho(g)\mbox{ has color }\mathtt{t}\\\
\gamma_{g}(n-1,\rho)L_{\overline{\mathtt{t}}}(\rho(\gamma_{g}(n-1,\rho)))&\mbox{
if }n>0\mbox{ and }\rho(g)\mbox{ has color }\mathtt{t}\end{cases}.$

In simple words, the map $\gamma_{g}$ assigns a path to $g$ by “following the
left arrows of the opposite color of $g$”. It is clear that $\gamma_{g}$ is
continuous, as $\gamma_{g}(n,\rho)$ only depends upon the values of $\rho$ in
$gK^{n}$. Notice also that for every $g\in\Gamma$ we have

($\heartsuit$)
$\displaystyle\gamma_{g}(n,\rho)=g\gamma_{1_{\Gamma}}(n,g^{-1}\rho).$

######  Remark 4.4.

Notice that if $\rho(g)$ has color $\mathtt{G}$, then for every
$n\in\mathbb{N}$ the symbol $\rho(\gamma_{g}(n,\rho))$ has color $\mathtt{B}$.
Similarly, if $\rho(g)$ has color $\mathtt{B}$, then for every
$n\in\mathbb{N}$ the symbol $\rho(\gamma_{g}(n,\rho))$ has color $\mathtt{G}$.
In particular, for every $n>0$,

$\gamma_{g}(n-1,\rho)=\gamma_{g}(n,\rho)R_{\mathtt{t}}(\rho(\gamma_{g}(n,\rho))).$

The function $\gamma_{g}$ assigns a one sided path to $g$. The next lemma says
that all these paths are disjoint.

######  Lemma 4.5.

For every $\rho\in\mathbf{P}$, the map $(n,g)\mapsto\gamma_{g}(n,\rho)$ for
$(n,g)\in\mathbb{N}\times\Gamma$ is injective.

###### Proof.

Suppose there are $g,h\in\Gamma$ and $n,m$ so that
$\gamma_{g}(n,\rho)=\gamma_{h}(m,\rho)$. By Remark 4.4 we have that $\rho(g)$
and $\rho(h)$ have the same color. Furthermore, repeatedly using the relation
in the remark, we may assume that either $n=0$ or $m=0$. Without loss of
generality let $n=0$.

Let $v=\gamma_{g}(0,\rho)$. We have that $g=vR_{\mathtt{t}}(\rho(v))$ and thus
$\rho(v)$ and $\rho(g)$ have different color. If $m>0$, then $\rho(v)$ is of
the same color as
$\rho(\gamma_{h}(m-1,\rho))=\rho(vR_{\mathtt{t}}(\rho(v))=\rho(g)$, therefore
we conclude that $m=0$ and thus
$\gamma_{h}(0,\rho)R_{\mathtt{t}}(\gamma_{h}(0,\rho))=h$. Hence $g=h$.∎

###  4.2. Existence of effective subshift extensions

Before finishing this section we shall to show a simple application of our
construction. In [45, Theorem 1.2] the author shows that every action of a
countable group on a compact metrizable space admits a subshift extension. The
proof is essentially based on theorem of Whyte [50] on the existence of
translation-like actions of $F_{2}$ on non-amenable groups and a
generalization of the classical factor map between the full $2$-shift and the
full $4$-shift in $F_{2}$ (See Section C of the appendix in [42]).

We shall provide an alternative proof of that theorem. Furthermore, we shall
show that whenever $\Gamma$ is finitely generated and $\Gamma\curvearrowright
X$ is effectively closed, then the subshift can be chosen to be effectively
closed.

######  Theorem 4.6.

Every action $\Gamma\curvearrowright X$ of a countable non-amenable group over
a compact metrizable space $X$ is the factor of some $\Gamma$-subshift $Z$.

Furthermore, if $\Gamma$ is finitely generated, $X\subseteq A^{\mathbb{N}}$
for some finite $A$ and $\Gamma\curvearrowright X$ is effectively closed, then
$Z$ can be chosen effectively closed by patterns.

###### Proof.

It is a standard exercise to show that every action of a countable group
$\Gamma$ over a compact metrizable space $X$ admits a zero-dimensional
extension, for instance, as an inverse limit of symbolic covers of radius
$\tfrac{1}{n}$ of $X$ (see also [45, Lemma 4.1]). We shall thus assume,
without loss of generality, that $X$ is a closed subset of $A^{\mathbb{N}}$.

As $\Gamma$ is a countable non-amenable group, there exists $K\Subset\Gamma$
such that the paradoxical subshift $\mathbf{P}\subseteq(A_{K})^{\Gamma}$ is
nonempty. Recall that $\mathbf{P}$ comes equipped with a family of continuous
maps $\gamma_{g}\colon\mathbb{N}\times\mathbf{P}\to\Gamma$.

Consider the subshift $Z\subseteq\mathbf{P}\times A^{\Gamma}$ which consists
on all configurations $z=(\rho,y)\in\mathbf{P}\times A^{\Gamma}$ which satisfy
the following two constraints.

  1. (1)

For every $n\in\mathbb{N}$ and $g\in\Gamma$, if we consider

$u=y(\gamma_{g}(0,\rho))y(\gamma_{g}(1,\rho))\dots y(\gamma_{g}(n-1,\rho))\in
A^{n},$

then $[u]\cap X\neq\varnothing$.

  2. (2)

For every $n,m\in\mathbb{N}$ and $g,h\in\Gamma$ if we consider

$u=y(\gamma_{g}(0,\rho))y(\gamma_{g}(1,\rho))\dots y(\gamma_{g}(n-1,\rho))\in
A^{n},$ $v=y(\gamma_{gh}(0,\rho))y(\gamma_{gh}(1,\rho))\dots
y(\gamma_{gh}(m-1,\rho))\in A^{m},$

then $[v]\cap h^{-1}([u]\cap X)\neq\varnothing$.

Clearly $Z$ is a closed $\Gamma$-invariant set, and therefore a
$\Gamma$-subshift. Consider the map $\phi\colon Z\to A^{\mathbb{N}}$ given by

$\phi(\rho,y)_{n}=y(\gamma_{1_{\Gamma}}(n,\rho))\mbox{ for every
}n\in\mathbb{N}.$

The map $\phi$ is obviously continuous. By the first constraint, we have that
$[\phi(\rho,y)|_{\\{0,\dots,n-1\\}}]\cap X\neq\varnothing$ for every
$n\in\mathbb{N}$. As $X$ is closed this means that $\phi(\rho,y)\in X$.

Let $g\in\Gamma$ and $k\in\mathbb{N}$. From here we obtain,

$\phi(g\rho,gy)_{k}=(gy)(\gamma_{1_{\Gamma}}(k,g\rho))=y(g^{-1}\gamma_{1_{\Gamma}}(k,g\rho))=y(\gamma_{g^{-1}}(k,\rho)).$

The second constraint implies that for every $n,m\in\mathbb{N}$ we have that

$[\phi(g\rho,gy)|_{\\{0,\dots,m-1\\}}]\cap
g([\phi(\rho,y)|_{\\{0,\dots,n-1\\}}]\cap X)\neq\varnothing.$

Thus $\phi(g\rho,gy)=g\phi(\rho,y)$, hence the map $\phi$ is
$\Gamma$-equivariant.

Finally, let us show that $\phi$ is surjective. Let $x\in X$ and choose some
$\rho\in\mathbf{P}$. Let $y\in A^{\Gamma}$ be any configuration such that

$y(\gamma_{g}(n,\rho))=(g^{-1}x)_{n}.$

Such a configuration $y$ exists due to the map
$(n,g)\mapsto\gamma_{g}(n,\rho)$ being injective. It is direct from the
definition that $(\rho,y)\in Z$ as it satisfies the two constraints, and that
$\phi(\rho,y)=x$. This shows that $\Gamma\curvearrowright X$ is a factor of
the $\Gamma$-subshift $Z$.

Now suppose that $\Gamma$ is finitely generated and that
$\Gamma\curvearrowright X$ is effectively closed. We will show that $Z$ can be
defined through a recursively enumerable set of forbidden pattern codings. As
$\mathbf{P}\times A^{\Gamma}$ is a $\Gamma$-subshift of finite type, it is
effectively closed, so we only need to show that we can enforce conditions (1)
and (2) in this way.

Let $S\Subset\Gamma$ be a finite symmetric set of generators of $\Gamma$ such
that $K\subseteq S$. Denote by $\varepsilon$ the empty word on $S^{*}$. We
define $\mathcal{C}$ as the set of pattern codings $c\colon\bigcup_{k\leq
n}S^{k}\to A_{K}\times A$ for some $n>1$ which fail to satisfy the following
conditions:

  1. (1’)

For every $w\in\bigcup_{k\leq n-1}S^{k}$ the conditions from Definition 4.2
(replacing $g$ by $w$) are satisfied. Notice that if condition (1’) holds,
then for every $w\in\bigcup_{k\leq n-1}S^{k}$ we may properly define on $c$ a
local analogue $\widetilde{\gamma}_{c}^{w}\colon\mathbb{N}\to\bigcup_{k\leq
n}S^{k}$ of the map
$\gamma_{\underline{w}}\colon\mathbb{N}\times\mathbf{P}\to\Gamma$ on $c$, that
is, such that

$\widetilde{\gamma}^{w}_{c}(k)=\gamma_{\underline{w}}(k,\rho)\mbox{ for every
}k\leq n-|w|-1\mbox{ and }\rho\in[c]\cap\mathbf{P}.$

  2. (2’)

Let $k\leq n$. If
$u=\widetilde{\gamma}^{\varepsilon}_{c}(0)\widetilde{\gamma}^{\varepsilon}_{c}(1)\dots\widetilde{\gamma}^{\varepsilon}_{c}(k)$
then $[u]\cap X\neq\varnothing$.

  3. (3’)

Let $s\in S$ and $\ell,\ell^{\prime}\leq n-2$. Let

$u=\widetilde{\gamma}^{\varepsilon}_{c}(0)\widetilde{\gamma}^{\varepsilon}_{c}(1)\dots\widetilde{\gamma}^{\varepsilon}_{c}(\ell)$
$v=\widetilde{\gamma}^{s}_{c}(0)\widetilde{\gamma}^{s}_{c}(1)\dots\widetilde{\gamma}^{s}_{c}(\ell^{\prime})$

Then $[v]\cap s^{-1}([u]\cap X)\neq\varnothing$.

Failure of condition (1’) can easily be checked with an algorithm. Algorithms
to check conditions (2’) and (3’) exist due to the action being effectively
closed and Remark 2.9. It is a straightforward exercise that the set of
pattern codings above defines a subshift $\widetilde{Z}$ which satisfies
condition (1) and condition (2) with $h\in\Gamma$ replaced by some $s\in S$.
As $\Gamma$ is generated by $S$ this suffices in this case. ∎

Note that in the second part of Theorem 4.6 we do not ask that the group is
recursively presented. Let us stress again that effectively closed subshifts
(by patterns) coincide up to topological conjugacy with expansive effectively
closed actions only if the group is recursively presented, therefore if we
wish to interpret our effectively closed subshift extension as an effectively
closed expansive action on a closed subset of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$, we need to ask that the group is
recursively presented.

##  5\. Self-simulable groups

The purpose of this section is to prove Theorem 1.2. Our main tool shall be
the paradoxical subshift as defined in Section 4. The main idea is quite
similar to the application shown on the previous section, namely, we saw that
the possibility to associate paths to group elements allows us to encode
arbitrary actions in subhifts by putting sequences on the path. By taking a
direct product of two finitely generated groups, we will be able to associate
not only a path but an actual $\mathbb{N}^{2}$-grid to each group element.
This will enable us to verify with local rules that a configuration is on some
effectively closed set by implementing Turing machines via Wang tilesets.

More precisely, given an effectively closed action $\Gamma\curvearrowright
X\subseteq\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$, we use a classical
embedding of Turing machines through seeded Wang tilings to construct a tiling
of $\mathbb{N}^{2}$, so that every configuration in which a special symbol
occurs at $(0,0)$ encodes in a straightforward manner a configuration on the
set representation of $\Gamma\curvearrowright X$. This idea is quite old and
can be traced back to [48, 49] and [31]. These ideas were famously used by
Berger to settle the undecidability of the domino problem [12]. The grids
shall encode a Turing machine which verifies that the configuration indeed
belongs to the set representation.

Finally, we shall encode a seeded instance of our tiling of $\mathbb{N}^{2}$
on top of the $\mathbb{N}^{2}$-grids of a product of two paradoxical subshifts
on each group, in such a way that the seed occurs at the origin of every grid.
We then endow this object with local rules ensuring that all the
$\mathbb{N}^{2}$-grids communicate information coherently with the action of
$\Gamma$. From here the factor map will be defined naturally using the grids
and the set representation.

###  5.1. The computation tilespace

In this section we shall construct a set of tilings of $\mathbb{N}^{2}$ which
is defined through local rules, and which has the property that the subset of
tilings such that a particular type of symbol, called the seed, occurs at
$(0,0)$, maps surjectively into a fixed effectively closed set.

Let us describe how to code the dynamics of a Turing machine
$\mathcal{M}=\\{Q,\Sigma,q_{0},q_{F},\delta\\}$ in a seeded tiling of
$\mathbb{N}^{2}$. Consider the alphabet $\mathcal{W}_{\mathcal{M}}$ given by
the square tiles drawn on Figure 3. Notice that we give special names to three
of the tiles on the top row.

$\texttt{tile}_{1}(a)$$(q_{0},a)$$\texttt{tile}_{2}(a)$$a$$a$$a$$(s^{\prime},b^{\prime})$$(s,b)$$c^{\prime}$$\stackrel{{\scriptstyle\ell^{\prime}}}{{\leftarrow}}$$(\ell,c)$$d^{\prime}$$\stackrel{{\scriptstyle
r^{\prime}}}{{\rightarrow}}$$(r,d)$$(q,a)$$\stackrel{{\scriptstyle
q}}{{\rightarrow}}$$a$$(q,a)$$\stackrel{{\scriptstyle q}}{{\leftarrow}}$$a$
Figure 3. The alphabet $\mathcal{W}_{\mathcal{M}}$ associated to a Turing
machine $\mathcal{M}=\\{Q,\Sigma,q_{0},q_{F},\delta\\}$. $a\in\Sigma$ is an
arbitrary symbol and $q\in Q$ is an arbitrary state. $(s,b),(\ell,c),(r,d)\in
Q\times\Sigma$ are any pairs such that
$\delta(s,b)=(s^{\prime},b^{\prime},0)$,
$\delta(\ell,c)=(\ell^{\prime},c^{\prime},-1)$ and
$\delta(r,d)=(r^{\prime},d^{\prime},+1)$.

Given a Turing machine $\mathcal{M}$, we define its associated set of
$\mathbb{N}^{2}$-tilings as the set $\mathcal{T}_{\mathcal{M}}$ of all maps
$\tau\colon\mathbb{N}^{2}\to\mathcal{W}_{\mathcal{M}}$ so that whenever two
tiles are horizontally or vertically adjacent to each other, both the color
and the symbol on their adjacent sides coincide. See Figure 4 for an example
of pattern satisfying this constraint.

######  Remark 5.1.

The $\mathbb{N}^{2}$-tilings which are described by square tiles satisfying
the above kind of constraints are called Wang tilings after Hao Wang, who
introduced them in [49].

The idea behind this construction is that for any $x\in\Sigma^{\mathbb{N}}$,
if we provide a horizontal row of tiles of Figure 3 given by
$\texttt{seed},\texttt{tile}_{1}(x_{0}),\texttt{tile}_{2}(x_{1}),\texttt{tile}_{2}(x_{2}),\texttt{tile}_{2}(x_{3}),\dots$,
then the local rules of the tileset force any configuration to encode the
dynamics of the Turing machine on the infinite word $x$.

######  Example 5.2.

Let us consider the following simple Turing machine. Let $Q=\\{a,b\\}$,
$\Sigma=\\{0,1,\sqcup\\}$, $q_{0}=a$ and let $\delta$ be given by

(1) $\displaystyle\delta(a,\sqcup)$ $\displaystyle=(b,0,+1)$
$\displaystyle\delta(a,0)$ $\displaystyle=(b,1,+1)$ $\displaystyle\delta(a,1)$
$\displaystyle=(a,0,+1)$ (2) $\displaystyle\delta(b,\sqcup)$
$\displaystyle=(a,0,-1)$ $\displaystyle\delta(b,0)$ $\displaystyle=(b,1,0)$
$\displaystyle\delta(b,1)$ $\displaystyle=(a,0,+1).$

A $\mathbb{N}^{2}$-tiling associated to this Turing machine is shown in Figure
4.  $\fullmoon$

$(a,\sqcup)$

$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$0$$\stackrel{{\scriptstyle
b}}{{\rightarrow}}$

$(a,\sqcup)$

$(b,\sqcup)$

$\stackrel{{\scriptstyle
b}}{{\rightarrow}}$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$

$(a,0)$

$\stackrel{{\scriptstyle a}}{{\leftarrow}}$$0$$0$$\stackrel{{\scriptstyle
a}}{{\leftarrow}}$

$(b,\sqcup)$

$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$1$$\stackrel{{\scriptstyle
b}}{{\rightarrow}}$

$(a,0)$

$(b,0)$

$\stackrel{{\scriptstyle
b}}{{\rightarrow}}$$0$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$1$$1$

$(b,1)$

$(b,0)$

$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$1$$1$$0$$\stackrel{{\scriptstyle
a}}{{\rightarrow}}$

$(b,1)$

$(a,\sqcup)$

$\stackrel{{\scriptstyle
a}}{{\rightarrow}}$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$$\sqcup$
Figure 4. A pattern of the Wang tiling associated to the machine of Example
5.2. Each row, starting from the bottom, can be associated to an iteration of
the Turing machine on an empty tape.

######  Remark 5.3.

If the tile seed occurs at position $(0,0)$, then necessarily
$\texttt{tile}_{1}(a)$ occurs at $(1,0)$ for some $a\in\Sigma$, and tiles
$\texttt{tile}_{2}(b_{n})$ for some $b_{n}\in\Sigma$ must occur at every
position $(n,0)$ for $n\geq 2$. The tiles at the remaining positions of
$\mathbb{N}^{2}$ are uniquely determined by these tiles.

Now consider an effectively closed set $Y\subseteq A^{\mathbb{N}}$. By
definition, there exists a Turing machine $\mathcal{M}_{Y}$ so that
$\mathcal{M}_{Y}$ accepts a word $w\in A^{*}$ if and only if $[w]\cap
Y=\varnothing$. Let us consider a new Turing machine
$\mathcal{M}_{\texttt{search},Y}$ whose tape alphabet and behavior we describe
as follows:

  * •

The tape alphabet of $\mathcal{M}_{\texttt{search},Y}$ consists of tuples in
$A\times\Sigma^{\prime}$, where $\Sigma^{\prime}\supset A$ is the working
alphabet of an universal Turing machine which contains a special symbol
$\sqcup$. The symbols in the first component are not modified by the machine,
but can be read.

  * •

The dynamics of $\mathcal{M}_{\texttt{search},Y}$ when run on the sequence
$(y_{n},\sqcup)_{n\in\mathbb{N}}$ are the following:

    1. (1)

Define $k=1$.

    2. (2)

For every word $w\in\bigcup_{j\leq k}A^{j}$, run the Turing machine
$\mathcal{M}_{Y}$ on input $w$ for $k$ steps.

       * –

If $\mathcal{M}_{Y}$ accepts $w$, check whether $y_{0}\dots y_{|w|-1}=w$. If
it is the case, accept (go to state $q_{F}$).

    3. (3)

Redefine $k$ as $k+1$ and go back to step (2).

As $Y$ is effectively closed, it follows that
$\mathcal{M}_{\texttt{search},Y}$ run on the sequence
$(y_{n},\sqcup)_{n\in\mathbb{N}}$ reaches its final state $q_{F}$ if and only
if $(y_{n})_{n\in\mathbb{N}}\notin Y$.

Given $s\in\mathcal{W}_{\mathcal{M}}$, the set of seeded tilings of
$\mathcal{T}_{\mathcal{M}}$ is the set of $\tau\in\mathcal{T}_{\mathcal{M}}$
such that $\tau(0,0)=s$.

######  Definition 5.4.

Let $Y$ be an effectively closed set. The search tilespace
$\mathcal{T}_{\texttt{Search},Y}$ is the set which consists on all seeded
tilings of $\mathcal{T}_{\mathcal{M}_{\texttt{Search},Y}}$ such that

  1. (1)

The seed is given by the tile seed.

  2. (2)

We forbid the tiles $\mathtt{tile}_{1}(a,b)$ and $\mathtt{tile}_{2}(a,b)$
where $b\neq\sqcup$.

  3. (3)

We forbid any tile carrying the final state $q_{F}$.

In simpler words, we keep only tilings associated to the machine
$\mathcal{M}_{\texttt{Search},Y}$ whose bottom row is of the form

$(y_{0},\sqcup)$

$(y_{1},\sqcup)$

$(y_{2},\sqcup)$

$(y_{3},\sqcup)$

$(y_{4},\sqcup)$

$(y_{5},\sqcup)$

$\cdots$

for some $(y_{n})_{n\in\mathbb{N}}\in A^{\mathbb{N}}$. Furthermore, the third
condition imposes that in any such tiling the machine never reaches the
accepting state, that is, we will have that $(y_{n})_{n\in\mathbb{N}}\in Y$.

Next we will define an auxiliary tileset which will be useful in the part of
proof of Theorem 1.2 which deals with the synchronization of the
$\mathbb{N}^{2}$-grids.

######  Definition 5.5.

Let $A$ be a finite alphabet. The synchronization tilespace
$\mathcal{T}_{\texttt{Sync}}$ is the set of tilings
$\sigma\colon\mathbb{N}^{2}\to A$ with the property that

$\sigma(u+(0,1))=\sigma(u+(1,0))\mbox{ for every }u\in\mathbb{N}^{2}.$

In other words, $\mathcal{T}_{\texttt{Sync}}$ consists on all tilings in which
the antidiagonals are constant.

Finally, we use the two previous constructions to define the computation
tileset $\mathcal{T}_{\texttt{Comp},Y}$ of an effectively closed set $Y$ as
follows.

######  Definition 5.6.

The computation tilespace $\mathcal{T}_{\texttt{Comp},Y}$ associated to an
effectively closed set $Y\subseteq A^{\mathbb{N}}$ is the set of maps
$(\tau,\sigma)\in\mathcal{T}_{\texttt{Search},Y}\times\mathcal{T}_{\texttt{Sync}}$
such that for every $u\in\mathbb{N}^{2}$, $i\in\\{1,2\\}$ and $a\in A$, if
$\tau(u+(1,0))=\texttt{tile}_{i}(a,\sqcup)$ then $\sigma(u)=a$.

We shall write down the two important properties of tilings in
$\mathcal{T}_{\texttt{Comp},Y}$ in the following two propositions.

######  Proposition 5.7.

Let $(\tau,\sigma)\in\mathcal{T}_{\texttt{Comp},Y}$. We have that
$(\sigma(0,n))_{n\in\mathbb{N}}=(\sigma(n,0))_{n\in\mathbb{N}}\in Y$.

###### Proof.

Let $(\tau,\sigma)\in\mathcal{T}_{\texttt{Comp},Y}$. From the definition of
$\mathcal{T}_{\texttt{Sync}}$ it follows that $\sigma(0,n)=\sigma(n,0)$ for
all $n\in\mathbb{N}$, therefore it suffices to show that
$(\sigma(n,0))_{n\in\mathbb{N}}\in Y$

By definition of $\mathcal{T}_{\texttt{Search},Y}$, we have
$\tau(0,0)=\texttt{tile}_{1}(a_{0},\sqcup)$ for some $a_{0}\in A$. By the
local rules of the tiling we have that for $n\geq 1$,
$\tau(n,0)=\texttt{tile}_{2}(a_{n})$ for some $a_{n}\in A$. Therefore the
tiling $\tau$ corresponds to the space time diagram of the computation of
$\mathcal{M}_{\texttt{search},Y}$ on the input
$(a_{n},\sqcup)_{n\in\mathbb{N}}$. As we removed the symbol $q_{F}$, it
follows that $(a_{n})_{n\in\mathbb{N}}\in Y$. Since $a_{n}=\sigma(n,0)$ for
every $n\in\mathbb{N}$ by Definition 5.6, we deduce that
$(\sigma(n,0))_{n\in\mathbb{N}}\in Y$. ∎

######  Proposition 5.8.

For every $y\in Y$ there exists
$(\tau,\sigma)\in\mathcal{T}_{\texttt{Comp},Y}$ so that
$y=(\sigma(n,0))_{n\in\mathbb{N}}$

###### Proof.

Fix $y\in Y$. Let $\sigma\in A^{\mathbb{N}^{2}}$ be given by
$\sigma(n-k,k)=y_{n}$ for all $n\in\mathbb{N}$ and $k\leq n$. It is clear that
$\sigma\in\mathcal{T}_{\texttt{Sync}}$.

Since $y\in Y$, it follows that $\mathcal{M}_{\texttt{search},Y}$ on
$(y_{n},\sqcup)_{n\in\mathbb{N}}$ does not reach the state $q_{F}$ and thus,
if we let $\tau$ be the only configuration in
$\mathcal{T}_{\texttt{Search},Y}$ which is compatible with
$(y_{n},\sqcup)_{n\in\mathbb{N}}$, then the pair $(\tau,\sigma)$ satisfies the
constraint of Definition 5.6 with respect to $\sigma$ and therefore
$(\tau,\sigma)\in\mathcal{T}_{\texttt{Comp},Y}$. ∎

In the next step of the proof, we shall overlay the computation tilings in the
grids induced by the paradoxical subshifts in a product of two non-amenable
groups. The role of the synchronization tilespace shall be to allow
communication between these two components.

###  5.2. Proof of Theorem 1.2

For the remainder of the section, let $\Gamma_{H}$, $\Gamma_{V}$ be two
finitely generated non-amenable groups. Fix generating sets $S_{H},S_{V}$ and
let $\Gamma=\Gamma_{H}\times\Gamma_{V}$ be their direct product.

Let $\Gamma\curvearrowright
X\subseteq\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ be an effectively closed
action of $\Gamma$. Consider the following set of generators of $\Gamma$

$S=\left(S_{H}\times\\{1_{\Gamma_{V}}\\}\right)\cup\left(\\{1_{\Gamma_{H}}\\}\times
S_{V}\right).$

Let $A=\\{\mathtt{0},\mathtt{1}\\}^{S}$ and $Y_{\Gamma\curvearrowright
X,S}\subseteq A^{\mathbb{N}}$ be the set representation of
$\Gamma\curvearrowright X$. We recall that $Y_{\Gamma\curvearrowright X,S}$ is
an effectively closed subset of $A^{\mathbb{N}}$ and that, for $s\in S$ and
$y\in Y_{\Gamma\curvearrowright X,S}$, we denote by $\pi_{s}(y)$ the
configuration $(y_{n}(s))_{n}\in X$. For simplicity of notation, and
coherently with the last section, we shall denote $Y_{\Gamma\curvearrowright
X,S}$ simply by $Y$.

By Proposition 4.3, there exist symmetric finite sets $K_{H}\Subset\Gamma_{H}$
and $K_{V}\Subset\Gamma_{V}$ which contain the identity and so that the
paradoxical subshifts defined on $\Gamma_{H}$ and $\Gamma_{V}$ with respect to
$K_{H}$ and $K_{V}$ are nonempty. Let us denote the corresponding paradoxical
subshifts respectively by $\mathbf{P}_{H}$ and $\mathbf{P}_{V}$. Consider
their trivial extensions to $\Gamma$ as follows

$\displaystyle\widetilde{\mathbf{P}}_{H}$
$\displaystyle=\\{\rho\in(A_{K_{H}})^{\Gamma}:\left(\rho(g,1_{\Gamma_{V}})\right)_{g\in\Gamma_{H}}\in\mathbf{P}_{H}\mbox{
and }\rho(g,g^{\prime})=\rho(g,1_{\Gamma_{V}})\mbox{ for every
}(g,g^{\prime})\in\Gamma\\}$ $\displaystyle\widetilde{\mathbf{P}}_{V}$
$\displaystyle=\\{\rho^{\prime}\in(A_{K_{V}})^{\Gamma}:\left(\rho^{\prime}(1_{\Gamma_{H}},g)\right)_{g\in\Gamma_{V}}\in\mathbf{P}_{V}\mbox{
and
}\rho^{\prime}(g,g^{\prime})=\rho^{\prime}(1_{\Gamma_{H}},g^{\prime})\mbox{
for every }(g,g^{\prime})\in\Gamma\\},$

It is clear that $\widetilde{\mathbf{P}}_{H}$ and $\widetilde{\mathbf{P}}_{V}$
are both $\Gamma$-subshifts of finite type. Consider the $\Gamma$-subshift of
finite type
$\widetilde{\mathbf{P}}=\widetilde{\mathbf{P}}_{H}\times\widetilde{\mathbf{P}}_{V}$.
It follows that for every $\widetilde{g}=(g,g^{\prime})\in\Gamma$ there exists
a continuous map
$\gamma_{\widetilde{g}}\colon\mathbb{N}^{2}\times\widetilde{\mathbf{P}}\to\Gamma$
given by

$\gamma_{\widetilde{g}}((n,n^{\prime}),(\rho,\rho^{\prime}))=\left(\gamma^{H}_{g}(n,\rho),\gamma^{V}_{g^{\prime}}(n^{\prime},\rho^{\prime})\right).$

Where $\gamma^{H}$ and $\gamma^{V}$ are the maps defined in Section 4 which
are determined by the restrictions of $\rho$ and $\rho^{\prime}$ to
$\Gamma_{H}\times\\{1_{V}\\}$ and to $\\{1_{\Gamma_{H}}\\}\times\Gamma_{V}$
respectively.

It follows from Lemma 4.5 that for every ${\rho}\in\widetilde{\mathbf{P}}$ the
map $(u,\widetilde{g})\mapsto\gamma_{\widetilde{g}}(u,{\rho})$ is injective,
where $u\in\mathbb{N}^{2}$ and $\widetilde{g}\in\Gamma$.

Recall that the computation tilespace $\mathcal{T}_{\texttt{Comp},Y}$ is a
subset of all tuples
$(\tau,\sigma)\in\mathcal{T}_{\texttt{Search},Y}\times\mathcal{T}_{\texttt{Sync}}$.
Denote by $B$ the alphabet of all tiles which occur in some tiling in
$\mathcal{T}_{\texttt{Search},Y}$. Also recall that given
$\mathtt{t}\in\\{\mathtt{G},\mathtt{B}\\}$, $\overline{\mathtt{t}}$ denotes
the opposite color. For $\rho\in\widetilde{\mathbf{P}}$, write
$\rho=({\rho}_{H},{\rho}_{V})\in\widetilde{\mathbf{P}}_{H}\times\widetilde{\mathbf{P}}_{V}$.
Denote also by $\mathtt{t}_{H}(g)$,$\mathtt{t}_{V}(g)$ the colors of
${\rho}_{H}(g)$ and ${\rho}_{V}(g)$ respectively.

######  Definition 5.9.

The final $\Gamma$-subshift $Z_{\texttt{Final}}$ is the set of configurations
$z=(\rho,\tau,\sigma)\in\widetilde{\mathbf{P}}\times B^{\Gamma}\times
A^{\Gamma}$ which satisfy the following constraints:

  1. (1)

Embedding rule: For every $g\in\Gamma$, $z$ respects the local rules of
$\mathcal{T}_{\texttt{Comp},Y}$. More precisely, for every $g\in\Gamma$,

    1. (a)

$\tau(gL_{\overline{\mathtt{t}_{H}(g)}}(\rho_{H}(g)),gL_{\overline{\mathtt{t}_{V}(g)}}(\rho_{V}(g)))=\texttt{seed}$.

    2. (b)

The right side of the tile $\tau(g)$ coincides with the left side of the tile
$\tau(gL_{{\mathtt{t}_{H}(g)}}(\rho_{H}(g)))$.

    3. (c)

The upper side of the tile $\tau(g)$ coincides with the bottom side of the
tile $\tau(gL_{{\mathtt{t}_{V}(g)}}(\rho_{V}(g)))$.

    4. (d)

$\sigma(gL_{{\mathtt{t}_{H}(g)}}(\rho_{H}(g)))=\sigma(gL_{{\mathtt{t}_{V}(g)}}(\rho_{V}(g)))$.

    5. (e)

If $\tau(gL_{{\mathtt{t}_{H}(g)}}(\rho_{H}(g)))=\texttt{tile}_{i}(a,\sqcup)$
for some $a\in A$, then $\sigma(g)=a$.

  2. (2)

Coherence rule: For every $g\in\Gamma$,

    1. (a)

For every $s\in S_{H}\times\\{1_{\Gamma_{V}}\\}$,

$\sigma(gL_{\overline{\mathtt{t}_{H}}}(\rho_{H}(g)))(s)=\sigma(gs^{-1}L_{\overline{\mathtt{t}_{H}(gs^{-1})}}(\rho_{H}(gs^{-1})))(1_{\Gamma}).$

    2. (b)

For every $s^{\prime}\in\\{1_{\Gamma_{H}}\\}\times S_{V}$,

$\sigma(gL_{\overline{\mathtt{t}_{V}}}(\rho_{V}(g)))(s^{\prime})=\sigma(gs^{\prime-1}L_{\overline{\mathtt{t}_{V}(gs^{\prime-1})}}(\rho_{V}(gs^{\prime-1})))(1_{\Gamma}).$

The following proposition translates the technical description of
$Z_{\texttt{Final}}$ into the properties we shall use to prove our result.

######  Proposition 5.10.

$Z_{\texttt{Final}}$ is a $\Gamma$-subshift of finite type which satisfies:

  1. (1)

For every $g\in\Gamma$,

$\left(\tau(\gamma_{g}(u,\rho)),\sigma(\gamma_{g}(u,\rho))\right)_{u\in\mathbb{N}^{2}}\in\mathcal{T}_{\texttt{Comp},Y}.$

  2. (2)

For every $g\in\Gamma$, $s\in S$ and $u\in\mathbb{N}^{2}$ we have

$\sigma(\gamma_{g}(u,\rho))(s)=\sigma(\gamma_{gs^{-1}}(u,\rho))(1_{\Gamma}).$

In other words, a configuration $z=(\rho,\tau,\sigma)$ in $Z_{\texttt{Final}}$
satisfies that (1) for every $g\in\Gamma$, the restriction of $(\rho,\tau)$ to
the $\mathbb{N}^{2}$-grid $\gamma_{g}(\mathbb{N}^{2},\rho)$ is a valid seeded
tiling of $\mathcal{T}_{\texttt{Comp},Y}$, and (2), when moving by a generator
$s$ of $\Gamma$, the component $\pi_{s}(y)$ of the element $y\in Y$ read from
the grid of $g$ coincides with the component $\pi_{1_{\Gamma}}(y^{\prime})$ of
the element $y^{\prime}\in Y$ read from the grid at $gs^{-1}$.

###### Proof.

From the definition of $Z_{\texttt{Final}}$ it is clear that it is a
$\Gamma$-subshift of finite type. Indeed, $\widetilde{\mathbf{P}}$ is a
$\Gamma$-subshift of finite type and all of the other rules are clearly local.

Let $z=(\rho,\tau,\sigma)\in Z_{\texttt{Final}}$ and fix $g\in\Gamma$. In
order to prove the first property, notice that the element
$\gamma_{g}((0,0),\rho)$ is given by the pair

$\gamma_{g}((0,0),\rho)=(gL_{\overline{\mathtt{t}_{H}(g)}}({\rho}_{H}(g)),gL_{\overline{\mathtt{t}_{V}(g)}}({\rho}_{V}(g))).$

Therefore rule (1a) is stating that
$\tau(\gamma_{g}((0,0),\rho))=\texttt{seed}$. Similarly, the positions
$gL_{{\mathtt{t}_{H}(g)}}(\rho_{H}(g))$ and
$gL_{{\mathtt{t}_{V}(g)}}(\rho_{V}(g))$ are respectively the ones directly
right and up from position $g$, therefore rules (1b) and (1c) implement the
local rules of a Wang tileset, namely, that colors must match horizontally and
vertically. As we let $B$ be the set of all tiles which occur in
$\mathcal{T}_{\texttt{Search},Y}$, these three rules already imply that
$\left(\tau(\gamma_{g}(u,\rho))\right)_{u\in\mathbb{N}^{2}}\in\mathcal{T}_{\texttt{Search},Y}.$

The same argument as above shows that rule (1d) implements the fact that
antidiagonals are constant in $\mathcal{T}_{\texttt{Sync}}$ and (1e) gives the
rule that defines $\mathcal{T}_{\texttt{Comp},Y}$. From here it follows that
rules (1a)-(1e) imply that
$\left(\tau(\gamma_{g}(u,\rho)),\sigma(\gamma_{g}(u,\rho))\right)_{u\in\mathbb{N}^{2}}\in\mathcal{T}_{\texttt{Comp},Y}$.

Let us now show the second property. Let $s\in S$. Given
$(n,n^{\prime})\in\mathbb{N}^{2}$, we need to show that

$\sigma(\gamma_{g}((n,n^{\prime}),\rho))(s)=\sigma(\gamma_{gs^{-1}}((n,n^{\prime}),\rho))(1_{\Gamma}).$

By definition of $S$, either $s\in S_{H}\times\\{1_{\Gamma_{V}}\\}$ or
$s\in\\{1_{\Gamma_{H}}\\}\times S_{V}$. Suppose $s\in
S_{H}\times\\{1_{\Gamma_{V}}\\}$. By definition of
$\mathcal{T}_{\texttt{Sync}}$ it suffices to show that for every
$m\in\mathbb{N}$,

$\sigma(\gamma_{g}((0,m),\rho))(s)=\sigma(\gamma_{gs^{-1}}((0,m),\rho))(1_{\Gamma}).$

Write $g=(g_{1},g_{2})$ and note that,

$\displaystyle\gamma_{g}((0,m),\rho)$
$\displaystyle=(\gamma^{H}_{g_{1}}(0,\rho_{H}),\gamma^{V}_{g_{2}}(m,\rho_{V}))$
$\displaystyle=(g_{1}L_{\overline{\mathtt{t}_{H}(g)}}({\rho}_{H}(g)),\gamma^{V}_{g_{2}}(m,\rho_{V}))$
$\displaystyle=(g_{1},\gamma^{V}_{g_{2}}(m,\rho_{V}))L_{\overline{\mathtt{t}_{H}(g)}}({\rho}_{H}(g)).$

and

$\displaystyle\gamma_{gs^{-1}}((0,m),\rho)$
$\displaystyle=(\gamma^{H}_{g_{1}s^{-1}}(0,\rho_{H}),\gamma^{V}_{g_{2}}(m,\rho_{V}))$
$\displaystyle=(g_{1}s^{-1}L_{\overline{\mathtt{t}_{H}(gs^{-1})}}({\rho}_{H}(gs^{-1})),\gamma^{V}_{g_{2}}(m,\rho_{V}))$
$\displaystyle=(g_{1},\gamma^{V}_{g_{2}}(m,\rho_{V}))s^{-1}L_{\overline{\mathtt{t}_{H}(gs^{-1})}}({\rho}_{H}(gs^{-1})).$

From rule (2a), we deduce that

$\displaystyle[\sigma(\gamma_{g}((0,m),\rho))](s)$
$\displaystyle=[\sigma((g_{1},\gamma^{V}_{g_{2}}(m,\rho_{V}))L_{\overline{\mathtt{t}_{H}(g)}}({\rho}_{H}(g)))](s)$
$\displaystyle=[\sigma((g_{1},\gamma^{V}_{g_{2}}(m,\rho_{V}))s^{-1}L_{\overline{\mathtt{t}_{H}(gs^{-1})}}({\rho}_{H}(gs^{-1})))](1_{\Gamma})$
$\displaystyle=[\sigma(\gamma_{gs^{-1}}((0,m),\rho))](1_{\Gamma}).$

Which is exactly what we wanted. An analogous argument using property (2b)
shows that if $s^{\prime}\in\\{1_{\Gamma_{H}}\\}\times S_{V}$, then for every
$m\in\mathbb{N}$

$\sigma(\gamma_{g}((m,0),\rho))(s^{\prime})=\sigma(\gamma_{gs^{\prime-1}}((m,0),\rho))(1_{\Gamma}).$

Again, by the definition of $\mathcal{T}_{\texttt{Sync}}$ this is enough to
obtain what we want.∎

Finally, consider the map

$\begin{array}[]{crcl}\phi\colon&Z_{\texttt{Final}}&\longrightarrow&\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}\\\
&(\rho,\tau,\sigma)&\longmapsto&\left(\sigma(\gamma_{1_{\Gamma}}((n,0),\rho))(1_{\Gamma})\right)_{n\in\mathbb{N}}\end{array}$

We will show that $\phi$ is a topological factor map from
$\Gamma\curvearrowright Z_{\texttt{Final}}$ to $\Gamma\curvearrowright X$. It
is clear from the definition that $\phi$ is a continuous map.

######  Claim 5.11.

$\phi(Z_{\texttt{Final}})\subseteq X$.

###### Proof.

Let $(\rho,\tau,\sigma)\in Z_{\texttt{Final}}$. By the embedding rule, we have
that
$(\tau(\gamma_{1_{\Gamma}}(u,\rho)),\sigma(\gamma_{1_{\Gamma}}(u,\rho)))_{u\in\mathbb{N}^{2}}\in\mathcal{T}_{\texttt{comp},Y}$.
By Proposition 5.7, we deduce that
$\left(\sigma(\gamma_{1_{\Gamma}}((n,0),\rho))\right)_{n\in\mathbb{N}}\in Y$.
Thus $\phi(\rho,\tau,\sigma)\in X$. ∎

######  Claim 5.12.

$\phi$ is $\Gamma$-equivariant.

###### Proof.

Let $s\in S$ and $(\rho,\tau,\sigma)\in Z_{\texttt{Final}}$. We have

$\displaystyle s\phi(\rho,\tau,\sigma)$
$\displaystyle=s\left(\sigma(\gamma_{1_{\Gamma}}((n,0),\rho)(1_{\Gamma})\right)_{n\in\mathbb{N}}$
$\displaystyle=\left(\sigma(\gamma_{1_{\Gamma}}((n,0),\rho)(s)\right)_{n\in\mathbb{N}}$
$\displaystyle=\left(\sigma(\gamma_{s^{-1}}((n,0),\rho)(1_{\Gamma})\right)_{n\in\mathbb{N}}$
$\displaystyle=\left(\sigma(s^{-1}\gamma_{1_{\Gamma}}((n,0),s\rho)(1_{\Gamma})\right)_{n\in\mathbb{N}}$
$\displaystyle=\left(s\sigma(\gamma_{1_{\Gamma}}((n,0),s\rho)(1_{\Gamma})\right)_{n\in\mathbb{N}}$
$\displaystyle=\phi(s\rho,s\tau,s\sigma).$

Since $S$ is a generating set for $\Gamma$, it follows that
$g\phi(\rho,\tau,\sigma)=\phi(g\rho,g\tau,g\sigma)$ for any $g\in\Gamma$ and
thus $\phi$ is $\Gamma$-equivariant.∎

######  Claim 5.13.

$\phi$ is surjective.

###### Proof.

Fix $\rho\in\widetilde{\mathbf{P}}$. Let $\mathcal{R}\subseteq\Gamma$ be the
set of reachable $r\in\Gamma$ for which there is $g\in\Gamma$ and
$u\in\mathbb{N}^{2}$ such that $r=\gamma_{g}(u,\rho)$. Since the map
$(g,u)\mapsto\gamma_{g}(u,\rho)$ is injective (by Lemma 4.5), we may denote
unambiguously these values by $u(r)$ and $g(r)$ for $r\in\mathcal{R}$.

Consider an arbitrary $x=(x_{n})_{n\in\mathbb{N}}\in X$ and let
$y=(y_{n})_{n\in\mathbb{N}}\in Y$ such that $y_{n}(1_{\Gamma})=x_{n}$ for
every $n\in\mathbb{N}$. Consider the natural action $\Gamma\curvearrowright Y$
such that $(gy)_{n}(1_{\Gamma})=(g(y_{n}(1_{\Gamma}))_{n\in\mathbb{N}})_{n}$
for every $y\in Y$ and $g\in\Gamma$. By Proposition 5.8, for every
$g\in\Gamma$ there exists
$(\tau^{g},\sigma^{g})\in\mathcal{T}_{\texttt{Comp},Y}$ so that
$\sigma^{g}(n,0)=(g^{-1}y)_{n}$ for every $n\in\mathbb{N}$.

Let us fix $a_{0}\in A$ and $w_{0}\in B$ given by

$\leavevmode\hbox to91.83pt{\vbox
to53.45pt{\pgfpicture\makeatletter\hbox{\hskip
66.01828pt\lower-26.72516pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-62.01868pt}{-1.50067pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$w_{0}=$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@moveto{-25.60751pt}{-25.60751pt}\pgfsys@moveto{-25.60751pt}{-25.60751pt}\pgfsys@lineto{-25.60751pt}{25.60751pt}\pgfsys@lineto{25.60751pt}{25.60751pt}\pgfsys@lineto{25.60751pt}{-25.60751pt}\pgfsys@closepath\pgfsys@moveto{25.60751pt}{25.60751pt}\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{
}{}{{}}{} {}{} {}{} {}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{-25.60751pt}{25.60751pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@lineto{-25.60751pt}{-25.60751pt}\pgfsys@closepath\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{} {}{} {}{}
{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{-25.60751pt}{-25.60751pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@lineto{25.60751pt}{-25.60751pt}\pgfsys@closepath\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{} {}{} {}{}
{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{25.60751pt}{-25.60751pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@lineto{25.60751pt}{25.60751pt}\pgfsys@closepath\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{} {}{} {}{}
{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{25.60751pt}{25.60751pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@lineto{-25.60751pt}{25.60751pt}\pgfsys@closepath\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{
{}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-12.14792pt}{15.52557pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\scalebox{0.8}{{($a_{0},\sqcup$)}}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-12.14792pt}{-20.32556pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{\scalebox{0.8}{{($a_{0},\sqcup$)}}}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>
Let us define $\tau\in B^{\Gamma}$ and $\sigma\in A^{\Gamma}$ as follows.

$\tau(h)=\begin{cases}\tau^{g(h)}(u(h))&\mbox{ if }h\in\mathcal{R}.\\\
w_{0}&\mbox{ if }h\notin\mathcal{R}.\end{cases}$
$\sigma(h)=\begin{cases}\sigma^{g(h)}(u(h))&\mbox{ if }h\in\mathcal{R}.\\\
a_{0}&\mbox{ if }h\notin\mathcal{R}.\end{cases}$

By construction, it follows that

$\phi(\rho,\tau,\sigma)=\left(\sigma(\gamma_{1_{\Gamma}}((n,0),\rho)(1_{\Gamma})\right)_{n\in\mathbb{N}}=(\sigma^{1_{\Gamma}}(n,0)(1_{\Gamma}))_{n\in\mathbb{N}}=(y_{n}(1_{\Gamma}))_{n\in\mathbb{N}}=(x_{n})_{n\in\mathbb{N}}.$

It suffices to check that $(\rho,\tau,\sigma)\in Z_{\texttt{Final}}$. It is
straightforward to check that the embedding rule holds. Let us check the
coherence rule, let $g\in G,s\in S$ and $(n,n^{\prime})\in\mathbb{N}^{2}$. On
the one hand we have

$\sigma(\gamma_{g}((n,n^{\prime}),\rho))=\sigma^{g}(n,n^{\prime})=\sigma^{g}(n+n^{\prime},0)=(g^{-1}y)_{n+n^{\prime}}.$

On the other hand we have

$\sigma(\gamma_{gs^{-1}}((n,n^{\prime}),\rho))=\sigma^{gs^{-1}}(n,n^{\prime})=\sigma^{gs^{-1}}(n+n^{\prime},0)=(sg^{-1}y)_{n+n^{\prime}}.$

We obtain that

$\sigma(\gamma_{g}((n,n^{\prime}),\rho))(s)=(g^{-1}y)_{n+n^{\prime}}(s)=(sg^{-1}y)_{n+n^{\prime}}(1_{\Gamma})=\sigma(\gamma_{gs^{-1}}((n,n^{\prime}),\rho))(1_{\Gamma}).$

Which is the coherence rule. It follows that $(\rho,\tau,\sigma)\in
Z_{\texttt{Final}}$ and thus $\phi$ is surjective.∎

Putting together Claims 5.11, 5.12 and 5.13 we have that $\phi\colon
Z_{\texttt{Final}}\to X$ is a topological factor map. By Claim 5.10
$Z_{\texttt{Final}}$ is a $\Gamma$-SFT. This completes the proof of Theorem
1.2.

##  6\. Extensions of self-simulable groups

The goal of this section is to study conditions under which a group $\Gamma$,
which contains in some form a self-simulable group $\Delta$, is self-
simulable. Our main result is that if $\Gamma$ is recursively presented and
the “adjacent” cosets of a subgroup $\Delta$ under a suitable generating set
$T$ of $\Gamma$ have “enough space to communicate”, then $\Gamma$ is also
self-simulable. Intuitively, in order to communicate an entire configuration
between elements $g$ and $gt$ of $\Gamma$ we need that the cosets $g\Delta$
and $gt\Delta$ are “close” in infinitely many places. Our endeavor will be to
find algebraic conditions which ensure that the former property holds. Let us
mention that normality of $\Delta$ is enough, and we shall indeed give a less
restrictive property which we call “mediation”. See Definition 6.7.

######  Example 6.1.

Let us notice that the sole property of $\Gamma$ admitting a self-simulable
subgroup is not enough for $\Gamma$ to be self-simulable. For instance, if
$\Gamma=(F_{2}\times F_{2})\ast F_{2}$, where $\ast$ denotes the free product,
we have that $\Gamma$ admits the self-simulable subgroup $F_{2}\times F_{2}$,
however, by Proposition 3.4 it is not simulable because it has infinitely many
ends. $\fullmoon$

As in the previous section, we shall encode elements of $A^{\mathbb{N}}$ on
infinite paths, and use copies of the paradoxical subshift to communicate
these elements along different paths. Therefore, it will be natural to assume
that $\Delta$ admits a covering by paths such that for the path
$p\colon\mathbb{N}\to\Delta$ starting at $h\in\Delta$, $n\mapsto p(n)t$ gives
a path in $ht\Delta$. We shall call those coverings $t$-media111Since a
$t$-medium allows communication of a paradoxical nature, “$t$-mediums” may
also be an acceptable plural..

In Section 4, we avoided the discussion of some technicalities associated to
the paradoxical subshift $\mathbf{P}$ as they were not necessary in the proof
of Theorem 1.2. In this section, we shall require the existence of
configurations in the paradoxical subshift with special properties. To this
end, we shall make the correspondence between elements of $\mathbf{P}$ and
path covers slightly more explicit.

Recall that given a color $\mathtt{t}\in\\{\mathtt{G},\mathtt{B}\\}$, we
denote by $\overline{\mathtt{t}}$ the other color.

######  Definition 6.2.

Let $\Delta$ be a group. A path cover with moves $K\Subset\Delta$ is a
collection of maps $(p_{h})_{h\in\Delta}$ called paths, where
$p_{h}\colon\mathbb{N}\to\Delta$ is injective, satisfies $p_{h}(0)=h$ and
$p_{h}(n)^{-1}p_{h}(n+1)\in K$ for all $h\in\Delta,n\in\mathbb{N}$, and every
$h\in\Delta$ is in the range of at most two paths.

We say a path cover is full if every $h\in\Delta$ is in the range of two
paths, and colored if it comes with a partition $\Delta$ into
$\Delta_{\mathtt{G}},\Delta_{\mathtt{B}}$ such that whenever
$h\in\Delta_{\mathtt{t}}$ for $\mathtt{t}\in\\{\mathtt{G},\mathtt{B}\\}$, then
for every $n\in\mathbb{N}$ we have that
$p_{h}(n+1)\in\Delta_{\overline{\mathtt{t}}}$.

By definition, $p_{h}$ always has $h$ in its range, so the condition that $h$
is in the range of at most (resp. exactly) two paths says precisely that $h$
appears as an intermediate node in at most (resp. exactly) one path. Notice
that if $\rho\in\mathbf{P}$ is a configuration in the Paradoxical subshift
associated to some $K\Subset\Delta$, and $(\gamma_{h})_{h\in\Delta}$ are the
maps defined in Section 4, then the collection of maps $(p_{h})_{h\in\Delta}$
given by

$p_{h}(0)=h\mbox{ and }p_{h}(n)=\gamma_{h}(n-1,\rho)\mbox{ for every }n\geq
1,$

is a colored path cover with moves in $K$ which we call the path cover induced
by $\rho$. It might not necessarily be a full path cover.

######  Remark 6.3.

If there exists a $2$-to-$1$ map $\varphi\colon\Delta\to\Delta$ such that for
every $g\in\Delta$, $g^{-1}\varphi(g)\in K\Subset\Delta$ with $K$ symmetric,
then there is a $2$-to-$1$ map $\widetilde{\varphi}\colon\Delta\to\Delta$ such
that for every $g\in\Delta$, $g^{-1}\widetilde{\varphi}(g)\in
K^{2}\setminus\\{1_{\Delta}\\}$. Indeed, let $L\subseteq\Delta$ be the set of
$g\in\Delta$ for which $\varphi(g)=g$. As the map is $2$-to-$1$, for every
$g\in L$ we can choose elements $g^{\prime},g^{\prime\prime}$ such that
$\\{g,g^{\prime},g^{\prime\prime}\\}$ are all distinct,
$\varphi(g^{\prime})=g$ and $\varphi(g^{\prime\prime})=g^{\prime}$. We can
then define $\widetilde{\varphi}$ as follows

$\widetilde{\varphi}(h)=\begin{cases}g^{\prime}&\mbox{ if }g\in L,\\\ g&\mbox{
if }h=g^{\prime\prime}\mbox{ for some }g\in L,\\\ \varphi(h)&\mbox{ otherwise.
}\end{cases}$

Clearly $g^{-1}\widetilde{\varphi}(g)\in K^{2}\setminus\\{1_{\Delta}\\}$. In
other words, by choosing a suitable symmetric set we may always assume that
the $2$-to-$1$ map has no fixed points and thus we may remove the identity
from the set of moves.

Given a configuration $\rho\in\mathbf{P}$, we may extract a $2$-to-$1$ map
$\varphi_{\rho}\colon\Delta\to\Delta$ and a color function
$\mathtt{C}_{\rho}\colon\Gamma\to\\{\mathtt{G},\mathtt{B}\\}$ by letting
$\varphi_{\rho}(h)=hR_{\mathtt{t}}(\rho(h))$ and
$\mathtt{C}_{\rho}(h)=\mathtt{t}(\rho(h))$ for every $h\in\Delta$.

######  Definition 6.4.

Let $\mathbf{P}$ be a paradoxical subshift in $\Delta$ and let
$\rho\in\mathbf{P}$. Let $\varphi_{\rho}$ and $\mathtt{C}_{\rho}$ as above. We
say $\rho$ is well-founded if for every $h\in\Delta$ there is $n\geq 1$ such
that $\mathtt{C}_{\rho}(\varphi_{\rho}^{n}(h))\neq\mathtt{C}_{\rho}(h)$.

In simpler words, a configuration $\rho\in\mathbf{P}$ is well-founded if for
every element of $\Delta$, following the function $\varphi_{\rho}$ eventually
leads to a distinct color. In particular, this means that there are no loops,
monochromatic cycles or monochromatic infinite paths. Clearly, if $\rho$ is
well-founded, then the path cover induced by $\rho$ is colored and full.

######  Lemma 6.5.

Let $\mathbf{P}$ be the paradoxical subshift in $\Delta$ defined by some
symmetric set $K\not\ni 1_{\Delta}$. If $\mathbf{P}\neq\emptyset$, then it
contains a well-founded configuration.

###### Proof.

Let $\rho\in\mathbf{P}$. We say that $h\in\Delta$ is in a monochromatic cycle
of $\rho$ if there is a smallest $n\geq 1$ such that $\varphi_{\rho}^{n}(h)=h$
and for every $0\leq i\leq n-1$ we have
$\mathtt{C}_{\rho}(\varphi_{\rho}^{i}(h))=\mathtt{C}_{\rho}(h)$. Notice that
we always have $n\geq 2$, as $1_{\Delta}\not\in K$. We first show that we can
find a configuration with no monochromatic cycles. Indeed, suppose there is
$h\in\Delta$ in a monochromatic cycle. Let $h^{\prime}\neq h$ such that
$\varphi_{\rho}(h^{\prime})=\varphi_{\rho}(h)$ and swap the colors of
$h^{\prime}$ and $h$. That is, modify the color function $\mathtt{C}_{\rho}$
to a function $\widetilde{\mathtt{C}}$ such that
$\widetilde{\mathtt{C}}(h^{\prime})=\mathtt{C}_{\rho}(h)$ and
$\widetilde{\mathtt{C}}(h)=\mathtt{C}_{\rho}(h^{\prime})$ and is equal to
$\mathtt{C}_{\rho}$ everywhere else. As $n\geq 2$ it follows that $h$ is no
longer in a monochromatic cycle, and no new monochromatic cycles were
constructed.

Given $\rho\in\mathbf{P}$ and $h\in\Delta$, let $\rho_{h}$ be the
configuration such that $\rho_{h}=\rho$ if $h$ is not in a monochromatic
cycle, and such that $\rho_{h}$ is the configuration with the colors of the
incoming edges of $\varphi_{\rho}(h)$ swapped as described above if $h$ is in
a monochromatic cycle. Clearly $\rho_{h}\in\mathbf{P}$. Letting
$(h_{k})_{k\in\mathbb{N}}$ be an enumeration of $\Delta$, $\rho^{(0)}=\rho$
and $\rho^{(k)}=(\rho^{(k-1)})_{h_{k-1}}$ for $k\geq 1$, it follows that none
of the elements $h_{0},\dots,h_{k-1}$ are in monochromatic cycles in
$\rho^{(k)}$. Any accumulation point of the sequence
$(\rho^{(k)})_{k\in\mathbb{N}}$ gives a configuration in $\mathbf{P}$ where no
$h\in\Delta$ is in a monochromatic cycle.

Notice that the set $\mathbf{P}^{\otimes}$ of all $\rho\in\mathbf{P}$ where no
$h\in\Delta$ is in a monochromatic cycle is closed and nonempty. Therefore, in
order to obtain a well-founded configuration, it suffices to show that, for
every $h\in\Delta$, the set of $\rho\in\mathbf{P}^{\otimes}$ for which there
is $n\geq 1$ such that
$\mathtt{C}_{\rho}(\varphi_{\rho}^{n}(h))\neq\mathtt{C}_{\rho}(h)$ is a dense
open set. Indeed, as $\Delta$ is countable, by the Baire category theorem we
would have that the intersection of these dense open sets would be a dense
$G_{\delta}$ set, therefore nonempty.

Fix $h\in\Delta$ and denote by $U_{h}$ the set of all
$\rho\in\mathbf{P}^{\otimes}$ such that there is $n\geq 1$ such that
$\mathtt{C}_{\rho}(\varphi_{\rho}^{n}(h))\neq\mathtt{C}_{\rho}(h)$. It is
clear that $U_{h}$ is an open set in $\mathbf{P}^{\otimes}$ (it is a union of
cylinder sets). Let us show that $U_{h}$ is dense. Let
$\rho\in\mathbf{P}^{\otimes}$ and $F\Subset\Delta$. If $\rho\in U_{h}$ we are
done, otherwise, we have that
$\mathtt{C}_{\rho}(\varphi_{\rho}^{n}(h))=\mathtt{C}_{\rho}(h)$ for every
$n\geq 1$ and as there are no monochromatic cycles in $\rho$, we conclude that
the elements $\varphi_{\rho}^{n}(h)$ are all distinct. Therefore there is
$\bar{n}\in\mathbb{N}$ such that for every $s\in F$,
$\varphi_{\rho}(s)\neq\varphi_{\rho}^{\bar{n}}(h)$.

Let $u\in\Delta$ such that $\varphi(u)=\varphi^{\bar{n}}(h)$ and
$u\neq\varphi^{\bar{n}-1}(h)$. By the previous argument we have $u\notin F$.
Let $\rho^{*}$ be the configuration where the colors of
$\varphi^{\bar{n}-1}(h)$ and $u$ are swapped. As the forward path from
$\varphi^{\bar{n}}(h)$ is monochromatic and infinite, it follows that no
monochromatic cycles occur in $\rho^{*}$, thus
$\rho^{*}\in\mathbf{P}^{\otimes}$. Furthermore,
$C_{\rho^{*}}(\varphi_{\rho^{*}}^{\bar{n}-1}(h))\neq C_{\rho^{*}}(h)$,
therefore $\rho^{*}\in U_{h}$. Finally, as no modifications were introduced in
$F$, we have that $\rho^{*}\in[\rho|_{F}]$. As $\rho$ and $F$ were arbitrary,
this shows that $U_{h}$ is dense in $\mathbf{P}^{\otimes}$.∎

######  Lemma 6.6.

Let $\Delta$ be a group and $K\Subset\Delta$ a symmetric set with $K\not\ni
1$.

  * •

If the paradoxical subshift $\mathbf{P}$ is constructed with moves $K$, then
$\mathbf{P}$ is nonempty if and only if there is a full and colored path cover
of $\Delta$ with moves $K$.

  * •

If there is a path cover of $\Delta$ with moves $K$, then there is a full and
colored path cover of $\Delta$ with moves $K^{2}\setminus\\{1_{\Delta}\\}$.

###### Proof.

We begin with the first item. Suppose $\mathbf{P}$ is nonempty. By Lemma 6.5,
we can find a well-founded configuration $\rho\in\mathbf{P}$. As discussed
before, it is clear the path cover of $\Delta$ induced by $\rho$ is full,
colored and uses moves in $K$. Conversely, if $\Delta$ has a full and colored
path cover with moves $K$, then it gives a (well-founded) configuration of
$\mathbf{P}$ in an obvious way: for every $h\in\Delta$ of color $\mathtt{t}$
we have $L_{\mathtt{t}}(h)=h^{-1}p_{h}(1)$, and for $n\geq 2$ we have
$L_{\overline{\mathtt{t}}}(p_{h}(n-1))=p_{h}(n-1)^{-1}p_{h}(n)$. Notice that
this also determines the value of $R_{\mathtt{t}}$ uniquely.

For the second item, from a path cover with moves $K$ we can construct a full
and colored path cover with the moves $K^{2}\setminus\\{1_{\Delta}\\}$ as
follows: First, to ensure the path cover is full, we make sure that every node
$h^{\prime}$ is an intermediate node of one of the paths $p_{h}$ for some
$h\in\Delta$. To do this, whenever $h^{\prime}$ is not already an intermediate
node of any path, pick $h\in\Delta$ such that $h^{\prime}\in hK$ and change
the path $p_{h}$ into a path $\widetilde{p}_{h}$ such that
$\widetilde{p}_{h}(1)=h^{\prime}$ and $\widetilde{p}_{h}(n)=p_{h}(n-1)$ for
$n\geq 2$. Notice that as long as $h^{-1}p(1)\in K$ and the rest of the moves
of $p_{h}$ are in $K^{2}\setminus\\{1_{\Delta}\\}$, then
$h^{-1}\widetilde{p}_{h}(1)=h^{-1}h^{\prime}\in K$ and the rest of the moves
of $\widetilde{p}_{h}$ are in $K^{2}\setminus\\{1_{\Delta}\\}$. Notice a fixed
$h\in\Delta$ can be chosen for at most $|K|$ elements of $\Delta$, therefore
the path $p_{h}$ gets modified finitely many times. Therefore if we iterate
this process over all $h^{\prime}\in\Delta$ which are not an intermediate node
of any path, we end up with a full path cover.

From a full path cover with moves in $K^{2}\setminus\\{1\\}$ it is easy to
obtain a coloring of $\Delta$ which is consistent with the path cover through
a compactness argument. ∎

Now we are ready to give the algebraic definition of the class of groups on
which our extension scheme applies.

######  Definition 6.7.

A subgroup $\Delta\leqslant\Gamma$ is called mediated if there exists a finite
generating set $T$ of $\Gamma$ such that for every $t\in T$ the subgroup
$\Delta\cap t\Delta t^{-1}$ is nonamenable.

This algebraic definition is justified in the following definition and
proposition.

######  Definition 6.8.

Let $\Delta\leqslant\Gamma$ and $t\in\Gamma$. A $t$-medium (on $\Delta$) is a
path cover $(p_{h})_{h\in\Delta}$ with moves $K\Subset\Delta$ such that
$K^{t}=t^{-1}Kt\subseteq\Delta$.

######  Proposition 6.9.

A subgroup $\Delta\leqslant\Gamma$ is mediated if and only if there is a
finite generating set $T$ for $\Gamma$ such that for each $t\in T$, there
exists a $t$-medium on $\Delta$.

###### Proof.

Let $t\in\Gamma$. We will show that there exists a $t$-medium on $\Delta$ if
and only if $\Delta\cap t\Delta t^{-1}$ is nonamenable. The result follows
directly from this claim.

Suppose that $\Sigma=\Delta\cap t\Delta t^{-1}$ is nonamenable, then it admits
a path cover with moves on some set $K\Subset\Sigma$, which in turn induces a
path cover of $\Delta$ with the same moves. Furthermore, as $\Sigma=\Delta\cap
t\Delta t^{-1}$ we have $K\Subset\Delta$ and
$K^{t}\subseteq\Sigma^{t}\subseteq\Delta$, and thus we have a $t$-medium on
$\Delta$.

Conversely, suppose there exists a $t$-medium on $\Gamma$ with moves
$K\Subset\Delta$. Let $H=\langle K\rangle$ be the subgroup of $\Delta$
generated by $K$. As $K^{t}\Subset\Delta$, we have that $K\Subset t\Delta
t^{-1}$ and thus $H\leqslant\Delta\cap t\Delta t^{-1}$. As the moves are in
$K$, the restriction of the path cover on $\Delta$ to $H$ is still path cover
and thus $H$ is nonamenable, which implies that $\Delta\cap t\Delta t^{-1}$ is
nonamenable. ∎

######  Remark 6.10.

The condition that $\Delta\cap\Delta^{t^{-1}}$ is non-amenable is of course
equivalent to the condition that there exists a non-amenable subgroup
$\Sigma\leqslant\Delta\cap\Delta^{t^{-1}}$. In most of our applications
$\Delta\cap\Delta^{t^{-1}}$ will not be so easy to understand, but the
assumptions will always provide a natural choice for a subgroup $\Sigma$ for
which we can check that $\Sigma\leqslant\Delta$ and
$\Sigma^{t}\leqslant\Delta$.

######  Remark 6.11.

Note that $\Delta\cap\Delta^{t^{-1}}$ is a subgroup of $\Gamma$, so applying
Lemma 6.6 yields that if $\Delta$ admits a $t$-medium with a symmetric set of
moves $K\setminus\\{1_{\Delta}\\}$, then $\Delta$ admits a full and colored
$t$-medium with moves $K^{2}\setminus\\{1_{\Delta}\\}$.

The main idea behind the definition of $t$-media is the following: suppose
$(p_{g})_{g\in\Gamma}$ is a path cover of $\Gamma$ with moves $K$, and
$t\in\Gamma$, then we can define $q_{g}\colon\mathbb{N}\to\Gamma$ by
$q_{g}(n)=p_{gt^{-1}}(n)t$ for every $g\in\Gamma$, and call
$(q_{g})_{g\in\Gamma}$ the $t$-conjugate path cover of $(p_{g})_{g\in\Gamma}$.
This is indeed a path cover with moves in $K^{t}$, since we have just shifted
the path cover by a right translation.

Furthermore, if $(p_{g})_{g\in\Gamma}$ is a path cover of $\Gamma$ with moves
in $K\Subset\Delta$, then $(p_{g})_{g\in\Gamma}$ naturally specifies a path
cover of $\Delta$ on each coset of $\Delta$: picking representatives
$\Gamma=\bigcup_{g\in R}gH$, for each $g\in R$ we obtain a path cover by
$q_{h}(n)=g^{-1}p_{gh}(n)$. Note that the choice of representatives only
translates the path covers, and in particular does not affect mediation.

Now we are ready to prove Theorem 1.3. That is, that if $\Gamma$ is a finitely
generated and recursively presented group which contains a mediated self-
simulable subgroup $\Delta$. Then $\Gamma$ is self-simulable.

###### Proof of Theorem 1.3.

Let $\Gamma\curvearrowright X$ be an effectively closed action and let
$\Delta\leqslant\Gamma$ be the mediated self-simulable subgroup. Without loss
of generality, suppose that
$X\subseteq\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$. Let $T\Subset\Gamma$ be
a (not necessarily symmetric) finite generating set, and let
$\overline{T}=\\{\bar{t}:t\in T\\}$ be a disjoint set (one can think of it as
a set of formal inverses). As $\Delta$ is mediated, we can associate to each
$t\in T$ a symmetric set $K_{t}\Subset\Delta\cap\Delta^{-t}$ such that
$1_{\Gamma}\notin K_{t}$ and there is a $t$-medium for $\Delta$ with moves
$K_{t}$. Let $K_{\bar{t}}=(K_{t})^{t}$.

For each $t\in T\cup\overline{T}$, denote by $\mathbf{P}_{t}$ the paradoxical
subshift on $\Gamma$ constructed with moves
$M_{t}=K_{t}^{2}\setminus\\{1_{\Gamma}\\}$ (using the alphabet
$(M_{t})^{3}\times\\{\mathtt{G},\mathtt{B}\\}$). Let us define the
$\Gamma$-subshift,

$\mathbf{W}=\prod_{t\in
T\cup\overline{T}}(\mathbf{P}_{t}\times\\{\mathtt{0},\mathtt{1}\\}^{\Gamma}).$

For every $t\in T\cup\overline{T}$, write the projection to the $t$-th layer
as
$\pi_{t}\colon\mathbf{W}\to\mathbf{P}_{t}\times\\{\mathtt{0},\mathtt{1}\\}^{\Gamma}$.
For $w\in\mathbf{W}$, if
$\pi_{t}(w)=(\rho,z)\in\mathbf{P}_{t}\times\\{\mathtt{0},\mathtt{1}\\}^{\Gamma}$,
let $\gamma_{g,t}(n,w)$ denote the function $\gamma_{g}(n,\rho)$ and
$\beta_{g,t}(n,\rho)=z(\gamma_{g,t}(n,w))$.

Next, we shall define a $\Gamma$-subshift $\mathbf{Y}$ by imposing additional
constraints on configurations $w\in\mathbf{W}$.

  * •

Constraint 1: For each $g\in\Gamma$, there exists $x\in X$, such that for
every $t\in T$ we have $(\beta_{g,t}(n,w))_{n\in\mathbb{N}}=x$. We call $x$
the simulated configuration at $g$.

  * •

Constraint 2: For each $g\in\Gamma$, if the simulated configuration at $g$ is
$x$, then for every $t\in T$ we have that
$(\beta_{g,\bar{t}}(n,w))_{n\in\mathbb{N}}=tx$.

  * •

Constraint 3: For all $t\in T$ and $g\in\Gamma$, if
$\pi_{t}(w)(g)=((k_{1},k_{2},k_{3},\mathtt{c}),b)$, then
$\pi_{\overline{t}}(w)(gt)=((k_{1}^{t},k_{2}^{t},k_{3}^{t},\mathtt{c}),b)$.

We argue that $\mathbf{Y}$ is a sofic $\Gamma$-subshift. To see this, notice
that the first two constraints can be defined using a recursively enumerable
list of forbidden pattern codings whose support is contained in $\Delta$
(because $M_{t}\subseteq\Delta$ for all $t\in T\cup\overline{T}$). In other
words, the configurations in $\mathbf{W}$ which satisfy the first two
constraints consist on copies on each coset of $\Delta$ of configurations of
an effectively closed subshift (by patterns) on $\Delta$. As $\Gamma$ is
recursively presented, so is $\Delta$, and this effectively closed subshift is
topologically conjugate to an effectively closed action of $\Delta$ by
Proposition 2.18. As $\Delta$ is self-simulable, it follows that there is a
subshift of finite type on $\Delta$ which factors onto this subshift and thus
can be extended to a $\Gamma$-subshift of finite type which factors onto the
set of configurations of $\mathbf{W}$ which satisfy the first two constraints.
The last constraint is a local rule, therefore we conclude that $\mathbf{Y}$
is a sofic $\Gamma$-subshift.

Therefore, it suffices to show that $\mathbf{Y}$ factors onto
$\Gamma\curvearrowright X$. Fix $t\in T$ and let $\phi\colon\mathbf{Y}\to X$
be the map defined by

$\phi(w)_{n}=\beta_{1_{\Gamma},t}(n,w)\mbox{ for every }w\in\mathbf{Y}.$

The map $\phi$ is obviously continuous, and the codomain is $X$ by the first
constraint. We need to show that $\phi$ is $\Gamma$-equivariant and
surjective.

First we show that $\phi$ is $\Gamma$-equivariant. Since $T$ is a generating
set, so is $T^{-1}$ and thus it suffices to show that
$\phi(t^{-1}w)=t^{-1}\phi(w)$ for every $t\in T$ and $w\in\mathbf{Y}$.

Fix $w\in\mathbf{Y}$ and let $x=\phi(w)\in X$. Let us denote for
$n\in\mathbb{N}$, $p(n+1)=\gamma_{1_{\Gamma},t}(n,w)$ and $p(0)=1_{\Gamma}$.
Suppose that the color at $\pi_{t}(w)(1_{\Gamma})$ is blue (the other case is
symmetric), and denote by $\textvisiblespace$ any symbol. Then we have

$\pi_{t}(w)(p(0))=((p(1),\textvisiblespace,\textvisiblespace,\mathtt{B}),\textvisiblespace),$

and

$\pi_{t}(w)(p(n))=((p(n)^{-1}p(n+1),\textvisiblespace,p(n)^{-1}p(n-1),\mathtt{G}),x_{n-1})\mbox{
for every }n\geq 1.$

By the third condition we have

$\pi_{\bar{t}}(w)(p(0)t)=(((p(1)^{t},\textvisiblespace,\textvisiblespace,\mathtt{B}),\textvisiblespace),$

and

$\pi_{\bar{t}}(w)(p(n)t)=(((p(n)^{-1}p(n+1))^{t},\textvisiblespace,(p(n)^{-1}p(n-1))^{t},\mathtt{G}),x_{n-1}).$

A direct calculation shows then that $\gamma_{t,\bar{t}}(n,w)=p(n)t$ for every
$n\in\mathbb{N}$, and thus $(\beta_{t,\bar{t}}(n,w))_{n\in\mathbb{N}}=x$. By
the second constraint, we obtain that the configuration simulated at $t$ is
$t^{-1}x$. Therefore, $\phi(t^{-1}w)=t^{-1}x$ as required.

Finally, we show surjectivity. Let $x\in X$ be arbitrary. For $t\in T$, pick a
$t$-medium for $\Delta$ with moves $K_{t}$. By Remark 6.11, there is a full
and colored $t$-medium with moves $M_{t}=K_{t}^{2}\setminus\\{1\\}$, and by
Lemma 6.6 the subshift $\mathbf{P}_{t}$ is nonempty. Construct a full and
colored $t$-medium on $\Gamma$ with moves $M_{t}$ by using this path cover on
every $\Delta$-coset. Take this as the $\mathbf{P}_{t}$-component of $w$ for
each $t\in T$. For $\bar{t}\in\overline{T}$, use the third constraint to
obtain the contents of the $\mathbf{P}_{\bar{t}}$-component. This is valid
because the moves on that layer are in $M_{t}^{t}=M_{\bar{t}}$. Postulating
that the simulated configuration at $g$ is $g^{-1}x$ specifies all the
$\\{\mathtt{0},\mathtt{1}\\}$ symbols on all layers because the configuration
is well-founded, From here it is clear that none of the constraints defining
$\mathbf{Y}$ are broken. ∎

Since by Proposition 3.2 a recursively presented self-simulable group is non-
amenable, we can always choose $\Sigma=\Delta$ when $\Delta$ is normal, giving
the following handy version of the previous result.

######  Corollary 6.12.

Suppose $\Gamma$ is finitely generated, recursively presented and has a normal
self-simulable subgroup $\Delta$. Then $\Gamma$ is self-simulable.

In other words, whenever we have a short exact sequence of the form

$1\to N\to\Gamma\to H\to 1,$

where $N$ is self-simulable and $\Gamma$ is finitely generated and recursively
presented, then $\Gamma$ is also self-simulable. It also follows that if $N$
is self-simulable then $N\times H$ is, for any finitely generated and
recursively presented group $H$.

######  Example 6.13.

Take $\Gamma=F_{4}$ the free group on $4$ generators. This group is not self-
simulable due to it having infinitely many ends (Proposition 3.4). However, it
has as a quotient the self-simulable group $F_{2}\times F_{2}$, therefore we
have a short exact sequence of the form

$1\to N\to F_{4}\to F_{2}\times F_{2}\to 1.$

Thus we conclude that admitting a self-simulable quotient does not imply that
the group is self-simulable. $\fullmoon$

We do not have a counterexample for split extensions, and under some
conditions on the quotient and its action, extensions on the right are indeed
self-simulable.

######  Corollary 6.14.

Suppose $\Delta$ is a recursively presented and self-simulable group, and
contains a direct product of two non-amenable groups. If $\Gamma$ is finitely
generated and recursively presented and
$\phi\colon\Delta\to\operatorname{Aut}(\Gamma)$ has amenable image, then
$\Gamma\rtimes_{\phi}\Delta$ is self-simulable.

###### Proof.

Observe that the fact that $\Gamma\rtimes_{\phi}\Delta$ is finitely generated
and recursively presented follows from the assumptions. We show that the
natural copy $\Delta\leqslant\Gamma\rtimes_{\phi}\Delta$ is mediated. Let
$\Delta_{1}\times\Delta_{2}\leqslant\Delta$ be a direct product of non-
amenable groups, and consider the action of $\Delta_{i}$ on $\Gamma$. We have
an exact sequence

$1\to K_{i}\to\Delta_{i}\to\phi(\Delta_{i})\to 1,$

where $K_{i}$ is the kernel of $\phi$ restricted to $\Delta_{i}$. By the
amenability of $\phi(\Delta_{i})\subseteq\operatorname{Aut}(\Gamma)$ and non-
amenability of $\Delta_{i}$ we have that $K_{i}$ is non-amenable. Then
$\Sigma=K_{1}\times K_{2}\leqslant\Delta$ acts trivially by conjugation on
$\Gamma$, i.e. $g^{(k_{1},k_{2})}=g$, in particular $\Sigma^{g}=\Sigma$ for
all $g\in\Gamma$ and of course we have $\Sigma^{g}\leqslant\Delta$ for any
$g\in\Delta$, thus this non-amenable subgroup satisfies the mediated
condition. ∎

In particular, if $\operatorname{Aut}(\Gamma)$ is amenable, then
$\Gamma\rtimes\Delta$ is self-simulable whenever $\Delta$ is self-simulable
and contains a direct product of two non-amenable groups.

######  Remark 6.15.

In the proof of Theorem 1.3 the condition that $\Delta$ is self-simulable can
be weakened. What we essentially use is the weaker property that for any
effectively closed $\Delta$-subshift $X$, the subshift
$X^{\Gamma/\Delta}=\\{x\in A^{\Gamma}:\mbox{ for every
}g\in\Gamma,gx|_{\Delta}\in X\\}$, where an independent copy of $X$ appears on
each $\Delta$-coset, is $\Gamma$-sofic. Note that if $\Gamma$ is self-
simulable and recursively presented, subshifts of the form $X^{\Gamma/\Delta}$
are always $\Gamma$-sofic for any finitely-generated subgroup $\Delta$ and
$\Delta$-effectively closed subshift $X$, so a subgroup $\Delta$ can certainly
have this property without being self-simulable (every finitely-generated
group is a subgroup of a self-simulable group). We do not have any examples
where this additional generality is needed.

##  7\. Rigid classes of self-simulable groups

The goal of this section is to prove Theorems 1.4 and 1.5. Recall that two
groups $\Gamma_{1}$ and $\Gamma_{2}$ are called commensurable if there exist
finite index subgroups $H_{1}\leqslant\Gamma_{1}$ and
$H_{2}\leqslant\Gamma_{2}$ which are isomorphic.

######  Lemma 7.1.