# Effective dynamical systems beyond dimension zero and factors of SFTs

Sebastián Barbieri, Nicanor Carrasco-Vargas and Cristóbal Rojas

###### Abstract.

Using tools from computable analysis we develop a notion of effectiveness for
general dynamical systems as those group actions on arbitrary spaces that
contain a computable representative in their topological conjugacy class. Most
natural systems one can think of are effective in this sense, including some
group rotations, affine actions on the torus and finitely presented algebraic
actions. We show that for finitely generated and recursively presented groups,
every effective dynamical system is the topological factor of a computable
action on an effectively closed subset of the Cantor space. We then apply this
result to extend the simulation results available in the literature beyond
zero-dimensional spaces. In particular, we show that for a large class of
groups, many of these natural actions are topological factors of subshifts of
finite type.

_Keywords: computable analysis, symbolic dynamics, simulation, topological
factors of SFTs._

_MSC2020: 37B10, 37B02, 03D78, 20F10._

##  1\. Introduction

Starting with the work of Hadamard [18] and the highly influential article of
Morse and Hedlund [21], symbolic dynamical systems have quite often played a
pivotal role in the understanding of more general dynamics. A celebrated
instance of this is the prominent role of subshifts of finite type (SFT) in
the study of Anosov, and more generally of Axiom A diffeomorphisms, through
Markov partitions of their non-wandering sets [9]. Another well-known example
of this tight relationship is the fact that the natural action of a word-
hyperbolic group on its boundary is a very well behaved topological factor of
an SFT on the same group [16].

These and similar results raise the question of understanding precisely which
dynamical systems are topological factors of SFTs. An observation made by
Hochman [22] is that subactions of multidimensional SFTs satisfy strong
computability constraints. More precisely, they must be computable maps on
effectively closed sets in the sense that the complement of the space of
orbits must consist on a union of cylinders whose defining words can be
enumerated by a Turing machine. However, the truly remarkable discovery of
Hochman is that, up to a difference in the dimension of the acting group and a
topological factor, this is the only constraint: every computable
homeomorphism on an effectively closed zero-dimensional set is the topological
factor of a subaction of a $\mathbb{Z}^{3}$-SFT.

Results linking computable maps on effectively closed zero-dimensional sets to
SFTs are called “simulation results”, as they express that very explicit and
simple models such as SFTs are capable of universally encoding this
considerably larger class of dynamical systems. These simulation results along
with further developments [2, 17] led to a new understanding of classical
results in the theory, such as the undecidability of the domino problem [35,
7], the existence of aperiodic tilesets [7, 30] and more generally the
existence of two-dimensional tilings without computable orbits [19, 28].
Moreover, they also provided the tools to obtain new and long sought-after
results, such as the classification of topological entropies of
multidimensional SFTs [23].

Further work has extended the initial result of Hochman to the context of
actions of discrete groups on zero-dimensional spaces [4, 3, 6]. Notably, it
was shown that for a large class of non-amenable groups called self-simulable,
the class of zero-dimensional topological factors of SFTs contains every
possible computable action on an effectively closed zero-dimensional set [5].
These works have led to new results about the dynamics of such groups. For
instance, they have provided new examples of groups that can act freely,
expansively and with shadowing on a zero-dimensional space.

A common theme among all of the previous simulation results is that they apply
to actions on zero-dimensional spaces. The reason behind this is rooted in the
fact that the Cantor space $\\{0,1\\}^{\mathbb{N}}$ admits a natural
computable structure, where the cylinders are described by finite words, and
that allows the application of algorithmic techniques. The main objective of
this paper is to explore a generalization to groups acting on non-symbolic
spaces, such as compact subsets of $\mathbb{R}^{n}$,
$\operatorname{GL}_{n}(\mathbb{C})$ or compact abelian groups such as
$(\mathbb{R}/\mathbb{Z})^{n}$. Thus, the goal of this article is to explore
the following question.

######  Question 1.1.

Can the simulation results be extended to group actions on spaces that are not
zero-dimensional?

The theory of computable analysis offers the means to endow separable metric
spaces with computable structures that allow the notion of computable map to
make sense, and the application of algorithmic techniques possible. In this
paper we explore this approach and study its connections with the existing
simulation results. In particular, we introduce a very general notion of
effective dynamical system (EDS) and show that all of the known simulation
results can be extended to this class. By an effective dynamical system we
mean one that is topologically conjugate to a computable action over a
recursively compact subset of a computable metric space. We do not require the
topological conjugacy to be computable, so an EDS does not need to be
computable itself. The class of EDS is therefore quite large and encompasses
virtually all natural examples (although artificial non-examples can be
constructed, see Section 8). Our main tool will be the following result:

######  Theorem A.

Let $\Gamma$ be a finitely generated and recursively presented group. For any
effective dynamical system $\Gamma\curvearrowright X$ there exists an
effectively closed zero-dimensional space
$\widetilde{X}\subset\\{0,1\\}^{\mathbb{N}}$ and a computable action
$\Gamma\curvearrowright\widetilde{X}$ such that $\Gamma\curvearrowright X$ is
a topological factor of $\Gamma\curvearrowright\widetilde{X}$.

We remark that is it a well-known fact that every group action by
homeomorphisms on a compact metrizable space admits a zero-dimensional
extension. This extension, however, carries a priory no computable structure.
Our contribution is that, for recursively presented groups, the computable
structure stemming from the effective nature of the system is preserved by a
well-chosen zero-dimensional extension.

Given a finitely generated group $\Gamma$ and an epimorphism
$\psi\colon\Gamma\to H$, we say that $\Gamma$ simulates $H$ if the action of
$\Gamma$ induced through $\psi$ of any computable action of $H$ on an
effectively closed subset of the Cantor space is a factor of a $\Gamma$-SFT.
If $\psi$ is an isomorphism, then $\Gamma$ is called self-simulable. The class
of self-simulable groups includes several interesting examples, see Theorem
5.2.

The main application of A is that for recursively presented groups the
simulation results in the literature also apply to EDS.

######  Theorem B.

Let $\Gamma,H$ be finitely generated groups and $\psi\colon\Gamma\to H$ be an
epimorphism. Suppose that $H$ is recursively presented, then $\Gamma$
simulates $H$ if and only if for every effective dynamical system
$H\curvearrowright X$ the induced action of $\Gamma$ is a topological factor
of a $\Gamma$-SFT.

Combining this result with the simulations result in the literature, we obtain
that many dynamical systems on non zero-dimensional spaces can be realized as
factors of subshifts of finite type. This includes the natural action of
$\operatorname{GL}_{n}(\mathbb{Z})\curvearrowright\mathbb{R}^{n}/\mathbb{Z}^{n}$
by left matrix multiplication for $n\geq 5$, actions of $F_{2}\times F_{2}$ on
the circle by computable rotations on each generator, actions of the Braid
groups $B_{n}$ for $n\geq 7$ on compact computable groups, and more.

To better illustrate the power of B, we develop in detail a particular
application which we believe could be special interest. An action of a
countable group on a compact abelian topological group by automorphisms is
called algebraic. This is a rich class of group actions which has been the
object of much study in the literature, for instance in [26, 32, 25, 15].
Using our results we obtain that a large class of algebraic actions of non-
amenable groups can be presented as topological factors of SFTs.

######  Theorem C.

Let $\Gamma$ be a finitely generated and recursively presented self-simulable
group. Every finitely presented algebraic action of $\Gamma$ is the
topological factor of a $\Gamma$-subshift of finite type.

In fact, this result applies to an even larger class of algebraic actions
which admit “recursive presentations”, see Definition 6.5.

We complete our discussion with several observations. There exist at least two
notions of computability for shift spaces present in the literature (Corollary
7.7). We discuss their connection to the notion of EDS and show that for
recursively presented groups they all coincide. We also completely
characterize the relations between these notions for groups which are not
recursively presented. We then focus on the class of topological factors of
EDS. While it is true that computable factors of EDS are EDS (Proposition
3.30), the class of EDS is in general not closed under topological factor
maps. We provide two examples of this fact, one as a non-EDS factor of an EDS
on a compact subset of $\mathbb{C}$, and a non-EDS zero-dimensional factor of
a zero-dimensional EDS. In the case of zero-dimensional spaces, we propose a
new notion (Definition 8.4) of weak effective dynamical system (WEDS). We show
that for recursively presented groups, every zero-dimensional factor of an EDS
is a WEDS (Proposition 8.9), and that the class of WEDS is closed under
topological factor maps. This class of systems can be though of as those that
can be written as an inverse limit of effective subshifts, but with the caveat
that the effectiveness of the sequence of subshifts is not required to be
uniform. Using this notion, we naturally recover the fact that the class of
subshifts which are EDS is closed under topological factor maps.

###  1.1. Paper organization

After some preliminaries, we give an introduction to computable analysis and
the precise definition of an EDS in Section 3. The proof of A along with a few
interesting side remarks are provided in Section 4. In particular, we show
that for zero-dimensional EDS we may always consider the canonical computable
structure induced by the cylinder sets and that in this case we do not need
the hypothesis that the acting group is recursively presented. We also show
that in case the action admits a generating cover, the extension can be taken
to be an effective subshift. In Section 5 we summarize the simulation results
in the literature, prove B, and discuss several examples. In Section 6 we
present the relevant background for C along with its proof. In Section 7 we
turn our attention back to shift spaces and study the relationship between the
different notions of computability for subshifts. Finally, in Section 8 we
construct the examples showing that the class of EDS is not closed by
topological factor maps, introduce the class of WEDS, show that this class is
closed by factor maps, and discuss their relationship with EDS.

Acknowledgments: The authors are thankful to Mathieu Hoyrup for stimulating
conversations on the construction of explicit examples of non effective
dynamical systems in higher dimensions. S. Barbieri was supported by the
FONDECYT grant 11200037. N. Carrasco-Vargas was partially supported by ANID
CONICYT-PFCHA/Doctorado Nacional/2020-21201185, ANID/Basal National Center for
Artificial Intelligence CENIA FB210017, and the European Union’s Horizon 2020
research and innovation program under the Marie Sklodowska-Curie grant
agreement No 731143. C. Rojas was supported by ANID/FONDECYT Regular 1230469
and ANID/Basal National Center for Artificial Intelligence CENIA FB210017.

##  2\. Preliminaries

###  2.1. Computability on countable sets

A formal introduction to the theory of computation can be found in [31] or
[33]. Here we will provide a brief functional description. We will make use of
the word algorithm to refer to a Turing Machine [34]. The reader may think
about a Turing machine as a computer program written in any standard
programming language which receives some finite information called input, then
proceeds to sequentially execute a finite set of instructions. Depending on
these instructions and the input, the execution may at some halt and return
some finite information, called output, or it may not halt, in which case the
execution will continue forever without ever providing an output.

The notion of algorithm characterizes mathematical objects according to the
extent to which they can be _computed_. Depending on what exactly the
algorithm is required to compute, we will use different names for them in our
definitions (computable, effective, decidable, etc…).

Let us start by functions over words. For a set $A$, denote by
$A^{*}=\bigcup_{n\in\mathbb{N}}A^{n}$ the set of all words on $A$. Let $A,B$
be finite sets (called alphabets in this setting). A partial function $f\colon
A^{*}\to B^{*}$ is a function which is not necessarily defined in all of
$A^{*}$. A computable function is a partial function $f\colon A^{*}\to B^{*}$
for which there exists an algorithm which on input $w\in A^{*}$ halts if and
only if $f$ is defined on $w$, in which case it outputs $f(w)$. We say that a
partial function is total if it is defined on every element of $A^{*}$.

We may also define computable functions on other countable sets by
representing them through words in a canonical way. For instance, we will
represent non-negative integers using the alphabet
$A=\\{\mathtt{0},\mathtt{1}\\}$ through their binary expansion. Similarly, we
can represent integers, rational numbers, tuples in $\mathbb{N}^{d}$ or
sequences in $\mathbb{N}^{*}$ by words using some explicit (such that we can
algorithmically recover them from one another) bijection with $\mathbb{N}$ and
then encoding $\mathbb{N}$ through binary words. In what follows, we refer to
these objects as named sets and speak freely of algorithms working on them.

Let $X$ be a named set and $A\subset X$. We say that $A$ is recursively
enumerable (r.e.) or semi-decidable if there is an algorithm which, on input
$w$, halts if and only if $w\in A$. Equivalently, $A$ is r.e. if it is either
empty, or it equals $\\{f(n):n\in\mathbb{N}\\}$ for some total computable
function $f\colon\mathbb{N}\to X$. We say that $A$ is decidable if both $A$
and $X\setminus A$ are semi-decidable.

######  Example 2.1.

Let $(\varphi_{e})_{e\in\mathbb{N}}$ be an effective enumeration of all
partial computable functions (for example, in lexicographic order according to
their “code”). The famous halting set
$\texttt{Halt}=\\{e\in\mathbb{N}:\varphi_{e}(e)\mbox{ halts}\\}$ is an example
of a semi-decidable set that is not decidable.

Every time we have a sequence $(x_{n})_{n\in\mathbb{N}}$ of objects that are
computable in some way, for instance a sequence $(f_{n})_{n\in\mathbb{N}}$ of
computable functions or a sequence $(A_{n})_{n\in\mathbb{N}}$ of decidable
sets, we will say that the computability of the sequence is uniform when all
the objects in the sequence can be computed by the same algorithm. For
example, a sequence $(f_{n})_{n\in\mathbb{N}}$ of total functions is uniformly
computable if there is an algorithm which on input $(n,w)$ halts and outputs
$f_{n}(w)$. Similarly, a sequence $(A_{n})_{n\in\mathbb{N}}$ of sets is
uniformly r.e. if there is an algorithm which on input $(n,w)$ halts if and
only if $w\in A_{n}$.

######  Example 2.2.

Let $(\varphi_{e})_{e\in\mathbb{N}}$ be the lexicographic enumeration of all
partial computable functions and let
$A_{e}=\\{n\in\mathbb{N}:\varphi_{e}(n)\text{ halts}\\}$. Then the sequence of
all recursively enumerable sets $(A_{e})_{e\in\mathbb{N}}$ is uniform. On the
other hand, the sequence $(A_{e_{n}})_{n\in\mathbb{N}}$ of all decidable sets
is not uniform.

###  2.2. Finitely generated groups

Let $\Gamma$ be a group. Given $S\subset\Gamma$ and a word $w=w_{1}\dots
w_{n}\in S^{*}$, we denote by $w$ the element of $\Gamma$ obtained by
multiplying the $w_{i}$. Recall that $\Gamma$ is finitely generated if
$\Gamma=\\{\underline{w}:w\in S^{*}\\}$ for some finite $S\subset\Gamma$. The
word problem of $\Gamma$ with respect to $S$ is the set of words

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

We say that a finitely generated group $\Gamma$ is recursively presented if
$\texttt{WP}_{S}(\Gamma)$ is recursively enumerable, and that $\Gamma$ has
decidable word problem if $\texttt{WP}_{S}(\Gamma)$ is decidable. These two
properties do not depend upon the choice of $S$, as long as $S$ is a finite
generating set for $\Gamma$. A surjective group homomorphism is called an
epimorphism.

######  Remark 2.3.

Let $\Gamma$ be a group which is finitely generated by $S$. Consider a total
order in $S^{*}$ where words are first ordered by their length, and amongst
words of the same length we use a fixed lexicographical order. There exists a
unique increasing function $f\colon\mathbb{N}\to S^{*}$ with the property that
for each $n\in\mathbb{N}$, $f(n)$ is minimal amongst all $w\in S^{*}$ with
$\underline{f(n)}=\underline{w}$ and such that $n\mapsto\underline{f(n)}$ is a
bijection. This function is computable if and only if $\Gamma$ has decidable
word problem, thus finitely generated groups with decidable word problem are
named sets.

###  2.3. Group actions and their dynamics

Given a group $\Gamma$ and actions by homeomorphisms on compact metrizable
spaces $\Gamma\curvearrowright X$ and $\Gamma\curvearrowright Y$, a continuous
surjective map $f\colon X\to Y$ is a topological factor map if for every
$g\in\Gamma$ and $x\in X$ we have $g(f(x))=f(gx)$. Furthermore, we say that a
topological factor map is a topological conjugacy if it is an homeomorphism. A
major challenge in dynamical systems theory is to classify this kind of group
actions up to topological conjugacy or topological factor maps.

Given a group homomorphism $\psi\colon G\to\Gamma$ and a group action
$\Gamma\curvearrowright X$, we define the induced action $G\curvearrowright X$
by $gx=\psi(g)x$ for every $g\in G$.

###  2.4. Shift spaces

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

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

The elements $x\in A^{\Gamma}$ are called configurations. Given
$F\Subset\Gamma$, a pattern with support $F$ is an element $p\in A^{F}$. We
denote the cylinder generated by $p$ by $[p]=\\{x\in A^{\Gamma}:x|_{F}=p\\}$
and note that the cylinders are a clopen base for the prodiscrete topology on
$A^{\Gamma}$.

