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 anywhere1”. 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 subshifts2.
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 order3. 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.