While at CIRM during this thematic month, I discussed with Emmanuel Rauzy about computability on (finitely or recursively presented) groups. In particular, he brought to my attention that the Higman-Clapham-Valiev embedding theorem (namely: any recursively presented group \(H\) embeds into a finitely presented group \(G\) that has solvable word problem if and only if \(H\) does) implies that the following decision problem is \(\Sigma^0_3\)-complete:

**Input:**A finite presentation \(\langle S \mid R \rangle\) of a group \(G\).**Output:**Does \(G\) have solvable word problem?

Of course, since I am interested in the analogies between group theory and subshifts, I wondered if the equivalent problem in subshifts would also be \(\Sigma^0_3\)-complete. Of course, it is, and here’s another short note proving so.

First, I have a few people to thank: first of all, Emmanuel Rauzy for giving me an interesting question; and second, Léo Paviet Salomon for making this proof with me.

## Preliminaries

In this note, I prove a computational characterization of the computability of the language of multidimensional subshifts: it is \(\Sigma^0_3\)-complete to decide whether a given subshift (either SFT, sofic or effective) has a computable language.

I didn’t see this anywhere, and in the words of Emmanuel Jeandel “if we didn’t do it with Pascal (Vanier) during his PhD, then it’s probably not written anywhere^{1}”. I don’t claim that the problem is very difficult, quite the opposite in fact; but more than the proof, the result by itself looks interesting to me. I have been investigating (recursively presented) groups as a model of computation as of late, and it was interesting to me to transpose computational results from group theory to subshifts^{2}.

Now that it’s proved, we can consider this result as “folklore” and hopefully at some point somebody will write this kind of stuff somewhere (in a book, for example). I know for a fact that some very famous person (who now happens to do math, I guess) is writing a survey about decision problems on subshifts, and will probably post it on the arXiv soon when she gets the time. I’ll post a link to it when it’s done, but in the meantime, here is a short note containing the proof.

### Definitions

For (crash course) definitions about subshifts and the arithmetical hierarchy, I refer to my previous note which very briefly covered the required notions.

In this note, I am interested in the computability of the language of a subshift. Given a subshift \(X \subseteq A^{\Z^d}\), we denote by \(\mathcal{L}_{D}(X) = \{w \in A^D \mid \exists x \in X, w \sqsubseteq x\}\) the set of patterns of finite domain \(D \subseteq_f \Z^d\) that appear in \(X\). The *language* of \(X\) is then defined as \(\mathcal{L}(X) = \bigcup_{D \subseteq_f \Z^d} \mathcal{L}_{D}(X)\).

Finally, we say that \(X\) has a *computable language* if \(\mathcal{L}(X)\) is a computable set, i.e. if there exists a total Turing machine that recognizes it.

## The result

Let us define the following decision problem **Computability**:

The decision problem **Computability** is defined as follows:

**Input**: A family of forbidden patterns \(\mathcal{F}\);**Output:**Is \(\mathcal{L}(X_{\mathcal{F}})\) computable?

As mentioned in the introduction of this post, here is what we proved:

In dimension \(d \geq 2\), **Computability** is \(\Sigma^0_3\)-complete on SFTs and effective subshifts.

The fact that **Computability** belongs in \(\Sigma^0_3\) for effective subshifts is straightforward: the exercise consists in writing the quantifiers in the right order^{3}. In the rest of this note, I focus on the converse: proving that **Computability** is a \(\Sigma^0_3\)-hard problem on SFTs.

### Hardness in dimension \(d=1\)

Let us prove an intermediary result:

The following decision problem is \(\Sigma^0_3\)-complete:

**Input**: a computably enumerable family of one-dimensional forbidden patterns \(\mathcal{F}\);**Output**: Is \(\mathcal{L}(X)\) computable?

We focus on \(\Sigma^0_3\)-hardness, and reduce to the problem ** coFin**: given a Turing machine \(\mathcal{M}\), does it halt on all but finitely many inputs?

Define \(X\) a \(\Z\) effective subshift on the alphabet \(\{\#,0,1\}\) of configurations that, if they contain at least two symbols \(\#\) separated by distance, say, \(p\), are then \(p\)-periodic; and, denoting by \((M_n)_{n \in \N}\) an enumeration of Turing machines, we add the following two families of forbidden patterns:

\[ \begin{align*} \mathcal{F}_1 & = \{ \# b_1 b_2 \dots b_n \# \mid b_i \in \{0,1\},\, b_i = 1 \text{ and } M_i \text{ halts on the empty word \(\varepsilon\)}\, \} \\ \mathcal{F}_2 & = \{ \# b_1 b_2 \dots b_n \# \mid b_i \in \{0,1\},\, \mathcal{M}(n) \text{ halts}\,\} \end{align*} \]

If \(\mathcal{M}\) halts on all but finitely many inputs, there are finitely many words of the form \(\# u \#\) in \(\mathcal{L}(X)\) because of \(\mathcal{F}_2\), so that \(\mathcal{L}(X)\) is computable. On the other hand, if there are infinitely many inputs on which \(\mathcal{M}\) does not halt, then there are arbitrary long words of the form \(\# u \#\) in \(\mathcal{L}(X)\) for \(u \in \{0,1\}^*\). As these words encode arbitrary long sequences of a \(\Sigma^0_1\) oracle (the halting problem), \(\mathcal{L}(X)\) is not computable.

### Hardness in dimension \(d \geq 2\)

Let me recall a simulation theorem from [Durand, Romashchenko & Shen (2012); Theorem 10] and [Aubrun & Sablik (2013); Theorem 3.1]:

Given an effective \(\Z\) subshift \(X_1\), there exists a \(\Z^2\) SFT \(X_2\) such that:

- Denoting \(X_1^\uparrow = \{ x \in A^{\Z^2} \mid \exists y \in X_1, \forall i,j \in \Z, x_{i,j} = y_j \}\) the vertical extension of \(X_1\), then \(X_1^\uparrow\) is a factor of \(X_2\);
- If \(X_1\) has computable language, then \(X_2\) also has computable language.

Basically, this theorem is a computable version of the fixpoint-based construction. We can then complete the proof of our theorem:

By the theorem above, we obtain that **Computability** of SFTs in dimension \(d \geq 2\) reduces to the computability problem for \(\Z\) effective subshifts, which is \(\Sigma^0_3\)-hard. This concludes the proof.

- ↩
Of course, were he to be wrong, please feel free to tell me!

- ↩
For some reason, it is way easier for me to get good ideas from groups and tranpose them to subshifts, than the other way around. Groups are mean.

- ↩
Which, in itself, might be a non-trivial matter. I always tend to confuse these things.