######  Definition 2.4.

A subset $X\subset 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}}=\\{x\in A^{\Gamma}:gx\notin[p]\mbox{ for every
}g\in\Gamma,p\in\mathcal{F}\\}.$

A subshift $X$ is of finite type (SFT) if there exists a finite set of
forbidden patterns $\mathcal{F}$ for which $X=X_{\mathcal{F}}$.

We say that an action $\Gamma\curvearrowright X$ on a compact metrizable space
is expansive if for some metric $d$, which is compatible with the topology,
there exists $C>0$ such that whenever $x,y\in X$ are distinct then
$\sup_{g\in\Gamma}d(gx,gy)\geq C$. It is a well known elementary fact (for
instance, see [20, Theorem 2.1]) that an action $\Gamma\curvearrowright X$ on
a zero-dimensional compact metrizable space is expansive if and only if it is
topologically conjugate to a subshift.

###  2.5. Computability on Cantor spaces

Let $A$ be a finite set with $|A|\geq 2$. The space $A^{\mathbb{N}}$ endowed
with the product of the discrete topology will be called Cantor space. It is
compact, metrizable and has topological dimension zero. The Cantor space is
universal in the sense that every compact, metrizable space with topological
dimension zero is homeomorphic to a closed subset of $A^{\mathbb{N}}$ (Further
on in Theorem 3.18 we will prove an effective version of this result). As we
will only deal with compact metrizable spaces, in what follows we will just
say that a space is zero-dimensional to say that it has these three
properties.

A natural metric in the Cantor space is given by

$d(x,y)=2^{-\inf\\{n\in\mathbb{N}\ :\ x_{n}\neq y_{n}\\}}\mbox{ for }x,y\in
A^{\mathbb{N}}.$

Given a word $w=w_{0}\dots w_{n}\in A^{*}$, the cylinder determined by $w$ is
the clopen set

$[w]=\\{x\in A^{\mathbb{N}}:x_{0}\dots x_{n}=w_{0}\dots w_{n}\\}.$

The collection of all cylinders forms a base for the topology on
$A^{\mathbb{N}}$.

Next we will introduce computability notions for $A^{\mathbb{N}}$. We say that
a set $U\subset A^{\mathbb{N}}$ is effectively open if there exists a
recursively enumerable set $L\subset A^{*}$ such that $U=\bigcup_{w\in L}[w]$.
Intuitively, this means that this set can be approximated by an algorithm from
the inside. Similarly, we say that a set $C\subset A^{\mathbb{N}}$ is
effectively closed, if it is the complement of an effectively open set. For a
subspace $X\subset A^{\mathbb{N}}$, we say that a set is effectively open
(respectively closed) in $X$ if it is the intersection of $X$ with an
effectively open (respectively closed) set.

######  Remark 2.5.

Let $(U_{i})_{i\in\mathbb{N}}$ be an uniform sequence of effectively open sets
and write $U_{i}=\bigcup_{w\in L_{i}}[w]$. As the union of a uniform sequence
(in particular a finite sequence) of recursively enumerable languages is
recursively enumerable, it follows that the union
$\bigcup_{i\in\mathbb{N}}U_{i}$ is also effectively open. An analogous
argument shows that the intersection of any uniform sequence (in particular, a
finite sequence) of effectively closed sets is effectively closed.

######  Remark 2.6.

Given a finite list of words $w_{1},\dots,w_{n}\in A^{*}$, it is easy to write
an algorithm which decides if $\bigcup_{i=1}^{n}[w_{i}]=A^{\mathbb{N}}$. In
particular, as $A^{\mathbb{N}}$ is compact it follows that if $U$ is an
effectively open set, we can algorithmically recognize if $U=X$ by enumerating
the words in its associated recursively enumerable language and repeatedly
checking whether their associated cylinder sets cover $A^{\mathbb{N}}$.
Analogously, we can algorithmically recognize if an effectively closed set is
empty.

######  Definition 2.7.

Let $A,B$ be alphabets, we say that a function $f\colon X\subset
A^{\mathbb{N}}\to B^{\mathbb{N}}$ is computable if uniformly for every $w\in
B^{*}$ there exists an effectively open set $U_{w}\subset A^{\mathbb{N}}$ such
that $f^{-1}([w])=U_{w}\cap X$.

Notice that computable functions are always continuous in their domain and
that the composition of computable functions is computable. An equivalent and
perhaps more intuitive way to think about computable functions on $X\subset
A^{\mathbb{N}}$ is as those for which there is an algorithm that given a
prefix of $x\in X$ yields a prefix of its image, and the sequence of prefixes
monotonously converges to $f(x)$.

######  Proposition 2.8.

Let $A,B$ be alphabets. A function $f\colon X\subset A^{\mathbb{N}}\to
B^{\mathbb{N}}$ is computable if and only if there exists a partial computable
function $g\colon A^{*}\to B^{*}$ such that for any $x\in X$,
$g(x|_{\\{0,\dots,n\\}})$ is defined for every $n$, the cylinders
$[g(x|_{\\{0,\dots,n\\}})]$ form a nested sequence and

$\\{f(x)\\}=\bigcap_{n\in\mathbb{N}}[g(x|_{\\{0,\dots,n\\}})].$

###### Proof.

Suppose that $f$ is computable, we shall construct a partial computable
function $g\colon A^{*}\to B^{*}$ with the required properties. As $f$ is
computable, there is an algorithm which can list in some order all $(v,w)\in
A^{*}\times B^{*}$ such that $[v]\cap X\subset f^{-1}([w])$. Set
$g(\epsilon)=\epsilon$ and start the listing algorithm. Iteratively, for every
pair $(v,w)$ which is listed, compute the largest prefix $v^{\prime}\in A^{*}$
for which $g(v^{\prime})$ is already defined. If $g(v^{\prime})$ is strictly a
prefix of $w$, set $g(v)=w$ and $g(v^{\prime\prime})=g(v^{\prime})$ for every
intermediate word $v^{\prime\prime}$ which has $v^{\prime}$ as a prefix and is
a prefix of $v$. Otherwise, do nothing. The function $g\colon A^{*}\to B^{*}$
resulting for this procedure is a partial computable map which satisfies the
required properties.

Conversely, given a partial computable function $g\colon A^{*}\to B^{*}$ with
the properties of the statement and $w\in B^{*}$, the collection

$L_{w}=\\{v\in A^{*}:g(v)\mbox{ is defined and }w\mbox{ is a prefix of
}g(v)\\},$

is recursively enumerable uniformly on $w$. Therefore the collection
$U_{w}=\bigcup_{v\in L_{w}}[v]$ is uniformly effectively open and because of
the assumptions on $g$ it satisfies $f^{-1}([w])=X\cap U_{w}$. ∎

We shall now provide a few examples.

######  Example 2.9.

The shift map $\sigma\colon A^{\mathbb{N}}\to A^{\mathbb{N}}$ given by
$\sigma(x)_{n}=x_{n+1}$ is computable. Indeed the map $g\colon A^{*}\to A^{*}$
which deletes the first symbol, that is $g(x_{1}\dots x_{m})=x_{2}\dots x_{m}$
is computable and satisfies the required monotonicity condition.

######  Example 2.10.

Consider the map
$f\colon\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}\to\\{\mathtt{0},\mathtt{1},\mathtt{2}\\}^{\mathbb{N}}$
given by

$f(x)_{0}=\begin{cases}\mathtt{0}&\mbox{ if }x_{0}=\mathtt{0}\\\
\mathtt{1}&\mbox{ if }x_{0}x_{1}=\mathtt{10}\\\ \mathtt{2}&\mbox{ if
}x_{0}x_{1}=\mathtt{11}\\\ \end{cases}\mbox{ and
}f(x)_{k}=\begin{cases}f(\sigma(x))_{k-1}&\mbox{ if }x_{0}=\mathtt{0}\\\
f(\sigma^{2}(x))_{k-1}&\mbox{ if }x_{0}=\mathtt{1}\\\ \end{cases}\mbox{ for
}k\geq 1.$

Where $\sigma$ is the shift map from Example 2.9. It is clear by its recursive
definition that $f$ is a computable map. Moreover, this map provides an
example of a computable homeomorphism (computable bijection with computable
inverse) between $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ and
$\\{\mathtt{0},\mathtt{1},\mathtt{2}\\}^{\mathbb{N}}$. This construction can
be easily generalized to provide a computable homeomorphism between
$A^{\mathbb{N}}$ and $B^{\mathbb{N}}$ for any finite $A,B$ with at least two
elements each, in fact, we shall show that a much more general statement holds
in Theorem 3.18.

######  Definition 2.11.

Let $\Gamma$ be a finitely generated group and $X\subset A^{\mathbb{N}}$. We
say that an action $\Gamma\curvearrowright X$ is computable if for some finite
set of generators $S$ and each $s\in S$ we have that the group action map
$f_{s}\colon X\to X$ given by $f_{s}(x)=sx$ is computable.

Notice that as the composition of computable maps is computable, we have that
for any $g\in\Gamma$ the map $f_{g}\colon X\to X$ given by $f_{g}(x)=gx$ is
computable. Therefore, if this condition is satisfied by some generating set,
then it is uniformly satisfied by all of them.

Although there are only countably many computable maps, almost every action
that one may come up with naturally (without introducing explicitly an
uncomputable parameter) is likely going to be computable. Let us provide a few
examples of computable actions on Cantor spaces.

######  Example 2.12.

Let $A=\\{\mathtt{0},\mathtt{1}\\}$ and consider the binary odometer action
$\mathbb{Z}\curvearrowright\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ induced
by the homeomorphism
$T\colon\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}\to\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$
defined by

$T(x)_{n}=\begin{cases}\mathtt{0}&\mbox{ if }n<c,\\\ \mathtt{1}&\mbox{ if
}n=c,\\\ x_{n}&\mbox{ if }n>c\end{cases}\qquad\mbox{ where }\quad
c=\inf\\{k\in\mathbb{N}:x_{k}=\mathtt{0}\\}.$

Clearly $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ is effectively closed. We
claim that the map $T$ is computable: let $x_{0}\dots x_{n-1}$ be the first
$n$ digits of $x\in A^{\mathbb{N}}$, we can read the sequence from left to
right swapping $\mathtt{1}$ for $\mathtt{0}$ until we either read a
$\mathtt{0}$, in which case we swap it for a $\mathtt{1}$ and leave the rest
of the sequence untouched, or we reach the end of the sequence. The resulting
sequence corresponds to the first $n$-digits of the image of $T(x)$. A similar
argument shows that $T^{-1}$ is computable as well, and as $\\{-1,1\\}$
generates $\mathbb{Z}$, we conclude that the binary odometer action is
computable.

######  Example 2.13.

Let $\mathcal{U}=\\{u_{1},\dots,u_{n}\\}$ and
$\mathcal{V}=\\{v_{1},\dots,v_{n}\\}$ be two sets of binary words which induce
partitions of $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$, that is, such that
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}=\bigcup_{i=1}^{n}[u_{i}]=\bigcup_{i=1}^{n}[v_{i}]$
and the unions are disjoint. Consider the homeomorphism $f$ of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ such that $f(u_{i}x)=v_{i}x$, that
is, if an infinite word begins by $u_{i}$, it replaces that prefix by $v_{i}$
and leaves the rest of the word unchanged. Notice that for any choice of
$\mathcal{U},\mathcal{V}$ the associated homeomorphism is computable.

Three celebrated groups can be defined using these homeomorphisms, namely:

  1. (1)

Thompson’s group $F$ of all such homeomorphisms where the elements of both
$\mathcal{U}$ and $\mathcal{V}$ are indexed in lexicographical order.

  2. (2)

Thompson’s group $T$ of all such homeomorphisms where the elements of both
$\mathcal{U}$ and $\mathcal{V}$ are indexed in lexicographical order up to a
cyclical permutation.

  3. (3)

Thompson’s group $V$ of all such homeomorphisms.

The three groups above satisfy $F\leqslant T\leqslant V$ and are finitely
generated [11]. Their natural actions on
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ are examples of computable actions
on an effectively closed set.

Naturally, for any named set $\mathcal{N}$, we can consider computability of
maps from $A^{\mathcal{N}}$ to $B^{\mathcal{N}}$ through the identification of
$\mathcal{N}$ with $\mathbb{N}$. For instance, if we let
$\varphi\colon\mathbb{N}\to\mathbb{Z}$ be the bijection
$\varphi(n)=(-1)^{n}\lceil\frac{n}{2}\rceil$, a set $X\subset A^{\mathbb{Z}}$
would be effectively closed if and only if $X^{\prime}=\\{x^{\prime}\in
A^{\mathbb{N}}:x^{\prime}=x\circ\varphi\mbox{ for some }x\in X\\}$ is
effectively closed in $A^{\mathbb{N}}$.

######  Example 2.14.

Consider the homeomorphisms $t$ and $a$ on
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{Z}}$ given by

$t(x)_{n}=x_{n+1}\quad\mbox{ and }\quad
a(x)_{n}=\begin{cases}\mathtt{1}-x_{n}&\mbox{ if }n=0,\\\ x_{n}&\mbox{ if
}n\neq 0\end{cases}\quad\mbox{ for every
}x\in\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{Z}}\mbox{ and }n\in\mathbb{Z}.$

In words, the map $t$ shifts a bi-infinite binary sequence to the left, while
the involution $a$ swaps the symbol at the origin. The maps $t,t^{-1}$ and $a$
generate the lamplighter group. If we identify
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{Z}}$ with
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ through a computable bijection
between $\mathbb{N}$ and $\mathbb{Z}$ we get that the maps corresponding to
$t,t^{-1}$ and $a$ are computable. It follows that the induced natural action
$(\mathbb{Z}\wr\mathbb{Z}/2\mathbb{Z})\curvearrowright\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{Z}}$
is computable.

##  3\. Effective dynamical systems

In this section we introduce and discuss the main notion of this work:
effective dynamical systems. This notion generalizes the idea of a computable
action over an effectively closed subset of $A^{\mathbb{N}}$ to metric spaces
with positive topological dimension. Our definition will be expressed in the
formalism of computable analysis, to which we will provide a short
introduction.

###  3.1. Computable analysis

Computable analysis is about making algorithms able to process infinite
objects, such as real numbers or infinite sequences. A convenient unifying way
to formalize this idea is to see these objects as points of a metric space
with an extra computable structure. Most of the results presented here are
well known and can be found in the literature (we refer to [10] for a modern
exposition). We also present some new results related to zero-dimensional
spaces.

######  Definition 3.1.

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

$|d(s_{i},s_{j})-r|\leq 2^{-n}.$

We say that the distances $d(s_{i},s_{j})$ are uniformly computable from
$i,j$.

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

$U_{I}=\bigcup_{n\in I}B_{n}.$

An open set $V\subset X$ is effectively open if $V=U_{I}$ for some recursively
enumerable set $I\subset\mathbb{N}$. We note that finite intersections and
unions of countably many uniformly effectively open sets is again effectively
open. A point $x\in X$ is computable if the set $\\{n\in\mathbb{N}:x\in
B_{n}\\}$ is recursively enumerable. Note that a point $x\in X$ is computable
if and only if one can uniformly compute a sequence
$(s_{\varphi(n)})_{n\in\mathbb{N}}$ of elements of $\mathcal{S}$ which satisfy
$|s_{\varphi(n)}-x|\leq 2^{-n}$ for every $n\in\mathbb{N}$.

######  Example 3.2.

The set $\mathbb{R}$ of real numbers, with the Euclidean metric $d(x,y)=|x-y|$
and $\mathcal{S}=\mathbb{Q}$ is a computable metric space. The basic balls
here are the open intervals with rational endpoints. In this case the notion
of computable point can be split into two: a real $x$ is lower semi-computable
if the set $\\{q\in\mathbb{Q}:q<x\\}$ is recursively enumerable and upper
semi-computable if $-x$ is lower semi-computable. It is an easy exercise to
verify that $x$ is computable if and only if it is both lower and upper semi-
computable. An example of a lower semi-computable real number which is not
computable is given by

$h=\sum_{e\in\texttt{Halt}}2^{-e}$

where Halt is the halting set (or any other r.e. set that is not decidable).

######  Example 3.3.

Let $A$ be a countable set with at least two elements. The space
$A^{\mathbb{N}}$ with the metric introduced in Subsection 2.4 has a natural
computable metric space structure using a standard enumeration of the dense
countable set of eventually constant configurations

$\mathcal{S}=\\{w\mathtt{a}^{\infty}:w\in A^{*},\mathtt{a}\in A\\}.$

In this case, the basic balls are the cylinders and thus for the case when $A$
is finite we recover the computable structure introduced in Subsection 2.4. We
will call this the canonical computable structure of Cantor spaces. In the
case where $A=\mathbb{N}$ we obtain an analogous canonical computable
structure for the Baire Space $\mathbb{N}^{\mathbb{N}}$.

######  Example 3.4.

If $(X_{i},d_{i},\mathcal{S}_{i})_{i\in\mathbb{N}}$ is a sequence of uniformly
computable metric spaces such that the distances $d_{i}$ are uniformly
bounded, then the product space

