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 HigmanClaphamValiev 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 \(\Sigma^0_3\) be 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 onedimensional 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:
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 fixpointbased 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 nontrivial matter. I always tend to confuse these things. ↩