Decidability of the isomorphism and the factorization between minimal substitution subshifts

Decidability of the isomorphism and the factorization between minimal substitution subshifts, Discrete Analysis 2022:7, 65 pp.

Symbolic dynamics is the study of topological dynamical systems $(X,S)$ where $X$ is a shift-invariant space of singly or doubly infinite sequences of words in a finite alphabet, with the product topology, and $S$ is the shift map. Such systems are called subshifts. Subshifts are important partly because many dynamical systems can be represented in this form (very roughly, given a map $T$ defined on some manifold $M$, one divides $M$ up into a finite number of small regions and associates with each point of the manifold the sequence of regions it visits under iterates of $T$), and partly because they are interesting in their own right and lead to many attractive questions.

A very basic question is to classify subshifts. However, that turns out to be hopeless, as the problem of determining whether two subshifts are isomorphic has been shown to be undecidable.

In the light of this, attention has turned to investigating more specific classes of subshifts. Arguably the main open problem of this type is to determine whether the problem is decidable for a class of subshifts that are created as follows. Given an alphabet $\Sigma$ and a 01-matrix $A$ indexed by $\Sigma\times\Sigma$, one can obtain a subshift by taking all sequences $(x_n)$ of elements of $\Sigma$ such that $A_{x_{n-1}x_n}=1$ for every $n$. Such subshifts are called subshifts of finite type. Since subshifts of finite type are defined by a finite amount of data, it makes sense to ask whether isomorphism of such subshifts (together with an irreducibility condition) is decidable.

This paper looks at another important and intensively studied class of subshifts, known as substitution subshifts, which are obtained as follows. One begins with an alphabet $A$, a symbol $a\in A$, and a set of substitution rules that provide, for each element of $A$, a finite sequence of elements that should replace it. If we start with just a singleton sequence $a$, and if the sequence that replaces $a$ begins with $a$, then these rules generate an infinite sequence. For example, the well-known Morse sequence 01101001100101101001… is generated by the initial element 0 and the rules that 0 is replaced by 01 and 1 is replaced by 10.

To turn this into a subshift, one takes $X$ to be the space of all sequences that belong to the closure of the set of shifts of the sequence $x$ we have generated. This consists of all sequences $y$ such that every restriction of $y$ to an interval of $y$ agrees with some restriction of $x$ to an interval (necessarily of the same length).

Again, only a finite amount of data is needed to define a substitution subshift, so again it makes sense to ask if there is an algorithm to determine whether two substitution subshifts are isomorphic. This problem is not quite as widely stated as the problem for irreducibile subshifts of finite type, but substitution subshifts are a fundamental source of examples of abstract dynamical systems, making this a very important question.

The paper solves the question for a wide class of substitution subshifts, known as minimal substitution subshifts. In fact, it does considerably more than this: given two such subshifts, it shows that one can compute all the morphisms between them. The paper also gives bounds on the sizes of these morphisms, and hence on the complexity of the algorithms needed to compute them. (These bounds are quite large but not ridiculously so – they are given by composing a bounded number of exponentials.)

Several questions are left open, but the main results of this paper are a big step forward in the area, building on a great deal of earlier work by the authors and others. They are likely to be of interest to researchers in dynamics, cellular automata, computability, and complexity theory, as well as solving questions that are natural and interesting in their own right.