$\left(\prod_{i\in\mathbb{N}}X_{i},d,\mathcal{S}\right)\quad\text{ where
}\quad\mathcal{S}=\prod_{i\in\mathbb{N}}\mathcal{S}_{i}\quad\text{and}\quad
d((x_{i})_{i},(y_{i})_{i})=\sum_{i\in\mathbb{N}}2^{-i}d_{i}(x_{i},y_{i}),$

is a computable metric space as well.

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

$f^{-1}(B^{\prime}_{m})=U_{I_{m}},$

that is, if the preimages $f^{-1}(B^{\prime}_{m})$ of basic balls are
effectively open sets uniformly in $m$. More generally, for any $Y\subset X$,
we say $f\colon Y\to X^{\prime}$ is computable if there exists an algorithm
which, given as input some integer $m$, enumerates a set $I_{m}$ such that

$f^{-1}(B^{\prime}_{m})=U_{I_{m}}\cap Y.$

######  Remark 3.5.

For Cantor spaces $A^{\mathbb{N}},B^{\mathbb{N}}$ endowed with the canonical
computable structure given in Example 3.3, the notion of computable function
boils down to Definition 2.7.

It follows immediately from the definition that computable functions are
continuous and closed under composition. It is perhaps more intuitively
familiar, and in fact equivalent, to think of a computable function as one for
which there is an algorithm which, provided with arbitrarily good
approximations, outputs arbitrarily good approximations of $f(x)$. The formal
statement and the proof is analogous to Proposition 2.8.

####  3.1.1. Computability of closed sets and compact sets

######  Definition 3.6.

A compact set $K\subset X$ is said to be recursively compact if the inclusion

$K\subset U_{I},$

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

We remark that for a recursively compact set $K$, the inclusion $K\subset
U_{I}$ can be semi-decided for any effectively open set $U_{I}$, as it
suffices to run in parallel the above algorithm on all finite subsets
$I^{\prime}\subset I$ and halt if one of them halts.

######  Example 3.7.

The Cantor space is recursively compact. Indeed, recursive compactness for
Cantor spaces boils down to check whether a finite list of cylinders covers
the whole space, which is clearly semi-decidable (actually, even decidable,
see Remark 2.6). A similar reasoning applies to the unit interval, which is
also recursively compact.

We observe that the product of a collection of uniformly recursively compact
metric spaces is again recursively compact. We refer to [29] for a treatment
of the computability of Tychonoff’s theorem in the general case.

######  Proposition 3.8.

Let $(X_{i},d_{i},\mathcal{S}_{i})_{i\in\mathbb{N}}$ be a uniform sequence of
computable metric spaces with uniformly bounded distances. If $K_{i}\subset
X_{i}$ is uniformly recursively compact, then their product
$\prod_{i\in\mathbb{N}}K_{i}$ is recursively compact in
$\prod_{i\in\mathbb{N}}X_{i}$.

###### Proof.

To see that $\prod_{i\in\mathbb{N}}K_{i}$ is recursively compact, notice that
the projection of a rational ball in the product space to coordinate $i$
contains the whole $X_{i}$ for all $i>N$ for some sufficiently large $N$, that
we can compute from the radius of the ball. Thus, checking whether a finite
list of balls covers $\prod_{i\in\mathbb{N}}K_{i}$ boils down to check, for
finitely many $i$’s, whether a finite list of balls in $X_{i}$ covers $K_{i}$,
and this can be done by the uniform recursive compactness of the $K_{i}$. ∎

######  Remark 3.9.

Note that the product topology on a uniform sequence of computable metric
spaces has the property that the projection onto a uniform (in particular a
finite) collection of coordinates is a computable function.

######  Definition 3.10.

A set $K\subset X$ is effectively closed if it is the complement of an
effectively open set.

######  Example 3.11.

For a computable point $x\in X$, a closed ball of the form
$\overline{B}(x,r)=\\{y\in X:d(x,y)\leq r\\}$ is effectively closed if and
only if $r$ is upper semi-computable. In particular, the closure of every
basic ball is effectively closed. However, if we let $r$ be a lower semi-
computable but not computable number, then the open ball $B(x,r)$ is an
example of an effectively open set whose closure is not effectively closed.

We will make use of the following result, which is a computable version of the
fact that in a Hausdorff space, a subset of a compact set is compact if and
only if it is closed.

######  Proposition 3.12.

Let $(X,d,\mathcal{S})$ be a recursively compact computable metric space. A
subset $K\subset X$ is recursively compact if and only if it is effectively
closed.

###### Proof.

Assume $K$ is effectively closed. Then $X\setminus K$ is effectively open. Let
$U$ be a finite union of open basic balls. To see that we can semi-decide
whether $K\subset U$, simply note that $U$ covers $K$ exactly when
$U\cup(X\setminus K)$ covers $X$, which can be semi-decided since $X$ is
recursively compact. Conversely, if $K$ is recursively compact, then we can
enumerate its complement by enumerating the complement of the closure of all
the finite unions of basic balls that cover $K$. ∎

######  Remark 3.13.

An important consequence of the previous proposition is that in any
recursively compact space $X$ there is an algorithm which, given as input a
description of an effectively closed set $K$ and an effectively open set
$U_{I}$, halts if and only if $K\subset U_{I}$. In particular, we can
uniformly semi-decide if $K=\varnothing$.

We also note that if $f\colon X\to X^{\prime}$ is a computable function
between computable metric spaces, then the image of a recursively compact set
is recursively compact uniformly in the description of the set. We end this
section with the following two important propositions.

######  Proposition 3.14.

Let $f\colon X\to Y$ be a function between computable metric spaces that is
computable on a recursively compact set $K\subset X$. Then uniformly for any
basic ball $B\subset X$ there exists an effectively open set $U_{B}\subset Y$
such that $f(B\cap K)=f(K)\cap U_{B}$. In particular, if $f$ is injective it
has a computable inverse $f^{-1}\colon f(K)\to K$.

###### Proof.

Let $B$ be a basic ball. We show how to uniformly compute an effectively open
$U_{B}\subset Y$ such that $f(B\cap K)=U_{B}\cap f(K)$. As $K$ is recursively
compact, we have that $K\setminus B$ is recursively compact, and thus
$f(K\setminus B)$ is recursively compact in $Y$ uniformly on $B$. The set
$U_{B}=Y\setminus f(K\setminus B)$ is effectively open and satisfies the
required property. ∎

######  Proposition 3.15.

Let $f\colon K\to K$ be a computable function on an effectively closed subset
of a computable metric space $X$. Then the set

$\\{x\in K:f(x)=x\\}$

is effectively closed.

###### Proof.

Simply note that the function $F(x)=d(x,f(x))$ is computable on $K$, and
therefore

$X\setminus\\{x\in K:f(x)=x\\}=(X\setminus K)\cup
F^{-1}(\\{r\in\mathbb{R}:r>0\\})$

is an effectively open set. ∎

###  3.2. Computability for zero-dimensional spaces

Another interesting application of Proposition 3.12 is the construction of a
basis of clopen sets for any given recursively compact zero-dimensional subset
of a computable metric space.

######  Proposition 3.16.

Let $K$ be a zero-dimensional recursively compact subset of a computable
metric space $X$. Then one can compute a collection $(C_{n})_{n\in\mathbb{N}}$
of finite unions of basic balls in $X$ such that $(C_{n}\cap
K)_{n\in\mathbb{N}}$ forms a basis of clopen sets for $K$.

###### Proof.

Since $K$ is zero-dimensional, it has a basis of clopen sets. Let $C$ be
clopen in $K$. Since $C$ is open in $K$, there exists a set $U$ open in $X$
such that $C=U\cap K$. Since $C$ is also closed and $K$ is compact, $C$ is
compact as well, and thus the set $U$ can be taken to be a finite union of
basic balls. Now consider the collection $V_{1},V_{2},\dots$ of all finite
unions of basic balls. By what we have just shown we know it contains a basis
of clopen sets for $K$. We claim that given a finite union $V$, one can semi-
decide whether $C=V\cap K$ is clopen in $K$. Indeed, note that if $C$ is a
clopen set in $K$, then one has

$C=\overline{C}=\overline{V}\cap K$

where $\overline{V}$ is the union of the closures of the finitely many balls
defining $V$. This is equivalent to have

$\left(K\setminus C\right)\subset X\setminus\overline{V}.$

But $K\setminus C=K\setminus V$ is effectively closed, and therefore
recursively compact by Proposition 3.12. Since $X\setminus\overline{V}$ is an
effectively open set, it follows that this last relation is semi-decidable. ∎

It is a well known result of Brouwer that every zero-dimensional compact space
without isolated points is homeomorphic to the Cantor space
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$. Here we will prove an effective
version of this result. To state it we need the following notion of
computability for closed sets.

######  Definition 3.17.

A closed set $X$ is recursively enumerable (r.e.) if one can uniformly compute
a sequence $(x_{i})_{i\in\mathbb{N}}\subset X$ of points that is dense in $X$.
If $X$ is both effectively closed and r.e. then we say it is computably
closed.

######  Theorem 3.18.

Let $X$ be a nonempty recursively compact zero-dimensional subset of a
computable metric space. Then $X$ is computably homeomorphic to an effectively
closed subset $E$ of $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$. Moreover,

  * •

if $X$ is computably closed, then $E$ can be taken to be computably closed,

  * •

if $X$ is computably closed and has no isolated points, then $E$ can be taken
to be $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$.

###### Proof.

If $X$ is a singleton, then there is nothing to prove. We assume therefore
that $X$ contains at least two points. From Proposition 3.16 it follows that
one can compute a sequence $(\mathcal{P}^{n})_{n\in\mathbb{N}}$ of partitions
of $X$ made by clopen sets where each $\mathcal{P}^{n}$ is indexed as
$\\{P^{n}_{0},\dots,P^{n}_{k_{n}}\\}$ such that each set in $\mathcal{P}^{n}$
has diameter at most $2^{-n}$ and the elements of $\mathcal{P}^{n}$ are unions
of elements in $\mathcal{P}^{n+1}$. Moreover, By our assumption on $X$ we can
assume that $P_{0}$ has more than one element. Now, for each $n\in\mathbb{N}$
we let $B_{n}=\\{0,\dots,k_{n}\\}$. It follows that $B_{n}$ has at least two
elements. As $(k_{n})_{n\in\mathbb{N}}$ is a computable sequence of natural
numbers, it follows that $\prod_{n\in\mathbb{N}}B_{n}$ is an effectively
closed and recursively compact subset of $\mathbb{N}^{\mathbb{N}}$ by
Proposition 3.8. We now consider the following subset of
$\prod_{n\in\mathbb{N}}B_{n}$:

$Y=\\{y\in\prod_{n\in\mathbb{N}}B_{n}:\text{ for all $n\in\mathbb{N}$
}P^{n}_{y(n)}\cap X\neq\varnothing\text{ and }P^{k}_{y(k)}\supset
P^{k+1}_{y(k+1)}\mbox{ for every }k\in\mathbb{N}\\}.$

Observe that $Y$ is effectively closed. Indeed, we can semi-decide whether
$P^{n}_{y(n)}\cap X=\varnothing$ by the recursive compactness of $X$. The
condition $P^{k}_{y(k)}\supset P^{k+1}_{y(k+1)}$ is decidable by construction.
As $\prod_{n\in\mathbb{N}}B_{n}$ is a recursively compact subset of
$\mathbb{N}^{\mathbb{N}}$, it follows that $Y$ is recursively compact as well
by Proposition 3.12.

We now observe that $Y$ and $X$ are computably homeomorphic. We define the
function $\psi\colon Y\to X$ by the following equality:

$\\{\psi(y)\\}=\bigcap_{n\in\mathbb{N}}P^{n}_{y(n)}.$

This function is well defined, as the intersection of a nested sequence of
compact sets with diameters tending to zero must be a singleton. It is clear
from the expression above that $\psi$ is continuous, computable and bijective.
It follows from Proposition 3.14 that the inverse of $\psi$ is computable, and
thus it is a computable homeomorphism.

We shall now prove that $\prod_{n\in\mathbb{N}}B_{n}$ is recursively
homeomorphic to $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$. For this we take
$T\subset\mathbb{N}^{*}$ as the set of words
$\\{\varepsilon\\}\cup\bigcup_{n\in\mathbb{N}}B_{0}\times\dots\times B_{n}$.
Then $T$ is an infinite tree (a set of words closed by prefix) with the
property that each word can be extended by at least two different words on the
right. Furthermore, $T$ is a decidable subset of $\mathbb{N}^{*}$ and
$\prod_{n\in\mathbb{N}}B_{n}$ can be identified with the set of infinite
rooted paths in this tree.

We define a function $h\colon T\to\\{\mathtt{0},\mathtt{1}\\}^{\ast}$ in the
following recursive manner. First, $h(\epsilon)=\epsilon$. Now let us assume
that $h(w)$ has been defined for some $w\in T$. Then we compute the set of
words $\\{w_{0},\dots,w_{m}\\}$ which have $w$ as prefix, and whose length is
equal to the length of $w$ plus one, labeled in lexicographical order. As each
word in $T$ can be extended in two ways on the right, this set is nonempty and
$m\geq 1$. Let

$v_{0}=\mathtt{0},v_{1}=\mathtt{10},v_{2}=\mathtt{110},\dots,v_{m-1}=\mathtt{1}^{m-1}\mathtt{0},v_{m}=\mathtt{1}^{m},$

and define $h(w_{i})=h(w)v_{i}$, for $0\leq i\leq m$. These conditions define
$h(w)$ for every $w\in T$. From our construction it is clear that $h$ is a
computable function, it is monotone for the prefix order, and the length of
$h(w)$ tends to infinity with the length of $w$. Thus $h$ induces a function

$H\colon\prod_{n\in\mathbb{N}}B_{n}\to\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$

Given by $H(y)(n)=h(y_{0}\dots y_{k})(n)$, the $n$-th element in the word
$h(y_{0}\dots y_{k})$, for some $k$ big enough. A routine verification shows
that $H$ is a computable homeomorphism between $\prod_{n\in\mathbb{N}}B_{n}$
and $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$.

We can now prove part of our statement. The fact that $X$ is computably
homeomorphic to an effectively closed subset $E$ of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ follows by composing the computable
homeomorphism between $X$ and $Y\subset\prod_{n\in\mathbb{N}}B_{n}$, and the
computable homeomorphism between $\prod_{n\in\mathbb{N}}B_{n}$ and
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$. Computable homeomorphisms preserve
the property of being effectively closed, so the set $E$ obtained will be
effectively closed when $X$ is effectively closed. The same holds for the
property of being r.e. closed. Indeed, a computable homeomorphism sends the
dense collection of uniformly computable points in $X$ to a dense sequence of
uniformly computable points in $E$, which is therefore also r.e. closed.

We now prove that if $X$ is computably closed, nonempty, and has no isolated
points, then it is computably homeomorphic to
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$. For this purpose we make some
modifications to the proof given above. We must add some conditions to the
sequence $(\mathcal{P}^{n})_{n\in\mathbb{N}}$. The first extra condition is
that for every $n\in\mathbb{N}$, every element in $\mathcal{P}^{n}$ intersects
$X$. As $X$ is computably closed, we can decide which elements from
$\mathcal{P}^{n}$ have empty intersection with $X$, and discard those
elements. The second extra condition is that for every $n\in\mathbb{N}$ every
element in $\mathcal{P}^{n}$ contains at least two elements in
$\mathcal{P}_{n+1}$. This can be obtained by computably taking a sub-sequence
of the original sequence of partitions. The existence being assured by the
fact that $X$ has no isolated points.

After these considerations, the set $Y$ is defined in the same manner. Observe
that being a computable homeomorphic image of a computably closed set $X$, $Y$
is computably closed. Now let $T$ be the set of words (including the empty
word) $w\in\mathbb{N}^{\ast}$ such that the cylinder
$[w]\subset\mathbb{N}^{\mathbb{N}}$ has nonempty intersection with $Y$. As $Y$
is computably closed, is follows that $T$ is a computable tree. Observe that
from our choice of $\mathcal{P}^{n}$ every element in the tree has at least
two children. Then we just repeat the construction of $h$ given above on the
tree $T$. The function $H$ constructed before induces now a computable
homeomorphism between $Y$ and $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$.∎

###  3.3. Effective subshifts

Let us recall that a subshift $X\subset A^{\Gamma}$ is a closed subset which
is invariant by the shift action. A subshift $X\subset A^{\mathbb{Z}}$ is said
to be effective when it is an effectively closed subset of $A^{\mathbb{Z}}$,
that is, when the set of all words not appearing in the subshift is
recursively enumerable. This notion has been extensively used in the
literature [14, 22, 2, 17]. Our goal in this section is to generalize this
notion from $\mathbb{Z}$ to an arbitrary finitely generated group $\Gamma$.
When $\Gamma$ has decidable word problem, there is a canonical way to endow
the full $\Gamma$-shift $A^{\Gamma}$ with a computable metric structure such
that one can speak about effectively closed sets (and therefore effective
subshifts). However, as we will see, for more general groups the task is less
straightforward.

####  3.3.1. Computable structure on $A^{\Gamma}$ for a group with decidable
word problem

Let $\Gamma$ be a finitely generated group with decidable word problem. Then
there is a bijection (see Remark 2.3) $\nu\colon\mathbb{N}\to\Gamma$ for which
the pullback of the group operation to $\mathbb{N}^{2}\to\mathbb{N}$ becomes a
computable function. We now introduce a computable metric space structure on
$A^{\Gamma}$. For this purpose we consider the function

$\psi\colon A^{\mathbb{N}}\to A^{\Gamma}$
$(x_{i})_{i\in\mathbb{N}}\mapsto(x_{\nu^{-1}(g)})_{g\in\Gamma}$

which is in fact an homeomorphism, and let
$\mathcal{S}=\\{\psi(w\mathtt{a}^{\infty}):w\in A^{\ast},\mathtt{a}\in A\\}$
to be the collection of basic points in $A^{\Gamma}$. The distance $d$ on
$A^{\Gamma}$ obtained by declaring $\psi$ to be an isometry generates the
prodiscrete topology. In this way, $\mathcal{S}$ becomes a dense subset of
$A^{\Gamma}$ on which the distance $d$ is clearly computable.

######  Remark 3.19.

We note that this computable metric structure for $A^{\Gamma}$ makes the shift
action $\Gamma\curvearrowright A^{\Gamma}$ computable. In order to see this,
let $g\in\Gamma$, and let $f_{g}\colon A^{\Gamma}\to A^{\Gamma}$ be defined by
$f_{g}(x)=gx$. To show that $f_{g}$ is computable, it is enough to note that
$\psi^{-1}f_{g}\circ\psi\colon A^{\mathbb{N}}\to A^{\mathbb{N}}$ is
computable. Indeed, this function can be written as
$(x_{i})_{i\in\mathbb{N}}\to(x_{h(i)})_{i\in\mathbb{N}}$, where $h$ is a
computable bijection of $\mathbb{N}$ which comes from the computability of the
group operation.

######  Remark 3.20.

The computable metric space structure produced in this way for $A^{\Gamma}$ is
inherent to $\Gamma$ and does not depend on the choice of $\nu$. Indeed, let
$\nu^{\prime}$ be another bijection $\mathbb{N}\to\Gamma$ as before, and let
us denote by $(A^{\Gamma},d,\mathcal{S})$,
$(A^{\Gamma},d^{\prime},\mathcal{S}^{\prime})$ the computable metric space
structures associated to $\nu$ and $\nu^{\prime}$. Then
$\operatorname{id}\colon(A^{\Gamma},d,\mathcal{S})\to(A^{\Gamma},d^{\prime},\mathcal{S}^{\prime})$
is a computable homeomorphism. This can be proved by noting that
$\nu^{-1}\circ\nu^{\prime}$ is a computable bijection of $\mathbb{N}$. For
details, the reader is referred to [12, Section 2.4 and Section 5]).

Once $A^{\Gamma}$ has been endowed with its canonical computable structure,
one can naturally extend the definition of effective subshift for
$A^{\mathbb{Z}}$ to make sense in $A^{\Gamma}$ by simply requiring the
subshift to be effectively closed. Note that, by definition, a set $X\subset
A^{\Gamma}$ is effectively closed if and only if the set of patterns
$p\colon\Gamma\to A$ such that $[p]\cap X=\varnothing$ is recursively
enumerable.

We now present a construction that allows us to have a useful notion of
effective subshift when $\Gamma$ is an arbitrary finitely generated group.

####  3.3.2. Computable structure on $A^{\Gamma}$, for arbitrary finitely
generated groups

We shall prove later that for some groups, the space $A^{\Gamma}$ can _not_ be
endowed with a computable metric space structure for which the action by
translations $\Gamma\curvearrowright A^{\Gamma}$ is computable. However, the
set $A^{\Gamma}$ can always be identified with a closed subset of $A^{F}$ for
a suitable free group $F$. The idea is to use the fact that finitely generated
free groups have decidable word problem, which as we have just seen allows us
to endow $A^{F}$ with a canonical computable structure. Now to the details.

Let $\Gamma$ be a finitely generated group, which is not assumed to have
decidable word problem. Let $S$ be a finite set of generators of the group
$\Gamma$. Consider the free group $F(S)$ generated by $S$, and consider the
canonical epimorphism $\phi\colon F(S)\to\Gamma$, where every reduced word on
$S$ is mapped to its corresponding element in $\Gamma$. Let
$\widehat{\phi}\colon A^{\Gamma}\to A^{F(S)}$ be the map given by
$\widehat{\phi}(x)(w)=x(\phi(w))$ for every $w\in F(S)$.

Every subshift $X\subset A^{\Gamma}$ induces a pullback subshift
$\widehat{X}\subset A^{F(S)}$ given by

$\widehat{X}=\\{\widehat{\phi}(x)\in A^{F(S)}:x\in A^{\Gamma}\\}.$

######  Definition 3.21.

We say that a subshift $X\subset A^{\Gamma}$ is effective if for some finite
symmetric set $S$ of generators of $\Gamma$ its induced subshift $\widehat{X}$
is an effectively closed subset of $A^{F(S)}$.

It can be seen that this definition does not depend on the set of generators
$S$. Indeed, let $S^{\prime}$ be another set of generators and denote by
$\widehat{X}^{\prime}$ its pullback in $A^{F(S^{\prime})}$. For each $s\in S$,
let $\psi(s)$ be a word in $S^{\prime}$ such that $s$ is equal to $\psi(s)$ in
$\Gamma$. Then $\psi$ extends to a computable injective homomorphism from
$F(S)$ to $F(S^{\prime})$. It follows that the map
$\Psi\colon\widehat{X}\to\widehat{X}^{\prime}$ given by
$\Psi(x)(w)=x(\psi(w))$ is a computable homeomorphism. In particular,
$\widehat{X}^{\prime}$ is also effectively closed. A similar argument shows
that for a group with decidable word problem, $\widehat{X}\subset A^{F(S)}$ is
effectively closed exactly when $X\subset A^{\Gamma}$ is effectively closed
set, as $\widehat{A^{\Gamma}}$ is then effectively closed in $A^{F(S)}$.

######  Remark 3.22.

In the literature [1] there is a different computability notion for shift
spaces, and for general finitely generated groups the two definitions are not
equivalent. In Section 7 we shall provide a characterization of this other
notion and clarify the relation with ours.

######  Example 3.23.

If $\Gamma$ is recursively presented, then the full shift $A^{\Gamma}$ is
effective. Indeed, as the word problem of $\Gamma$ is recursively enumerable,
the set of patterns of the form $p:\\{1_{F(S)},w\\}\to A$ satisfying
$\underline{w}=1_{\Gamma}$ and $p(1_{F(S)})\neq p(w)$ is recursively
enumerable. The union of cylinders associated to these patterns in $A^{F(S)}$
is equal to the complement of $\widehat{A^{\Gamma}}$.

######  Remark 3.24.

Observe that the map $\widehat{\phi}$ is a homeomorphism between $X$ and
$\widehat{X}$. Moreover, we can define an action
$\Gamma\curvearrowright\widehat{X}$ by setting $gx=wx$, where $w\in F(S)$ is
any element satisfying $\phi(w)=g$. In this manner the actions
$\Gamma\curvearrowright\widehat{X}$ and $\Gamma\curvearrowright X$ are
topologically conjugate. In particular, we have that if $X$ is an effective
subshift, then $\Gamma\curvearrowright X$ is topologically conjugate to a
computable action $\Gamma\curvearrowright\widehat{X}$ where $\widehat{X}$ is
an recursively compact subset of a computable metric space. This is the
property that will allow us to generalize the notion of effective subshift to
general dynamical systems.

###  3.4. Effective dynamical systems

Let $X$ be a recursively compact subset of a computable metric space.
Similarly to the zero-dimensional case, we say that $\Gamma\curvearrowright X$
is computable action if for some finite set of generators $S$, we have that
for each $s\in S$ the group action map $f_{s}\colon X\to X$ given by
$f_{s}(x)=sx$ is a computable function. Notice that in this case, $f_{g}\colon
X\to X$ is in fact uniformly computable for all $g\in\Gamma.$ In particular,
if an action is computable, it will satisfy the definition with respect to
every finite set of generators.

We are interested in the behavior of actions as topological dynamical systems,
and thus will consider them up to topological conjugacy. Our focus will be on
those conjugacy classes that contain some computable representative.

######  Definition 3.25.

Let $X$ be a compact metrizable space and $\Gamma$ a finitely generated group.
We say that an action $\Gamma\curvearrowright X$ is an effective dynamical
system (EDS) if it is topologically conjugate to a computable action
$\Gamma\curvearrowright\widehat{X}$ for some recursively compact subset
$\widehat{X}$ of a computable metric space.

We insist in that our definition of effective dynamical system _does not_
require the space $X$ to have any computable structure or the topological
conjugacy to be computable. Given an EDS $\Gamma\curvearrowright X$, we will
refer to a topologically conjugate instance of a computable action
$\Gamma\curvearrowright\widehat{X}$ over a recursively compact subset
$\widehat{X}$ of a computable metric space as a computable representative.

######  Example 3.26.

An effective subshift $X\subset A^{\Gamma}$ is an EDS. Indeed, if $A^{\Gamma}$
is an effective subshift, then $\Gamma\curvearrowright X$ is topologically
conjugate to the action $\Gamma\curvearrowright\widehat{X}$, where
$\widehat{X}$ is the subshift defined in Definition 3.21 (see also Remark
3.24). We will see later that, conversely, the only subshifts which are EDS
are the effective ones, thus justifying the name (Proposition 7.1).

The following example shows that the conjugacy class of an effective dynamical
system can contain uncountably many systems. In particular, it contains
representatives that are not computably homeomorphic.

######  Example 3.27.

Fix some computable angle $\alpha\in[0,2\pi]$ and consider
$C_{r}=\\{x\in\mathbb{R}^{2}:\|x\|=r\\}$ to be the circle of radius $r>0$.
Note that the space $C_{r}$ is a recursively compact subset of
$\mathbb{R}^{2}$ only for computable $r$. Despite this, the conjugacy class of
the action $\mathbb{Z}\curvearrowright C_{r}$ induced by the rotation by
$\alpha$ has a computable representative, namely $\mathbb{Z}\curvearrowright
C_{1}$, and is therefore an EDS regardless of the value of $r$.

######  Example 3.28.

The action
$\operatorname{GL}_{n}(\mathbb{Z})\curvearrowright\mathbb{R}^{n}/\mathbb{Z}^{n}$
of the general linear group on the $n$-dimensional torus by left matrix
multiplication is an EDS.

######  Example 3.29.

Recall the Thompson’s groups $F$ and $T$ from Example 2.13. These groups are
more often defined in the literature as the space of piecewise linear
homeomorphisms of $[0,1]$ (in the case of $T$, of $\mathbb{R}/\mathbb{Z}$)
that preserve orientation and whose non-differentiable points are dyadic
rationals and whose slopes are all powers of 2. These maps are clearly
computable and thus it follows that the natural actions
$F\curvearrowright[0,1]$ and $T\curvearrowright\mathbb{R}/\mathbb{Z}$ are EDS.

Next we are going to show that the class of EDS is closed under computable
topological factor maps. We stress the fact that in this result we both need
both actions to be represented as computable actions in computable metric
spaces and the factor to be computable as well. In Section 8 we will later
show that without strong assumptions that enforce computability, the class of
EDS is in general not closed under topological factor maps.

######  Proposition 3.30.

Let $\Gamma$ be a finitely generated group and $X$, $Y$ be computable metric
spaces. Let $X^{\prime}\subset X$ be a recursively compact set and
$\Gamma\curvearrowright X^{\prime}$ be a computable action. Let
$\Gamma\curvearrowright Y^{\prime}\subset Y$ be a topological factor of
$\Gamma\curvearrowright X^{\prime}$ by a computable function $f\colon
X^{\prime}\to Y$. Then $Y^{\prime}$ is a recursively compact set and
$\Gamma\curvearrowright Y^{\prime}$ is a computable group action.

###### Proof.

Let $(B^{X}_{i})_{i\in\mathbb{N}}$ and $(B^{Y}_{i})_{i\in\mathbb{N}}$ be
recursive enumerations of the basic balls in $X$ and $Y$ respectively. As
$X^{\prime}$ is recursively compact and $f$ is computable, it follows that
$Y^{\prime}$ is recursively compact. Let $s\in\Gamma$ and let
$i\in\mathbb{N}$. As $f$ is computable it follows that, uniformly in $i$,
there is a recursively enumerable set $I_{i}\subset\mathbb{N}$ such that
$f^{-1}(B^{Y}_{i})=X^{\prime}\cap\bigcup_{j\in I_{i}}B^{X}_{j}$. As the action
is computable, uniformly for each $j\in\mathbb{N}$ there is a recursively
enumerable set $I^{\prime}_{j}\subset\mathbb{N}$ such that

$s^{-1}f^{-1}(B^{Y}_{i})=X^{\prime}\cap\bigcup_{j\in I_{i}}\bigcup_{k\in
I^{\prime}_{j}}B_{k}^{X}.$

Finally, as $f$ is computable and $X^{\prime}$ recursively compact, it follows
by Proposition 3.14 that uniformly for $k\in\mathbb{N}$ there is a recursively
enumerable set $I^{\prime\prime}_{k}\subset\mathbb{N}$ such that

$s^{-1}(B_{i}^{Y}\cap Y^{\prime})=f(s^{-1}f^{-1}(B_{i}^{Y}))=\bigcup_{j\in
I_{i}}\bigcup_{k\in I^{\prime}_{j}}\bigcup_{m\in
I^{\prime\prime}_{k}}B_{m}^{Y}.$

Where the first equality holds because $f$ is $\Gamma$-equivariant. It follows
the map $y\mapsto sy$ is computable and as $s$ is arbitrary, we obtain that
$\Gamma\curvearrowright Y^{\prime}$ is computable. ∎

##  4\. EDS as factors of computable actions on 0-dimensional effectively
closed sets

In this section we prove A. Let us briefly recall the standard procedure to
build a zero-dimensional topological extension of a dynamical system
$\Gamma\curvearrowright X$.

  1. (1)

First we extract a sequence $(\mathcal{P}_{n})_{n\in\mathbb{N}}$ of open
covers of $X$ with diameters tending to zero, and associate to each one of
them a subshift $Y_{n}$.

  2. (2)

Define the sequence of subshifts $(Z_{n})_{n\in\mathbb{N}}$ where
$Z_{n}=\prod_{k\leq n}Y_{k}$ with the coordinate-wise shift, and consider the
projection factor maps $\pi_{n+1}\colon Z_{n+1}\to Z_{n}$.

  3. (3)

Define the inverse limit $Z=\varprojlim Z_{n}$, this is a topological
extension of $\Gamma\curvearrowright X$.

In our proof we effectivize this construction. For this purpose, we first need
to prove effective versions of some of the steps. This includes infinite
products, inverse limits, and subshifts associated to covers.

###  4.1. Effective versions of some classical constructions.

In this section we prove effective versions of a few classical constructions
commonly used in dynamical systems, and which may therefore be of independent
interest.

####  4.1.1. Products of computable actions and inverse limit constructions

Now we show that the operations of countable product and inverse limits are
computable under mild computability assumptions. For the next two results,
$(Y_{n})_{n\in\mathbb{N}}$ will be a sequence of uniformly computable metric
spaces as in Example 3.4 and we will consider $\prod_{n\in\mathbb{N}}Y_{n}$
with its product computable metric space structure.

######  Proposition 4.1.

Let $X_{n}\subset Y_{n}$ be a sequence of subsets and $\Gamma\curvearrowright
X_{n}$ be a uniform sequence of computable actions of the finitely generated
group $\Gamma$. Then the component-wise action

$\Gamma\curvearrowright\prod_{n\in\mathbb{N}}X_{n}\subset\prod_{n\in\mathbb{N}}Y_{n}$

is computable.

###### Proof.

Let us fix $g\in\Gamma$. Let $n\in\mathbb{N}$ and let $U_{i}$ be an
effectively open subset of $X_{i}$ for $i\in\\{0,\dots,n\\}$. We verify that
the preimage by $g$ of

$U=U_{0}\times\dots\times U_{n}\times Y_{n+1}\times Y_{n+2}\times\dots$

is effectively open in $\prod_{n\in\mathbb{N}}X_{n}$ and that this process is
uniform in $n$ and the $U_{i}$. Indeed,

$g^{-1}(U)=g^{-1}(U_{0})\times\dots\times g^{-1}(U_{n})\times X_{n+1}\times
X_{n+2}\times\dots$

This set is effectively open in $\prod_{n\in\mathbb{N}}X_{n}$, and it can be
uniformly computed from $n\in\mathbb{N}$ and a description of
$U_{0},\dots,U_{n}$ because each of the $g^{-1}(U_{i})$ is effectively open in
$X_{i}$, and can be uniformly computed from a description of $U_{i}\subset
Y_{i}$. ∎

######  Proposition 4.2.

Let $\Gamma\curvearrowright X_{n}$ be as in the previous statement, where each
$X_{n}$ is now assumed to be an effectively closed subset of $Y_{n}$. Let
$(\pi_{n})_{n\geq 1}$ be a sequence of uniformly computable functions, where
each $\pi_{n+1}\colon X_{n+1}\to X_{n}$ is a topological factor map from
$\Gamma\curvearrowright X_{n+1}$ to $\Gamma\curvearrowright X_{n}$. Then the
inverse limit

$\varprojlim
X_{n}=\\{(x_{n})\in\prod_{n\in\mathbb{N}}X_{n}\mid\pi_{n+1}(x_{n+1})=x_{n},n\geq
1\\}$

is an effectively closed subset of $\prod_{n\in\mathbb{N}}Y_{n}$.

###### Proof.

Let $f\colon\prod_{n\in\mathbb{N}}X_{n}\to\prod_{n\in\mathbb{N}}X_{n}$ be the
function defined by
$(x_{n})_{n\in\mathbb{N}}\mapsto(\pi_{n+1}(x_{n+1}))_{n\in\mathbb{N}}$. We
claim that $f$ is computable. We verify that the preimage by $f$ of a set of
the form

$U=U_{0}\times\dots\times U_{n}\times X_{n+1}\times X_{n+2}\times\dots$

is effectively open in $\prod_{n\in\mathbb{N}}Y_{n}$, uniformly on $n$ and the
$U_{i}$. Indeed, the preimage $f^{-1}$ can be written as

$f^{-1}(U)=\pi_{1}^{-1}(U_{0})\times\dots\times\pi_{n+1}^{-1}(U_{n})\times
X_{n+1}\times X_{n+2}\times\dots$

This set is effectively open uniformly on the $U_{i}$ because
$(\pi_{n})_{n\geq 1}$ is a sequence of uniformly computable functions. On the
other hand, it is clear that $\varprojlim X_{n}$ equals the set of fixed
points of $f$ in $\prod_{n\in\mathbb{N}}X_{n}$. Then it follows from
Proposition 3.15 that $\varprojlim X_{n}$ is effectively closed. ∎

####  4.1.2. Effective covers and partitions, and their associated subshifts

In this subsection we fix a recursively compact set $X$ which lies in a
computable metric space $\mathcal{X}$. We start by reviewing some standard
terminology regarding covers and the construction of a subshift from a cover.
A cover $\mathcal{P}$ of $X$ is a finite collection of sets whose union equals
$X$. The cover $\mathcal{P}$ is said to be open (resp. closed) if it is formed
of open (resp. closed) sets. We say that the cover $\mathcal{P}^{\prime}$
refines $\mathcal{P}$ if every element in $\mathcal{P}^{\prime}$ is contained
in some element of $\mathcal{P}$. The join of two covers
$\mathcal{P}\lor\mathcal{P}^{\prime}$ is the cover $\\{P\cap P^{\prime}\mid
P\in\mathcal{P},P^{\prime}\in\mathcal{P}^{\prime}\\}$. Given a group action
$\Gamma\curvearrowright X$ and a finite subset $F\subset\Gamma$, we write
$\bigvee_{g\in F}g^{-1}\mathcal{P}$ for the join of all $g^{-1}\mathcal{P}$
for $g\in F$. The diameter of the cover $\mathcal{P}$ is the maximum of the
diameters of its elements. An open cover $\mathcal{P}$ of $X$ is said to be
generating for the group action $\Gamma\curvearrowright X$ if for each
$\varepsilon>0$ there is a finite subset $F\subset\Gamma$ such that
$\bigvee_{g\in F}g^{-1}\mathcal{P}$ has diameter at most $\varepsilon$.

Given a cover labeled as $\mathcal{P}=\\{P_{0},\dots,P_{n}\\}$, we define the
subshift cover $Y(\Gamma\curvearrowright X,\mathcal{P})$ by

$Y(\Gamma\curvearrowright
X,\mathcal{P})=\\{y\in\\{0,\dots,n\\}^{\Gamma}:\mbox{ exists }x\in X\mbox{
such that for every }g\in\Gamma,g^{-1}x\in\overline{P_{y(g)}}\\}.$

The idea behind this definition is that every configuration in the subshift
labels the orbit of some element $x\in X$ under the action
$\Gamma\curvearrowright X$ by indicating the elements of $\mathcal{P}$ it
hits. A compactness argument shows that a configuration $y$ lies in
$Y(\Gamma\curvearrowright X,\mathcal{P})$ if and only if for every pattern
$p\colon F\to\\{0,\dots,n\\}$ which occurs in $y$, the set

$D(p):=\bigcap_{g\in F}g^{-1}(\overline{P_{p(g)}}\cap X).$

is nonempty. In particular, $Y(\Gamma\curvearrowright X,\mathcal{P})$ is
indeed a subshift. Now we prove that this well known construction is
computable when the cover is made by effectively closed sets.

######  Definition 4.3.

A cover $\mathcal{P}$ of $X$ is called effective if it is formed of
effectively closed sets.

######  Proposition 4.4.

Let $\Gamma\curvearrowright X$ be a computable action of a finitely generated
group, and let $F(S)\curvearrowright X$ be the induced action. Then the
associated subshift $Y(F(S)\curvearrowright X,\mathcal{P})$ is effective
uniformly for all effective covers $\mathcal{P}$.

###### Proof.

Fix a finite set of generators $S$ of $\Gamma$. It suffices to show that the
set of patterns $p\colon F(S)\to\\{0,\dots,n\\}$ for which the set $D(p)$ is
empty is semi-decidable. Observe that $D(p)$ is an effectively closed subset
of $\mathcal{X}$, uniformly in $p$. Indeed, each $P_{i}\cap X$ is effectively
closed, the preimage of an effectively closed set by a computable function is
effectively closed, and the finite intersection of effectively closed sets is
effectively closed. Thus, we can uniformly semi-decide whether ${D(p)}$ is
empty using the recursive compactness of $\mathcal{X}$ (see Definition 3.6 and
Remark 3.13). ∎

Now we turn to the construction of effective covers. These covers will be
obtained from elements of the form $\overline{B_{i}}\cap X$, where $B_{i}$ are
basic balls in $\mathcal{X}$.

######  Proposition 4.5.

A cover of $X$ whose elements are finite unions of elements of the form
$\overline{B}\cap X$, where $B$ are basic balls in $\mathcal{X}$, is
effective.

###### Proof.

This follows from the fact that $X$ is effectively closed, and that the
topological closure of a basic ball in $\mathcal{X}$ is effectively closed
(see Example 3.11). ∎

The following construction provides a uniform sequence of refined effective
covers at any desired resolution.

######  Lemma 4.6.

There is an algorithm which on input $n\in\mathbb{N}$ computes an effective
cover $\mathcal{P}_{n}$ of $X$ with diameter at most $2^{-n}$, and such that
for every $n\in\mathbb{N}$, $\mathcal{P}_{n+1}$ refines $\mathcal{P}_{n}$ and
the inclusion of elements in $\mathcal{P}_{n+1}$ to elements in
$\mathcal{P}_{n}$ is decidable uniformly on $n$. Moreover, if $X$ is a zero
dimensional set, we can add the extra condition that the restriction of the
elements in $\mathcal{P}$ to $X$ forms a partition of $X$.

###### Proof.

Fix $\mathcal{P}_{0}$ as any cover of $X$ made by (the closure of) basic balls
of radius one. The algorithm proceeds inductively on $n\in\mathbb{N}$, that
is, after it has computed $\mathcal{P}_{0},\dots,\mathcal{P}_{n}$ with the
desired properties, it computes $\mathcal{P}_{n+1}$ as follows. Let
$\\{V_{i}\\}_{i\in\mathbb{N}}$ be an effective enumeration of all finite
unions of basic balls. First observe that there is a finite subset $I$ of
$\mathbb{N}$ such that the set $\\{V_{i}\mid i\in I\\}$ satisfies the
following conditions:

  1. (1)

$V_{i}$ has diameter at most $2^{-(n+1)}$.

  2. (2)

$\overline{V}_{i}$ is contained in the interior of some of the elements of
$\mathcal{P}_{n}$

  3. (3)

The union of $V_{i}$ for $i\in I$ contains $X$

  4. (4)

If $X$ is zero dimensional, then the sets $\overline{V_{i}}\cap X$ are
disjoint.

The existence of such a finite set of basic balls satisfying the first three
conditions follows from the fact that $X$ is compact and that the set
$\\{V_{i}\mid i\in\mathbb{N}\\}$ is a basis for the topology. If $X$ is zero
dimensional, then the last condition can be added because by Proposition 3.16
we can take the basic sets to be clopen. We now observe that it is semi-
decidable whether a finite subset $I$ of $\mathbb{N}$ satisfies the conditions
above. Note that this suffices to compute such a set by exhaustive search. The
first condition is trivial, the semi-decidability of the second follows from
the fact that $\overline{V}_{i}\cap X$ is recursively compact and the interior
of the elements in the partition are effectively open. The semi-decidability
of the third condition comes from the recursive compactness of $X$. For the
fourth condition, it suffices to note that in a recursively compact space it
is semi-decidable whether two effectively closed sets have empty intersection
(recall that in a recursively compact space we can semi-decide whether an
effectively closed subset is empty, the intersection of two effectively closed
sets is effectively closed, and this is a computable operation on the
descriptions of the sets). ∎

######  Proposition 4.7.

If $\Gamma\curvearrowright X$ admits a generating open cover, then it admits a
generating effective cover.

###### Proof.

Let $\mathcal{P}$ be a generating open cover of $\Gamma\curvearrowright X$. We
construct a new cover $\mathcal{P}^{\prime}$ as follows. Let $\mathcal{J}$ be
the collection of all sets of the form $B_{i}\cap X$ which are contained in
some element of $\mathcal{P}$, where $B_{i}$ is a basic ball in $\mathcal{X}$.
The fact that basic balls constitute a basis for a topology of $\mathcal{X}$
implies that $\mathcal{J}$ is an open cover of $X$. As $X$ is compact, it
follows that there is a finite subset $\mathcal{J}^{\prime}\subset\mathcal{J}$
which is also an open cover of $X$. As $\mathcal{J}^{\prime}$ refines
$\mathcal{P}$, it follows that it is also a generating cover of
$\Gamma\curvearrowright X$. Finally we define $\mathcal{P}^{\prime}$ as the
closed cover obtained by taking the topological closure of all elements in
$\mathcal{J}^{\prime}$. By construction, $\mathcal{P}^{\prime}$ is a closed
cover of $X$ which is generating for the action $\Gamma\curvearrowright X$,
and it follows from Proposition 4.5 that $\mathcal{P}^{\prime}$ is an
effective cover. ∎

We remark that in the previous proposition we do not claim the cover
$\mathcal{P}^{\prime}$ to be computable uniformly from a description of
$\Gamma\curvearrowright X$, just its existence.

######  Proposition 4.8.

If $\Gamma\curvearrowright X$ admits a generating open cover and $X$ is zero
dimensional, then $\Gamma\curvearrowright X$ admits an effective generating
cover which is also a partition.

###### Proof.

It follows from the hypotheses that $X$ admits a generating open cover
$\mathcal{P}$ which is a partition of $X$. Indeed, let $\mathcal{P}_{0}$ be an
open cover for $X$ which is generating for $\Gamma\curvearrowright X$. As $X$
is zero-dimensional, there is an open cover $\mathcal{P}$ of $X$ which refines
$\mathcal{P}_{0}$ and constitutes a partition of $X$. Observe that the cover
$\mathcal{P}$ is also generating for $\Gamma\curvearrowright X$ because it
refines $\mathcal{P}_{0}$.

By repeating the construction in the proof of Proposition 4.7 to the cover
$\mathcal{P}=\\{P_{0},\dots,P_{n}\\}$ , we obtain a finite open cover
$\mathcal{J}^{\prime}$ of $X$ which refines $\mathcal{P}$, and such that every
element in $\mathcal{J}^{\prime}$ has the form $B\cap X$, where $B$ is a basic
ball in $\mathcal{X}$. We define a new cover
$\mathcal{P}^{\prime}=\\{P^{\prime}_{0},\dots,P^{\prime}_{n}\\}$ by the
following condition. For every $i\in\\{0,\dots,n\\}$, $P^{\prime}_{i}$ is the
union of all elements in $\mathcal{J}^{\prime}$ which are contained in
$P_{i}$. The fact that $\mathcal{P}$ is a partition of $X$ implies that the
same holds for $\mathcal{P}^{\prime}$. It is also clear that
$\mathcal{P}^{\prime}$ is a generating cover. We now verify that
$\mathcal{P}^{\prime}$ is an effective cover. Indeed, the fact that
$\mathcal{P}^{\prime}$ is a partition implies that the elements of
$\mathcal{P}^{\prime}$ are closed in $X$. In particular we can write

$P^{\prime}_{i}=\overline{P^{\prime}_{i}}=\bigcup_{m\in M}\overline{B_{m}}\cap
X$

where $M$ is a finite subset of $\mathbb{N}$ and $B_{m}$ are rational balls.
Here topological closures can be taken in $X$ and in $\mathcal{X}$, they
coincide because $X$ is a closed subset of $\mathcal{X}$ and we consider $X$
with the subspace topology. Now it follows from the previous set equality and
Proposition 4.5 that $\mathcal{P}^{\prime}$ is also an effective cover. ∎

###  4.2. Proof of main results

We start with the following observation for computable actions on zero
dimensional spaces.

######  Proposition 4.9.

Let $\Gamma\curvearrowright X$ be a computable action, where $X$ is zero-
dimensional subset of a computable metric space. Then $\Gamma\curvearrowright
X$ is topologically conjugate to a computable action $\Gamma\curvearrowright
Y$, where $Y$ is an effectively closed subset of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$.

###### Proof.

This follows by conjugating the action $\Gamma\curvearrowright X$ with a
computable homeomorphism between $X$ and an effectively closed subset of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$, whose existence is guaranteed by
Theorem 3.18. ∎

We are now ready to present the proof of our main result.

######  Theorem 4.10 (A).

Let $\Gamma\curvearrowright X$ be an EDS, where $\Gamma$ is a finitely
generated and recursively presented group. Then $\Gamma\curvearrowright X$ is
the topological factor of a computable action of an effectively closed subset
of $\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$.

###### Proof.

We start by replacing $\Gamma\curvearrowright X$ by a computable
representative, as defined in Subsection 3.4. As explained at the beginning of
this section, we will construct a topological extension of
$\Gamma\curvearrowright X$ as the inverse limit of a sequence of subshifts.

Let $S$ be a finite set of generators of $\Gamma$ and $F(S)$ be the free group
generated by $S$. Let $F(S)\curvearrowright X$ be the action induced from
$\Gamma\curvearrowright X$ and notice it is computable. We apply the tools
from Subsection 4.1.2 to the action $F(S)\curvearrowright X$. Let
$(\mathcal{P}^{n})_{n\in\mathbb{N}}$ be a sequence of effective covers as in
Lemma 4.6. For each $\mathcal{P}^{n}=\\{P^{n}_{1},\dots,P^{n}_{m_{n}}\\}$ we
set $A_{n}$ to be the alphabet $\\{0,\dots,m_{n}\\}$, and we let
$Y(F(S)\curvearrowright X,\mathcal{P}^{n})$ be the subshift cover associated
to the action $F(S)\curvearrowright X$ and the cover $\mathcal{P}^{n}$. By
Proposition 4.4 and Lemma 4.6, each $Y(F(S)\curvearrowright
X,\mathcal{P}^{n})$ is an effective subshift, and the sequence
$(Y(F(S)\curvearrowright X,\mathcal{P}^{n}))_{n\in\mathbb{N}}$ is uniformly
effective.

It is possible that some elements in $F(S)$ which are mapped to the identity
element in $\Gamma$ (and thus act trivially on $X$), act non-trivially on
$Y(\Gamma\curvearrowright X,\mathcal{P}^{n})$. This is solved as follows. For
each $n$, we define $Y_{n}$ by

$Y_{n}=Y(F(S)\curvearrowright
X,\mathcal{P}^{n})\cap\widehat{A_{n}^{\Gamma}}\subset A_{n}^{F(S)},$

where $\widehat{A_{n}^{\Gamma}}$ is the pullback of $A_{n}^{\Gamma}$ to
$F(S)$. As $\Gamma$ is recursively presented, the set
$\widehat{A_{n}^{\Gamma}}$ is effectively closed (Example 3.23). As $Y_{n}$ is
uniformly the intersection of two effectively closed sets, then $Y_{n}$ is
effectively closed, uniformly in $n$.

We now build a zero-dimensional topological extension of
$\Gamma\curvearrowright X$, and then we verify the computability of the
construction. We define a $F(S)$-subshift $Z_{n}$ on alphabet
$B_{n}=A_{0}\times\dots\times A_{n}$ by the following two conditions:

  1. (1)

$Z_{n}\subset Y_{0}\times\dots\times Y_{n}$.

  2. (2)

For each $z\in Z_{n}$ and for each $w\in F(S)$ with $z(w)=(e_{0},\dots,e_{n})$
we have

$P^{n}_{e_{n}}\subset\dots\subset P^{0}_{e_{0}}.$

For each $n$, let $\pi_{n+1}\colon Z_{n+1}\to Z_{n}$ be the map which removes
the last component of the tuple. Then let $Z$ be the inverse limit of
dynamical systems

$Z=\varprojlim
Z_{n}=\\{(z_{n})\in\prod_{n\in\mathbb{N}}Z_{n}\mid\pi_{n+1}(x_{n+1})=x_{n},n\geq
1\\}\subset\prod_{n\in\mathbb{N}}B_{n}^{F(S)}.$

We now go into some computability considerations. First observe that for each
$n\in\mathbb{N}$, $Z_{n}$ is an effectively closed subset of $B_{n}^{F(S)}$.
As $(Y_{n})$ is a uniform sequence of effectively closed sets, we can semi-
decide whether the first condition fails. Moreover the second defining
condition of $Z_{n}$ is decidable, uniformly on $n$, by construction of the
sequence $(\mathcal{P}^{n})_{n\in\mathbb{N}}$ (Lemma 4.6). Thus
$(Z_{n})_{n\in\mathbb{N}}$ is a uniform sequence of effective
$F(S)$-subshifts. It is also clear that $(\pi_{n})_{n\geq 1}$ is a uniform
sequence of computable functions, which are also factor maps. Now we claim
that $Z$ is a recursively compact subset of
$\prod_{n\in\mathbb{N}}B_{n}^{F(S)}$. This follows from three facts:

  1. (1)

$Z$ is an effectively closed subset of $\prod_{n\in\mathbb{N}}B_{n}^{F(S)}$ by
Proposition 4.2.

  2. (2)

The product $\prod_{n\in\mathbb{N}}B_{n}^{F(S)}$ is recursively compact by
Proposition 3.8.

  3. (3)

An effectively closed subset of a recursively compact computable metric space
is recursively compact (Proposition 3.12).

The action $F(S)\curvearrowright\prod_{n\in\mathbb{N}}B_{n}^{F(S)}$ is
computable by Proposition 4.1, and then the same holds for
$F(S)\curvearrowright Z$. By construction, every element $w\in F(S)$ which
corresponds to the identity element in $\Gamma$ acts trivially on $Z$, and
thus we can define an action $\Gamma\curvearrowright Z$ by the expression
$gz=wz$, where $w\in F(S)$ is any element with $\underline{w}=g$. It remains
to verify that $\Gamma\curvearrowright Z$ is a topological extension of
$\Gamma\curvearrowright X$. This is well known, but we sketch the argument by
completeness.

We define a topological factor $\phi\colon Z\to X$ as follows. First, for each
$n\in\mathbb{N}$ we define $\nu_{n}\colon Z\to Y_{n}$ as the function which
sends $z=(z_{n})_{n\in\mathbb{N}}$ to the configuration $\nu(z)$ given by
$\nu(z)(w)=(z_{n})(w)(n)$, the $n$-th component of $(z_{n})(w)\in B_{n}$. We
now define $\phi(z)$ by the expression

$\\{\phi(z)\\}=\bigcap_{n\in\mathbb{N}}P^{n}_{\nu_{n}(z)(1_{F(S)})}.$

The function $\phi$ is well defined, as a nested intersection of nonempty
compact sets with diameter tending to zero must be a singleton. It is
straightforward to verify that $\phi$ is continuous, surjective, and it
commutes with the actions $\Gamma\curvearrowright X$ and
$\Gamma\curvearrowright Z$.

We have proved that $\Gamma\curvearrowright Z$ is a computable action on a
recursively compact and zero-dimensional subset of a computable metric space,
and that it is a topological extension of $\Gamma\curvearrowright X$. Now by
Proposition 4.9, the action $\Gamma\curvearrowright Z$ is topologically
conjugate to a computable action on an effectively closed subset of
$\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$. This finishes the proof. ∎

We end this section by proving that when the action admits a generating
partition, the extension can be taken as an effective subshift. In the zero-
dimensional regime this is the computable version of the fact that subshifts
are precisely the expansive actions on zero-dimensional sets.

######  Theorem 4.11.

Let $\Gamma\curvearrowright X$ be an EDS, where $\Gamma$ is a finitely
generated and recursively presented group and the action admits a generating
open cover. Then $\Gamma\curvearrowright X$ is a topological factor of an
effective $\Gamma$-subshift.

Moreover, if $X$ is zero-dimensional, then $\Gamma\curvearrowright X$ is
topologically conjugate to an effective $\Gamma$-subshift and the recursively
presented hypothesis on $\Gamma$ can be removed.

###### Proof.

We first prove the result assuming that $\Gamma$ is recursively presented. By
Proposition 4.7, $\Gamma\curvearrowright X$ admits an effective generating
cover $\mathcal{P}$. If $X$ is zero-dimensional, then by Proposition 4.8 we
can assume that $\mathcal{P}$ is also a partition.

Let $S$ be a finite set of generators of $\Gamma$ and let $F(S)$ be the free
group generated by $S$. Let $F(S)\curvearrowright X$ be the action induced by
$\Gamma\curvearrowright X$. Consider the subshift $Y(F(S)\curvearrowright
X,\mathcal{P})$ defined in Subsection 4.1.2. By Proposition 4.4
$Y(F(S)\curvearrowright X,\mathcal{P})$ is effective.

It is possible that some elements in $F(S)$ which are mapped to the identity
element in $\Gamma$ and thus act trivially on $X$, act non-trivially on
$Y(\mathcal{P})$. Let $Y$ be given by

$Y=Y(F(S)\curvearrowright X,\mathcal{P})\cap\widehat{A^{\Gamma}},$

where $\widehat{A^{\Gamma}}$ is the pullback of $A^{\Gamma}$ in $F(S)$. As
$\Gamma$ is recursively presented, the set $\widehat{A^{\Gamma}}$ is
effectively closed (Example 3.23), and thus $Y$ is an effective subshift.

It is a standard fact that $X$ is a topological factor of $Y$ thanks to the
fact that $\mathcal{P}$ is a generating cover. We sketch the argument for
completeness. Let $(F_{n})_{n\in\mathbb{N}}$ be an increasing sequence of
finite subsets of $F(S)$ whose union is $F(S)$. For each $y\in
Y(F(S)\curvearrowright X,\mathcal{P})$, we define $D(y)$ as the following
subset of $X$:

$D(y)=\bigcap_{n\in\mathbb{N}}D(y|_{F_{n}}).$

Recall that $D(p)$, for a pattern $p$, was defined in Subsection 4.1.2. For
each $y\in Y$ the set $D(y)$ is a singleton, being a nested intersection of a
nested intersection of nonempty compact sets with diameter tending to zero.
Indeed, for each $n$ the set $D(y|_{F_{n}})$ is contained in the cover
$\bigvee_{g\in F_{n}}g^{-1}\mathcal{P}$, and the diameters of these elements
tend to zero by definition of generating cover.

We can now define a topological factor map $\phi\colon Y\to X$ by the
expression

$\\{\phi(y)\\}=D(y).$

It is straightforward to verify that $\phi$ is continuous, surjective, and it
commutes with the actions $\Gamma\curvearrowright X$ and
$\Gamma\curvearrowright Y$. Moreover, if $X$ is zero-dimensional, then $\phi$
is also injective because $\mathcal{P}$ is a partition of $X$. Thus in this
case, $\phi$ is also a topological conjugacy.

We have proved the claim for recursively presented groups. We now prove that
if $X$ is zero-dimensional, the hypothesis that $\Gamma$ is recursively
presented can be removed. This is just because a topological conjugacy
preserves the set of elements which act trivially. More precisely, recall that
$F(S)\curvearrowright X$ is the action induced by $\Gamma\curvearrowright X$.
As $F(S)$ has decidable word problem, the previous construction shows that the
action $F(S)\curvearrowright X$ is topologically conjugate to an effectively
closed $F(S)$-subshift $Y$. Being a topological conjugacy, every element in
$F(S)$ which maps to the trivial element of $\Gamma$ must act trivially. Thus
we can define a $\Gamma$-subshift $Z$ given by

$Z=\\{z\in A^{\Gamma}:y\in Y\mbox{ where }y(w)=z(\underline{w})\mbox{ for
every }w\in F(S)\\}.$

It is straightforward that the pullback $\widehat{Z}$ to $F(S)$ is precisely
$Y$, and thus $Z$ is an effective $\Gamma$-subshift as required. ∎

##  5\. Simulation by subshifts of finite type

The main motivation behind A is that it can be used to enhance several results
in the literature that characterize zero-dimensional effective dynamical
systems as topological factors of subshifts of finite type. We shall provide a
general definition that will help us to summarize most of these results.

Consider two groups $\Gamma,H$ and suppose there exists an epimorphism
$\psi\colon\Gamma\to H$, that is, that $H$ is a quotient of $\Gamma$. Given an
action $H\curvearrowright X$, recall that the induced action of
$H\curvearrowright X$ to $\Gamma$ is the action $\Gamma\curvearrowright X$
which satisfies that $g\cdot x=\psi(g)\cdot x$ for every $g\in\Gamma$.

######  Definition 5.1.

Let $\Gamma$ and $H$ be finitely generated groups and $\psi\colon\Gamma\to H$
be an epimorphism. We say $\Gamma$ simulates $H$ (through $\psi$) if for every
effectively closed set $X\subset\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ and
every computable action $H\curvearrowright X$ there exists a $\Gamma$-SFT $Y$
such that the induced action $\Gamma\curvearrowright X$ is a topological
factor of $\Gamma\curvearrowright Y$.

If the map $\psi$ in the definition above is clear then we don’t mention it
(for instance, if $\Gamma$ is a direct product of $H$ with another group we
assume that $\psi$ is the projection to $H$). Furthermore, if $\psi$ is an
isomorphism, we say that $\Gamma$ is a self-simulable group. Let us briefly
summarize a few of the simulation results available in the literature

######  Theorem 5.2.

The following simulation results hold111In references [22, 4, 3] the
simulation results are stated differently, using subactions rather than an
induced action. However, they also hold in our terminology (the result in [3]
is stated only for expansive actions, but it can be generalized with a slight
modification in the proof which will be covered in an upcoming article).

  1. (1)

[22] $\Gamma=\mathbb{Z}^{3}$ simulates $\mathbb{Z}$.

  2. (2)

[4] Let $H$ be a finitely generated group, $d\geq 2$ and $\varphi\colon
G\to\operatorname{GL}_{d}(\mathbb{Z})$. Then the semidirect product
$\Gamma=\mathbb{Z}^{d}\rtimes_{\varphi}H$ simulates $H$ (through the
projection epimorphism).

  3. (3)

[3] Let $H,G_{1},G_{2}$ be finitely generated groups. Then $\Gamma=H\times
G_{1}\times G_{2}$ simulates $H$.

  4. (4)

[6] Let $H,K$ be finitely generated groups, suppose $H$ is nonamenable and
that $K$ has decidable word problem, then $\Gamma=H\times K$ simulates $H$.

  5. (5)

[5] The following groups are self-simulable:

     * •

The direct product of any two finitely generated nonamenable groups.

     * •

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

     * •

Thompson’s group $V$ and the Brin-Thompson’s groups $nV$ for $n\geq 1$.

     * •

Finitely generated non-amenable Branch groups.

     * •

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

     * •

The Braid groups $B_{n}$ for $n\geq 7$ strands.

We can enhance all of the above results using A.

######  Theorem 5.3 (B).

Let $\Gamma,H$ be finitely generated groups and $\psi\colon\Gamma\to H$ be an
epimorphism. Suppose that $H$ is recursively presented, then $\Gamma$
simulates $H$ if and only if for every effective dynamical system
$H\curvearrowright X$ the induced action of $\Gamma$ is a topological factor
of a $\Gamma$-SFT.

###### Proof.

Suppose first that for every EDS $H\curvearrowright X$ the induced action of
$\Gamma$ is a topological factor of a $\Gamma$-SFT. As a computable action on
an effectively closed zero-dimensional set is in particular an EDS, it follows
that $\Gamma$ simulates $H$.

Conversely, let $H\curvearrowright X$ be an EDS. As $H$ is recursively
presented, A implies that there exists an effectively closed set
$\widetilde{X}\subset\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{N}}$ and a
computable action $H\curvearrowright\widetilde{X}$ such that
$H\curvearrowright X$ is a topological factor of
$H\curvearrowright\widetilde{X}$. Taking the induced action of $\Gamma$ of
these two actions it follows that $\Gamma\curvearrowright X$ is a topological
factor of $\Gamma\curvearrowright\widetilde{X}$. As $\Gamma$ simulates $H$,
there exists a $\Gamma$-SFT $Y$ which factors onto
$\Gamma\curvearrowright\widetilde{X}$ and thus onto $\Gamma\curvearrowright
X$. ∎

Let us illustrate how B can be applied with a few examples.

######  Example 5.4.

As mentioned in Example 3.28, the action
$\operatorname{GL}_{n}(\mathbb{Z})\curvearrowright\mathbb{R}^{n}/\mathbb{Z}^{n}$
by left matrix multiplication is an EDS. For $n\geq 5$ the group
$\operatorname{GL}_{n}(\mathbb{Z})$ is both recursively presented and self-
simulable, thus it follows by B that there exists a
$\operatorname{GL}_{n}(\mathbb{Z})$-SFT which topologically factors onto
$\operatorname{GL}_{n}(\mathbb{Z})\curvearrowright\mathbb{R}^{n}/\mathbb{Z}^{n}$.

######  Example 5.5.

Let $\\{\beta_{i}\\}_{i=1}^{4}$ be four computable points in
$\mathbb{R}/\mathbb{Z}$. Consider $F_{2}\times F_{2}=\langle
a_{1},a_{2}\rangle\ast\langle a_{3},a_{4}\rangle$ and the action $F_{2}\times
F_{2}\curvearrowright\mathbb{R}/\mathbb{Z}$ given by $a_{i}\cdot
x=x+\beta_{i}\bmod{\mathbb{Z}}$ for $i\in\\{1,\dots,4\\}$. As $F_{2}\times
F_{2}$ is recursively presented and self-simulable, it follows by B that there
exists an $(F_{2}\times F_{2})$-SFT which topologically factors onto
$F_{2}\times F_{2}\curvearrowright\mathbb{R}/\mathbb{Z}$.

######  Example 5.6.

Let $G$ be a group, $n\geq 2$ and consider $\Delta_{n}(G)\subset G^{n}$ the
space of all $n$-tuples of elements of $G$ whose product is trivial, that is

$\Delta_{n}(G)=\\{(x_{1},\dots,x_{n})\in G^{n}:x_{1}\cdots x_{n}=1_{G}\\}$

The braid group $B_{n}$ on $n$ strands acts on $\Delta_{n}(G)$ by

$\sigma_{i}(x_{1},\dots,x_{i-1},x_{i},x_{i+1},\dots,x_{n})=(x_{1},\dots,x_{i-1},x_{i+1},x_{i+1}^{-1}x_{i}x_{i+1},x_{i+2},\dots,x_{n}).$

Where $1\leq i\leq n-1$ and $\sigma_{i}$ is the element of $B_{n}$ which
crosses strands $i$ and $i+1$ (for the definition of Braid group, refer to
[8]).

In [5] it was proven that Thompson’s group $F$ (see Example 2.13) is self-
simulable if and only if $F$ is non-amenable, which is a longstanding open
question. We can therefore strengthen the characterization of the potential
amenability of $F$ in the following way:

######  Corollary 5.7.

Thompson’s group $F$ is amenable if and only if there exists an EDS
$F\curvearrowright X$ which is not the topological factor of an $F$-SFT.

If we let $G$ be any compact topological group which admits a computable
structure such that group multiplication is a computable map, for instance the
group of unitary complex matrices
$G=U(k)\leqslant\operatorname{GL}_{k}(\mathbb{C})$ for some $k\geq 1$, then
$\Delta_{n}(G)$ is an effectively closed set of $G^{n}$ and the action
$B_{n}\curvearrowright\Delta_{n}(G)$ is computable. It follows that if $n\geq
7$ then there exists a $B_{n}$-SFT which topologically factors onto
$B_{n}\curvearrowright\Delta_{n}(G)$.

In the literature, there are a few simulation results which apply exclusively
to expansive maps. More precisely, let $\Gamma$ and $H$ be finitely generated
groups and $\psi\colon\Gamma\to H$ be an epimorphism. We say $\Gamma$
simulates expansive actions of $H$ (through $\psi$) if for every effective
subshift $X\subset A^{H}$ there exists a $\Gamma$-SFT $Y$ such that the
pullback subshift $\Gamma\curvearrowright X$ is a topological factor of
$\Gamma\curvearrowright Y$. The most famous results are due to Aubrun and
Sablik [2] and Durand, Romaschenko and Shen [17] which state that
$\mathbb{Z}^{2}$ simulates expansive actions of $\mathbb{Z}$ (through the
projection epimorphism).

In light of Theorem 4.11, we can improve the expansive simulation theorems in
the following way

######  Theorem 5.8.

Let $\Gamma,H$ be finitely generated groups and $\psi\colon\Gamma\to H$ be an
epimorphism. Suppose that $H$ is recursively presented, then $\Gamma$
simulates expansive actions of $H$ if and only if for every effective
dynamical system $H\curvearrowright X$ which admits a generating cover (in
particular, every expansive EDS) the induced action of $\Gamma$ is a
topological factor of a $\Gamma$-SFT.

##  6\. Algebraic actions as effective dynamical systems

In this section we will show that, under mild conditions, algebraic actions
are effective dynamical systems and thus we can apply the results of the
previous sections on them.

######  Definition 6.1.

Let $\Gamma$ be a countable group and $X$ be a compact metrizable abelian
group. We say that $\Gamma\curvearrowright X$ is an algebraic action if
$\Gamma$ acts by continuous automorphisms of $X$.

Next we provide a few examples to give an idea of what algebraic actions look
like. The reader can find a plethora of interesting examples in [32].

######  Example 6.2.

Let $X=(\mathbb{R}/\mathbb{Z})^{2}$ be the torus (with pointwise addition).
For every $A\in\operatorname{GL}_{2}(\mathbb{Z})$ the action
$\mathbb{Z}\curvearrowright X$ given by $n\cdot x=A^{n}x$ is algebraic.

######  Example 6.3.

Let $\Gamma$ be a countable group and consider
$X=(\mathbb{R}/\mathbb{Z})^{\Gamma}$ with pointwise addition as the group
operation. Then $X$ is a compact metrizable abelian group and the shift action
$\Gamma\curvearrowright X$ given by $(g\cdot x)(h)=x(g^{-1}h)$ for every $x\in
X$ and $g,h\in\Gamma$ is algebraic.

######  Example 6.4.

Let $e_{1}=(1,0),e_{2}=(0,1)$ in $\mathbb{Z}^{2}$ and consider

$X=\\{x\in(\mathbb{R}/\mathbb{Z})^{\mathbb{Z}^{2}}:\mbox{for every
}u\in\mathbb{Z}^{2},x(u)+x(u+e_{1})+x(u+e_{2})=0\bmod{\mathbb{Z}}\\}.$

Then $X$ is a compact metrizable abelian group (with pointwise addition) and
the shift action $\mathbb{Z}^{2}\curvearrowright X$ is algebraic.

An interesting property of algebraic dynamical systems is that they can all be
represented in a canonical way through the use of Pontryagin duality. This
identification is well established in the literature (it can be found for
$\mathbb{Z}^{d}$ in [32] and for a general countable group in [24, Chapter
13]), so we shall provide a relatively short account of the main facts. A
reader who is already familiar with the basics of algebraic actions of
countable groups can skip directly to the paragraph above the definition of
recursively presented algebraic action (Definition 6.5).

Let $\Gamma$ be a countable group. The integral group ring
$\mathbb{Z}[\Gamma]$ (usually denoted in the literature as $\mathbb{Z}\Gamma$
to simplify the notation) is the set of all finitely supported maps
$p\colon\Gamma\to\mathbb{Z}$ endowed with pointwise addition and with
polynomial multiplication. That is, for $p,q\in\mathbb{Z}[\Gamma]$ and
$g\in\Gamma$ then $(p+q)(g)=p(g)+q(g)$ and $p\cdot
q(g)=\sum_{h\in\Gamma}p(gh^{-1})q(h)$. For this reason, we usually denote
elements $p\in\mathbb{Z}[\Gamma]$ as finite formal sums $p=\sum_{i\in
I}c_{i}g_{i}$ with $c_{i}\in\mathbb{Z},g_{i}\in\Gamma$. We also endow
$\mathbb{Z}[\Gamma]$ with the $*$-operation given by $p^{*}=\sum_{i\in
I}c_{i}g_{i}^{-1}$. We remark that for $x\in(\mathbb{R}/\mathbb{Z})^{\Gamma}$
and $p=\sum_{i\in I}c_{i}g_{i}\in\mathbb{Z}[\Gamma]$ the product $xp^{*}$ is
well defined and given for every $h\in\Gamma$ by

$(xp^{*})(h)=\sum_{i\in I}c_{i}x(hg_{i})\bmod{\mathbb{Z}}.$

Let us recall that for a locally compact abelian group $X$, its Pontryagin
dual is the space $\widehat{X}$ of all continuous homomorphisms from $X$ to
$\mathbb{R}/\mathbb{Z}$. Notice that if we endow $\widehat{X}$ with the
topology of uniform converge on compact sets and with pointwise addition, then
$\widehat{X}$ is also a locally compact abelian group whose elements are
called characters. We recall two well-known properties, their proofs can be
found for instance in [27]. First, that $X$ is a compact metrizable abelian
group if and only if $\widehat{X}$ is countable and discrete. Second, that
there exists an isomorphism (as topological groups, and through the canonical
evaluation map) between $X$ and its double dual $\widehat{\widehat{X}}$.

Now, there is a natural correspondence between algebraic actions
$\Gamma\curvearrowright X$ and actions $\Gamma\curvearrowright\widehat{X}$ by
automorphisms by letting $(g\cdot\chi)(x)=\chi(g^{-1}x)$ for every
$g\in\Gamma$, $x\in X$ and $\chi\in\widehat{X}$. Moreover, $\widehat{X}$
(endowed with its induced action) has a natural structure of countable left
$\mathbb{Z}[\Gamma]$-module where for $p=\sum_{i\in
I}c_{i}g_{i}\in\mathbb{Z}[\Gamma]$ and $\chi\in\widehat{X}$ the operation is
given by

$p\cdot\chi=\sum_{i\in I}c_{i}(g_{i}\cdot\chi).$

Conversely, given a countable left $\mathbb{Z}[\Gamma]$-module $M$ endowed
with the discrete topology, there is a natural action by (continuous)
automorphisms $\Gamma\curvearrowright M$ given by left multiplication by the
monomials $p_{g}=1\cdot g$ using the module product operation, and as before,
this induces an action by continuous automorphisms in $\widehat{M}$. In
particular, this means that there is a one-to-one correspondence (up to
isomorphism) between algebraic actions of $\Gamma$ and countable left
$\mathbb{Z}[\Gamma]$-modules.

An algebraic action $\Gamma\curvearrowright X$ is called finitely generated if
its associated $\mathbb{Z}[\Gamma]$-module is finitely generated. In this case
we can identify the module up to isomorphism with $\mathbb{Z}[\Gamma]^{n}/J$
for some integer $n\geq 1$ and $J$ a left-submodule of the free module
$\mathbb{Z}[\Gamma]^{n}$. Passing through the Pontryagin dual, this means that
in this case, without loss of generality, we can identify

$X=\\{(x_{1},\dots,x_{n})\in((\mathbb{R}/\mathbb{Z})^{\Gamma})^{n}:\sum_{i=1}^{n}x_{i}p_{i}^{*}=0\mbox{
for every }(p_{1},\dots,p_{n})\in J\\}.$

With the action $\Gamma\curvearrowright\widehat{\widehat{X}}$ being the left
shift as in Example 6.3. An algebraic action $\Gamma\curvearrowright X$ is
called finitely presented if the associated $\mathbb{Z}[\Gamma]$-module is
finitely presented. In this case the module is isomorphic to
$\mathbb{Z}[\Gamma]^{n}/\mathbb{Z}[\Gamma]^{k}P$ for some $n\in\mathbb{N}$ and
a $k\times n$ matrix $P\in\mathcal{M}_{k\times n}(\mathbb{Z}[\Gamma])$.
Therefore in this case we can identify

$X=\\{(x_{1},\dots,x_{n})\in((\mathbb{R}/\mathbb{Z})^{\Gamma})^{n}:\sum_{i=1}^{n}x_{i}P_{i,j}^{*}=0\mbox{
for every }j\in\\{1,\dots,k\\}\\}.$

We remark that the three examples given at the start of this section are
finitely presented algebraic actions.

In order to state our results in their full generality, we will introduce an
intermediate notion for algebraic actions which we call being “recursively
presented”. Let $S$ be a finite set of generators for a group $\Gamma$ and for
$w\in S^{*}$ denote by $\underline{w}$ its corresponding element of $\Gamma$.
Let $\mathbb{Z}[S^{*}]$ be the space of finitely supported maps $p\colon
S^{*}\to\mathbb{Z}$. To each map $p$ we can associate
$\underline{p}\in\mathbb{Z}[\Gamma]$ by letting
$\underline{p}=\sum_{w\in\operatorname{\mathrm{supp}}(p)}p(w)\underline{w}$.

######  Definition 6.5.

Let $\Gamma$ be a finitely generated group and $S$ a finite set of generators.
A finitely generated algebraic action $\Gamma\curvearrowright X$ is called
recursively presented if there exists $n\in\mathbb{N}$ and a computable total
map $g\colon\mathbb{N}\to\mathbb{Z}[S^{*}]^{n}$ such that up to isomorphism
the action is the shift map on

$X=\\{(x_{1},\dots,x_{n})\in((\mathbb{R}/\mathbb{Z})^{\Gamma})^{n}:\sum_{i=1}^{n}x_{i}\underline{g(k)_{i}}^{*}=0\mbox{
for every }k\in\mathbb{N}\\}.$

Notice that finitely presented algebraic actions are recursively presented, as
they can be represented by the maps
$g\colon\mathbb{N}\to\mathbb{Z}[S^{*}]^{n}$ which are eventually the zero of
$\mathbb{Z}[S^{*}]^{n}$ and thus computable.

######  Theorem 6.6.

Let $\Gamma$ be a finitely generated and recursively presented group. Every
recursively presented algebraic action $\Gamma\curvearrowright X$ is an EDS.

###### Proof.

Fix $S$ a symmetric finite set of generators of $\Gamma$. Consider
$n\in\mathbb{N}$ and a computable total map
$g\colon\mathbb{N}\to\mathbb{Z}[S^{*}]^{n}$ which define the recursively
presented algebraic action $\Gamma\curvearrowright X$. As the space
$(\mathbb{R}/\mathbb{Z})$ is recursively compact (with the structure given by
the rationals and the euclidean metric), it follows by Proposition 3.8 that
the product space $((\mathbb{R}/\mathbb{Z})^{S^{*}})^{n}$ is also recursively
compact. For $x\in(\mathbb{R}/\mathbb{Z})^{S^{*}}$ and $p\in\mathbb{Z}[S^{*}]$
we formally define $xp^{*}\in(\mathbb{R}/\mathbb{Z})^{S^{*}}$ by
$(xp^{*})(w)=\sum_{u\in\operatorname{\mathrm{supp}}(p)}x(wu)p(u)$.

Consider the space $Y$ of all
$(x_{1},\dots,x_{n})\in((\mathbb{R}/\mathbb{Z})^{S^{*}})^{n}$ which satisfy
the following two conditions:

  1. (1)

For every $u,v\in S^{*}$ such that $\underline{u}=\underline{v}$, and for
every $i\in\\{1,\dots,n\\}$ we have $x_{i}(u)=x_{i}(v)$.

  2. (2)

For every $k\in\mathbb{N}$ we have that $\sum_{i=1}^{n}x_{i}g(k)_{i}^{*}=0$.

We claim that $Y$ is an effectively closed subset of
$((\mathbb{R}/\mathbb{Z})^{S^{*}})^{n}$. Indeed, as $\Gamma$ is recursively
presented, the set $\texttt{EQ}(\Gamma)=\\{(u,v)\in S^{*}\times
S^{*}:\underline{u}=\underline{v}\\}$ is recursively enumerable. For words
$u,v$ consider the map
$f_{u,v}\colon((\mathbb{R}/\mathbb{Z})^{S^{*}})^{n}\to(\mathbb{R}/\mathbb{Z})^{n}$
given by

$f_{u,v}(x_{1},\dots,x_{n})=(x_{1}(u)-x_{1}(v),\dots,x_{n}(u)-x_{n}(v)).$

It is clear that each $f_{u,v}$ is computable (as projections are computable
in the product space), and that the collection
$\\{f_{u,v}\\}_{(u,v)\in\texttt{EQ}(\Gamma)}$ is uniformly computable. As
$\\{0\\}$ is an effectively closed subset of $(\mathbb{R}/\mathbb{Z})^{n}$, it
follows that
$Y_{(1)}=\bigcap_{(u,v)\in\texttt{EQ}(\Gamma)}f_{u,v}^{-1}(\\{0\\})$ is an
effectively closed set. Remark that this is precisely the set of elements of
$((\mathbb{R}/\mathbb{Z})^{S^{*}})^{n}$ which satisfy condition (1).

Given $k\in\mathbb{N}$, and $v\in S^{*}$, consider the map
$h_{k,v}\colon((\mathbb{R}/\mathbb{Z})^{S^{*}})^{n}\to\mathbb{R}/\mathbb{Z}$
given by

$h_{k,v}(x_{1},\dots,x_{n})=\left(\sum_{i=1}^{n}x_{i}g(k)_{i}^{*}\right)(v)=\sum_{i=1}^{n}\sum_{u\in\operatorname{\mathrm{supp}}(g(k)_{i})}x_{i}(vu)g(k)_{i}(u).$

It is clear from the fact that $g$ is a total computable function that the
collection $(h_{k,v})_{k\in\mathbb{N},v\in S^{*}}$ is uniformly computable. It
follows that $Y_{(2)}=\bigcap_{k\in\mathbb{N}}\bigcap_{v\in
S^{*}}h_{k,v}^{-1}(\\{0\\})$ is an effectively closed set as well. Remark that
this is precisely the set of elements of
$((\mathbb{R}/\mathbb{Z})^{S^{*}})^{n}$ which satisfy condition (2).

As $Y=Y_{(1)}\cap Y_{(2)}$, it follows that $Y$ is an effectively closed
subset of $((\mathbb{R}/\mathbb{Z})^{S^{*}})^{n}$.

Let us define for each $s\in S$ the computable map $t_{s}\colon Y\to Y$ given
by $(t_{s}(x_{1},\dots,x_{n}))(u)=(x_{1},\dots,x_{n})(s^{-1}u)$. It is clear
by condition (1) that these maps induce an action of $\Gamma$, thus
$\Gamma\curvearrowright Y$ is a computable action on an effectively closed
set. Finally, it follows from condition (2) that the map $\phi\colon X\to Y$
given by $(\phi(x_{1}\dots,x_{n}))(w)=(x_{1},\dots,x_{n})(\underline{w})$ is a
topological conjugacy and thus $\Gamma\curvearrowright X$ is an EDS.∎

Putting together Theorem 6.6 and B, we obtain the following corollary which in
turn, implies C (as finitely presented algebraic actions are recursively
presented).

######  Corollary 6.7 (Theorem C).

Let $\Gamma$ be a recursively presented self-simulable group. Then every
recursively presented algebraic action of $\Gamma$ is the topological factor
of some $\Gamma$-subshift of finite type.

##  7\. Other computability notions for shift spaces

The goal of this section is to compare the computability notions for subshifts
we have introduced in this article with other notions of computability for
shift spaces that can be found in the literature. We start by showing that a
subshift is an EDS if and only if it is effective as per Definition 3.21.

######  Proposition 7.1.

Let $\Gamma$ be a finitely generated group. A subshift $X\subset A^{\Gamma}$
is an EDS if and only if it is effective.

###### Proof.

Let us recall that for a finitely generated group $\Gamma$ a subshift
$X\subset A^{\Gamma}$ is effective if its pullback into the full shift
$A^{F(S)}$ is an effectively closed set. We already argued in Example 3.26
that every effective subshift is an EDS. Let us fix a finite set of generators
$S$ of $\Gamma$ and denote by $\widehat{X}\subset A^{F(S)}$ the subshift
induced by $X$ on the free group $F(S)$. Suppose that $\Gamma\curvearrowright
X$ is topologically conjugate to a computable action on an effectively closed
subset $Y$ of a recursively compact metric space. By Proposition 4.9, we may
assume without loss of generality that $Y$ is an effectively closed subset of
$\\{0,1\\}^{\mathbb{N}}$ with the canonical computable structure. As
$\Gamma\curvearrowright X$ is topologically conjugate to
$\Gamma\curvearrowright\widehat{X}$, there is a topological conjugacy
$\phi\colon Y\to\widehat{X}$. For every $a\in A$, let
$[a]=\\{\widehat{x}\in\widehat{X}:\widehat{x}(1_{F(S)})=a\\}$. As $\phi$ is a
homeomorphism, we have that $C_{a}=\phi^{-1}([a])$ is a finite union of
cylinder sets in $Y$ and thus an effectively closed subset of $Y$.

We claim that there exists an algorithm that given $W\Subset F(S)$ and a
pattern $p\colon W\to A$, accepts if and only if
$[p]\cap\widehat{X}=\varnothing$. Indeed, given such a $p$, we may compute a
description of $C_{p}=\bigcap_{w\in W}w\cdot C_{p(w)}$. As the action
$\Gamma\curvearrowright Y$ is computable, it follows that each $w\cdot
C_{p(w)}$ is an effectively closed set and thus, as the intersection of
finitely many effectively closed sets is effectively closed, one may
algorithmically detect whether $C_{p}=\varnothing$, which occurs precisely
when $[p]\cap\widehat{X}=\varnothing$. It follows that the collection
$\mathcal{F}_{\mathrm{max}}=\\{p\mbox{ is a pattern
}:[p]\cap\widehat{X}=\varnothing\\}$ is recursively enumerable. As
$\mathcal{F}_{\mathrm{max}}$ is the maximal set of patterns which defines
$\widehat{X}$, it follows that $\widehat{X}$ is an effectively closed set. ∎

In the literature, there is also an intrinsic notion of computability for
subshifts based on codings of forbidden patterns. This notion was originally
defined in [1].

Let $S$ be a finite set of generators of a group $\Gamma$ and $A$ be an
alphabet. A partial function $c\colon S^{*}\to A$ with finite support is
called a pattern coding and its domain is denoted $\operatorname{supp}(c)$.
Recall that for $w\in S^{*}$ we denote by $\underline{w}$ the corresponding
element of $\Gamma$. The cylinder set induced by a pattern coding $c$ is given
by

$[c]=\\{x\in A^{\Gamma}:x(\underline{w})=c(w)\mbox{ for every
}w\in\operatorname{supp}(c)\\}.$

A pattern coding is inconsistent if there are $u,v\in\operatorname{supp}(c)$
such that $\underline{u}=\underline{v}$ but $c(u)\neq c(v)$. Notice that for
inconsistent pattern codings we have $[c]=\varnothing$. The set of all pattern
codings is a named set, and thus we can speak about computability of sets of
pattern codings. Given a set $\mathcal{C}$ of pattern codings, we can define a
subshift $X_{\mathcal{C}}\subset A^{\Gamma}$ by

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

######  Definition 7.2.

We say that a subshift $X\subset A^{\Gamma}$ is effectively closed by patterns
(ECP) if there exists a recursively enumerable set of pattern codings
$\mathcal{C}$ such that $X=X_{\mathcal{C}}$.

######  Example 7.3.

For any finitely generated group $\Gamma$, every subshift of finite type
$X\subset A^{\Gamma}$ is ECP, as it is given by a finite set of forbidden
pattern codings.

In what follows we will show that for general finitely generated groups, being
an ECP subshift is strictly weaker than being an EDS (or equivalently, an
effective subshift), but that all notions coincide for recursively presented
groups. For a subshift $X\subset A^{\Gamma}$ denote by
$\mathcal{C}_{\mbox{max}}(X)$ the set of all pattern codings $c$ such that
$[c]\cap X=\varnothing$.

######  Proposition 7.4.

Let $\Gamma$ be a finitely generated group. A subshift $X\subset A^{\Gamma}$
is effective if and only if the set $\mathcal{C}_{\mbox{max}}(X)$ is
recursively enumerable.

###### Proof.

Let $\mathcal{C}_{\mbox{max}}^{\prime}$ be the set of all pattern codings $c$
such that $[c]\cap X=\varnothing$ and $c$ is consistent on the free group
$F(S)$. As the set of pattern codings which are consistent for the free group
is decidable, it follows that $\mathcal{C}_{\mbox{max}}(X)$ is recursively
enumerable if and only if $\mathcal{C}_{\mbox{max}}^{\prime}$ is recursively
enumerable.

Let us recall that $X$ is an effective subshift when $\widehat{X}\subset
A^{F(S)}$ is effectively closed. We claim that
$\mathcal{C}_{\mbox{max}}^{\prime}$ is recursively enumerable if and only if
$\widehat{X}\subset A^{F(S)}$ is effectively closed. This is just by
definition of effetively closed set, as $\mathcal{C}_{\mbox{max}}^{\prime}$ is
exactly the set of pattern codings of patterns in the free group whose
associated cylinder in $A^{F(S)}$ do not intersect $\widehat{X}$. ∎

In particular, as the set $\mathcal{C}_{\mbox{max}}(X)$ defines the subshift
$X$, we obtain that every effective subshift is ECP.

######  Corollary 7.5.

Let $\Gamma$ be a finitely generated group and $X\subset A^{\Gamma}$ be an
effective subshift. Then $X$ is effectively closed by patterns.

We shall see that the converse only holds in recursively presented groups. For
this we shall need the following lemma.

######  Lemma 7.6.

[1, Lemma 2.3] Let $\Gamma$ be a finitely generated and recursively presented
group. For every ECP subshift $X\subset A^{\Gamma}$, the set
$\mathcal{C}_{\mbox{max}}(X)$ is recursively enumerable.

######  Corollary 7.7.

On recursively presented groups, every ECP subshift is effective. Thus on
recursively presented groups the three computability notions are equivalent.

We remark that for an effective cover $\mathcal{P}$ of a recursively compact
metric space $X$, the subshift $Y(\Gamma\curvearrowright X,\mathcal{P})$ from
Proposition 4.4 is ECP but not necessarily effective. This is fundamentally
the reason why we need to ask that $\Gamma$ is recursively presented in A.

A useful consequence of Corollary 7.7 is that on recursively presented groups,
SFTs are effective subshifts. This follows from the fact that SFTs are ECP.

######  Corollary 7.8.

Let $\Gamma$ be a recursively presented group. Then every $\Gamma$-SFT is
effective.

Let us show that for non recursively presented groups there are always ECP
subshifts which are not effective. Let $A$ be a finite alphabet with $|A|\geq
2$ and $\Gamma$ a finitely generated group. Notice that the full
$\Gamma$-shift $A^{\Gamma}$ is ECP as it is defined through the empty set of
pattern codings.

######  Proposition 7.9.

The full $\Gamma$-shift is effective if and only if $\Gamma$ is recursively
presented.

###### Proof.

Let $S$ be a finite generating set of $\Gamma$ and consider the pullback
$\widehat{A^{\Gamma}}\subset A^{F(S)}$. Fix two distinct symbols $a,b\in A$.
Given $w\in S^{*}$, there is an algorithm that constructs its corresponding
element $\underline{w}\in F(S)$ and the pattern $p_{w}\in
A^{\\{1_{F(S)},\underline{w}\\}}$ with $p_{w}(1_{F(S)})=a$ and
$p_{w}(\underline{w})=b$. Clearly
$[p_{w}]\cap\widehat{A^{\Gamma}}=\varnothing$ if and only if $w$ represents
the identity in $\Gamma$ and furthermore
$\widehat{A^{\Gamma}}=A^{F(S)}\setminus\bigcup_{g\in\Gamma,w\in\operatorname{\texttt{WP}(\Gamma)}}g[p_{w}]$.

If $\Gamma$ is recursively presented the result is immediate (either by the
argument in Example 3.23 or by Corollary 7.7). Conversely, if
$\widehat{A^{\Gamma}}$ is an effectively closed set then by Proposition 7.4
the maximal set of forbidden pattern codings is recursively enumerable. In
particular, given $w\in S^{*}$ we can recursively enumerate the $w$ for which
$[p_{w}]\cap\widehat{A^{\Gamma}}=\varnothing$ which are precisely the elements
of $\texttt{WP}(\Gamma)$. Therefore $\Gamma$ is recursively presented. ∎

##  8\. Topological factors of effective dynamical systems

We begin by showing that the class of EDS is not closed by topological
factors. In particular, it shows that subshifts of finite type on certain
groups may have factors that are not EDS. However, we shall show that under
certain conditions such as having topological zero dimension, we can still
provide computational restrictions that said factors must satisfy.

Given an action $\Gamma\curvearrowright X$, we define its set of periods as

$\mathtt{Per}(\Gamma\curvearrowright X)=\\{g\in\Gamma:\mbox{ there is }x\in
X\mbox{ such that }gx=x\\}$

The following lemma holds in general for any finitely generated group with
decidable word problem. However, we shall only need it for the special case of
$\mathbb{Z}$-actions.

######  Lemma 8.1.

Let $\mathbb{Z}\curvearrowright X$ be an EDS. Then
$\mathtt{Per}(\mathbb{Z}\curvearrowright X)$ is a co-recursively enumerable
set.

###### Proof.

We will prove that the complement of $\mathtt{Per}(\mathbb{Z}\curvearrowright
X)$ is a recursively enumerable subset of $\mathbb{Z}$. Without loss of
generality, replace $\mathbb{Z}\curvearrowright X$ by a computable
representative. Then the product space $X^{2}$ is recursively compact and thus
the diagonal $\Delta^{2}=\\{(x,x)\in X^{2}:x\in X\\}$ is an effectively closed
subset and thus also recursively compact. As $\mathbb{Z}\curvearrowright X$ is
computable, it follows that the collection of diagonal maps $f_{n}\colon
X^{2}\to X^{2}$ given by $(x,y)\mapsto(T^{n}(x),y)$ for $n\in\mathbb{Z}$ is
uniformly computable, and thus the collection of sets
$Y_{n}=f_{n}^{-1}(\Delta^{2})$ is uniformly recursively compact. It follows
that we can recursively enumerate the integers $n$ such that
$Y_{n}\cap\Delta^{2}=\varnothing$. In other words, the set

$\mathbb{Z}\setminus\mathtt{Per}(\mathbb{Z}\curvearrowright
X)=\\{n\in\mathbb{Z}:Y_{n}\cap\Delta^{2}=\varnothing\\},$

is recursively enumerable. ∎

The set of periods is an invariant of topological conjugacy, therefore any
action $\mathbb{Z}\curvearrowright X$ for which the set of periods is not co-
recursively enumerable cannot be topologically conjugate to an EDS.

######  Proposition 8.2.

The class of EDS is not closed under topological factor maps.

###### Proof.

Let us consider

$X=\\{0\\}\cup\left\\{z\in\mathbb{C}:|z|=\frac{1}{n}\mbox{ for some integer
}n\geq 1\right\\}.$

And let $T\colon X\to X$ be given by $T(z)=z\exp\left(2\pi i|z|\right)$. It is
clear that $X$ is a recursively compact subset of $\mathbb{C}$ with the
standard topology and that $T$ is a computable homeomorphism which thus
induces a computable action $\mathbb{Z}\curvearrowright X$. The map $T$
consists of rational rotations on each circle where the period is given by the
inverse of the radius, and thus it is easy to see that
$\mathtt{Per}(\mathbb{Z}\curvearrowright X)=\mathbb{Z}$.

$T$$X$$S$$Y$$f$ Figure 1. A representation of the actions
$\mathbb{Z}\curvearrowright X$ and $\mathbb{Z}\curvearrowright Y$.

Now let $A\subset\mathbb{N}\setminus\\{0\\}$ be some infinite set and let
$Y\subset\mathbb{C}$ be given by

$Y=\\{0\\}\cup\left\\{z\in\mathbb{C}:|z|=\frac{1}{n}\mbox{ for some }n\in
A\right\\}.$

Similarly, the map $S\colon Y\to Y$ given by $S(z)=z\exp\left(2\pi
i|z|\right)$ is a homeomorphism which induces an action
$\mathbb{Z}\curvearrowright Y$.

Let $f\colon X\to Y$ be the map given by

$f(z)=\begin{cases}z&\mbox{ if }|z|\in A\mbox{ for some }n\in A,\\\ 0&\mbox{
if }|z|\notin A.\end{cases}$

It is clear from the definition that $f$ is a continuous, surjective map such
that $f\circ T=S\circ T$ and thus a topological factor map from
$\mathbb{Z}\curvearrowright X$ to $\mathbb{Z}\curvearrowright Y$. However,
notice that $\mathtt{Per}(\mathbb{Z}\curvearrowright Y)=\mathbb{Z}A$, that is,
the set of integers which are integer multiples of some element of $A$.

Notice that as the set of prime numbers is decidable, then a subset $A$ of
prime numbers is co-recursively enumerable if and only if $\mathbb{Z}A$ is co-
recursively enumerable. In particular, for such a set $A$ we would have that
$\mathtt{Per}(\mathbb{Z}\curvearrowright Y)$ is not co-recursively enumerable
and thus $\mathbb{Z}\curvearrowright Y$ cannot be an EDS. ∎

######  Proposition 8.3.

The class of EDS is not closed under topological factor maps, even if we
restrict to zero-dimensional spaces.

###### Proof.

For each $n\in\mathbb{N}$, let $X_{n}=\\{0,\dots,n\\}$, and let $t_{n}=(1\ 2\
\dots\ n)$ be the permutation on $X_{n}$ which fixes $0$ and cyclically
permutes $1\mapsto 2\mapsto 3\mapsto\dots\mapsto n\mapsto 1$. Now define
$Y_{n}$ as the product $X_{0}\times\dots\times X_{n}$, and $s_{n}$ as the map
on $Y_{n}$ which applies $t_{0},\dots,t_{n}$ component-wise. We define
$\pi_{n+1}$ as the map $Y_{n+1}\to Y_{n}$ which removes the last component of
the tuple, this is a factor map from $Y_{n+1}$ to $Y_{n}$ with their
respective actions. We now define $Y$ as the inverse limit of sequence

$\dots\xrightarrow{\pi_{n+2}}\
Y_{n+1}\xrightarrow{\pi_{n+1}}Y_{n}\xrightarrow{\pi_{n}\ \
}\dots\xrightarrow{\pi_{1}\ \ }Y_{0}.$

It is straightforward to verify that the set $Y$ endowed with the component-
wise action is a zero dimensional EDS. Let $A\subset\mathbb{N}$. We now define
a topological factor of $Y$ called $Y_{A}$.

For each $n$ define $g_{n}\colon X_{n}\to X_{n}$, as follows. For $n\not\in
A$, $g_{n}$ sends everything to $0$. For $n\in A$, $g_{n}$ is the identity
function on $X_{n}$. Now define $f_{n}\colon Y_{n}\to Y_{n}$ as the function
which on component $n$ applies $g_{n}$. Then $f_{n}$ is an endomorphism of
$Y_{n}$ with the action induced by $s_{n}$. Finally, define $F$ as the
endomorphism of $Y$ which in component $n$ applies $f_{n}$ and let $Y_{A}$ be
the image of $F$, which is a compact subset of $\prod_{n\in\mathbb{N}}Y_{n}$
by the continuity of $F$. We endow $Y_{A}$ with the componentwise action
inherited as a subsystem of $Y$.

As in the previous construction, it suffices to take $A$ as a set of primes
which is not co-recursively enumerable. In this case, $Y_{A}$ is a zero-
dimensional topological factor of the zero dimensional EDS $Y$, but it cannot
be an EDS because its set of periods is exactly $\mathbb{Z}A$ which is not co-
recursively enumerable. ∎

Even if the class of EDS is not closed under topological factor maps, it is
reasonable to assume that a factor of an EDS should still satisfy some sort of
computability constraint. With the aim of understanding this class in the case
of zero-dimensional spaces, we introduce a notion of weak EDS which will turn
out to be stable under topological factor maps.

######  Definition 8.4.

An action $\Gamma\curvearrowright X$ with $X\subset A^{\mathbb{N}}$ is a weak
effective dynamical system (WEDS) if for every clopen partition
$\mathcal{P}=(P_{i})_{i=1}^{n}$ of $X$ the subshift

$Y(\Gamma\curvearrowright
X,\mathcal{P})=\\{y\in\\{1,\dots,n\\}^{\Gamma}:\mbox{ there is }x\in X\mbox{
such that for every }g\in\Gamma,\ g^{-1}x\in P_{y(g)}\\}.$

is effective.

Notice that for an action $\Gamma\curvearrowright X$ with $X\subset
A^{\mathbb{N}}$ to be a WEDS, it suffices to check the condition on the clopen
partitions $\mathcal{P}_{n}=\\{[w]:w\in A^{n}\mbox{ and }[w]\cap
X\neq\varnothing\\}$ as this family of clopen partitions refines any other
clopen partition. As $\Gamma\curvearrowright X$ can be obtained as the inverse
limit of the shift action on the $Y(\Gamma\curvearrowright
X,\mathcal{P}_{n})$, we may also define a WEDS as an action that can be
obtained as the inverse limit of a sequence of effective subshifts. Notice
that we do not require the sequence to be uniform in this definition.

######  Remark 8.5.

Notice that any expansive WEDS $\Gamma\curvearrowright X$ is automatically an
EDS, as in this case $\Gamma\curvearrowright X$ is topologically conjugate to
$Y(\Gamma\curvearrowright X,\mathcal{P})$ for any partition with small enough
diameter and thus we have that $\Gamma\curvearrowright X$ is an EDS.

######  Proposition 8.6.