<p>Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e.</p>

<blockquote>
  <p>Theorem. There is no algorithm that given two context-free languages, says "same" if they define the same subshift, and says "non-conjugate" if they are not conjugate.</p>
</blockquote>

<p>Note that no requirement, even on halting, is made when they are distinct and conjugate.</p>

<p>Proof. Note that CFL are closed under unions and contain all regular languages, so we can forbid finitely many regular and CFL languages. We will forbid a bunch of things to force our configurations to simulate Turing machines.</p>

<p>Let <span class="math-container">$M$</span> be a Turing machine with state set <span class="math-container">$Q$</span> and alphabet <span class="math-container">$A$</span>, suppose <span class="math-container">$Q \cap A = \emptyset$</span> and <span class="math-container">$\#, @ \notin A \cup Q$</span>, and <span class="math-container">$0 \in A$</span>. Let <span class="math-container">$q_0 \in Q$</span> be the initial state of <span class="math-container">$Q$</span> and <span class="math-container">$q_f$</span> the unique halting state.</p>

<p>We will construct two subshifts <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> over the alphabet <span class="math-container">$Q \cup A \cup \{\#, @\}$</span> such that if <span class="math-container">$M$</span> reaches the halting state <span class="math-container">$q_f$</span> from the initial configuration <span class="math-container">$q_0 0^\omega$</span> then <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> are not conjugate, and if <span class="math-container">$M$</span> does not, then <span class="math-container">$X = Y$</span> as sets.</p>

<p>I won't list the precise forbidden patterns since it's a lot of programming, but I'll explain what they accomplish. I'll say what needs to be true about subwords of a certain form, which you can turn into forbidden patterns by forbidding the complement of these conditions. First, with a regular set of forbidden patterns we force that <span class="math-container">$\#$</span> and <span class="math-container">$@$</span> alternate, and the word between any consecutive appearance of <span class="math-container">$\#$</span> and <span class="math-container">$@$</span> (in either order) is an element of <span class="math-container">$A^* Q A^*$</span> (so there's a Turing machine configuration between <span class="math-container">$\#$</span> and <span class="math-container">$@$</span>).</p>

<p>Next, with a context-free set of forbidden patterns we force that in every pattern <span class="math-container">$u@v$</span> where <span class="math-container">$u, v \in (Q \cup A)^*$</span>, we have <span class="math-container">$u = v^R$</span> where <span class="math-container">$v^R$</span> denotes reversal. We also force that in every word <span class="math-container">$\#u@va$</span> with <span class="math-container">$|u| = |v|$</span>, <span class="math-container">$u, v \in (Q \cup A)^*$</span> and <span class="math-container">$a \in Q \cup A \cup \{\#, @\}$</span>, we have <span class="math-container">$a = \#$</span>, and the three symmetric conditions that together force that <span class="math-container">$\#$</span> and <span class="math-container">$@$</span> appear in a single arithmetic progression.</p>

<p>Next, the main trick. It's the one used in the standard proof of undecidability of whether two given context-free languages intersect: we require that in every word <span class="math-container">$@ v \# u @$</span>, if <span class="math-container">$v$</span> does not contain <span class="math-container">$q_f$</span>, then <span class="math-container">$u$</span> is the configuration that follows <span class="math-container">$v^R$</span> in the rule of <span class="math-container">$M$</span>. If <span class="math-container">$v$</span> does contain <span class="math-container">$q_f$</span>, then we require that <span class="math-container">$u^R$</span> is the unique word in <span class="math-container">$q_0 0^*$</span> of the correct length.</p>

<p>Finally, require that in every word <span class="math-container">$@ v \# w \# v^R @$</span> where <span class="math-container">$v \in (Q \cup A)^*$</span>, the state <span class="math-container">$q_f$</span> appears somewhere in <span class="math-container">$w$</span>. These patterns define the subshift <span class="math-container">$X$</span>.</p>

<p>Let us analyze what kind of configurations appear in <span class="math-container">$X$</span>. First, no matter whether <span class="math-container">$M$</span> halts on input <span class="math-container">$q_0 0^\omega$</span>, in <span class="math-container">$X$</span> you have all configurations of the form <span class="math-container">$x @ y$</span> and <span class="math-container">$x \# y$</span> where <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are over the alphabet <span class="math-container">$Q \cup A$</span>, and all the limits of such configurations under the shift action, namely the full shift <span class="math-container">$(Q \cup A)^{\mathbb{Z}}$</span>. Let <span class="math-container">$Y \subset X$</span> be this subset. It's a sofic subshift.</p>

<p>Suppose then that both <span class="math-container">$\#$</span> and <span class="math-container">$@$</span> appear in a configuration of <span class="math-container">$X$</span> (recall that they must alternate, so this happens unless the configuration is in <span class="math-container">$Y$</span>), then the rules force that <span class="math-container">$@$</span> and <span class="math-container">$\#$</span> appear periodically in an arithmetic progression, and the configuration is of the form
<span class="math-container">$$ \ldots v_{-1} \# u_0 @ v_0 \# u_1 @ v_1 \# u_2 @ v_2 \# u_3 @ \ldots $$</span>
with all the <span class="math-container">$|u_i|$</span> and <span class="math-container">$|v_i|$</span> of the same length, <span class="math-container">$u_i = v_i^R$</span> and the <span class="math-container">$M$</span>-successor of <span class="math-container">$u_i$</span> is <span class="math-container">$u_{i+1}$</span>. Since the lengths are the same, the computation must enter a loop starting from any <span class="math-container">$u_i$</span>, i.e. <span class="math-container">$u_m = u_k$</span> for some <span class="math-container">$m &lt; k$</span>. The last rule then forces an appearance of <span class="math-container">$q_f$</span> somewhere between <span class="math-container">$u_m$</span> and <span class="math-container">$u_k$</span>. But this means there is an occurrence of <span class="math-container">$q_0 0^n$</span> between them as well. Another application of this argument shows that the computation from <span class="math-container">$q_0 0^n$</span> reaches the halting state <span class="math-container">$q_f$</span>.</p>

<p>We see that any configuration not in <span class="math-container">$Y$</span> is periodic, and must periodically repeat the accepting computation of <span class="math-container">$M$</span> on some <span class="math-container">$q_0 0^n$</span>, where <span class="math-container">$n$</span> is any integer large enough that he computation has time to halt. (And if <span class="math-container">$M$</span> does halt on <span class="math-container">$q_0 0^n$</span>, then periodically repeating the computation gives a valid configuration of <span class="math-container">$X$</span>.)</p>

<p>In conclusion, if <span class="math-container">$M$</span> never halts on <span class="math-container">$q_0 0^\omega$</span>, <span class="math-container">$X = Y$</span>, and if <span class="math-container">$M$</span> does, then <span class="math-container">$X$</span> contains an isolated periodic point while <span class="math-container">$Y$</span> does not, so <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> are not conjugate. So an algorithm with the properties listed in the statement would solve the halting problem, thus cannot exist. Square.</p>

<blockquote>
  <p>Corollary: Equality and conjugacy of subshifts given by forbidden context-free languages are both undecidable problems.</p>
</blockquote>

<p>Proof. Let's do conjugacy. If conjugacy were decidable by algorithm <span class="math-container">$A$</span>, then it would give an algorithm <span class="math-container">$B$</span> that accomplishes what we claimed cannot be done: given <span class="math-container">$X$</span> and <span class="math-container">$Y$</span>, if <span class="math-container">$A$</span> says they are conjugate, <span class="math-container">$B$</span> claims they are the same, and if <span class="math-container">$A$</span> says they are not conjugate, <span class="math-container">$B$</span> claims they are not conjugate as well. Now if <span class="math-container">$X = Y$</span>, certainly <span class="math-container">$A$</span> says they are conjugate, so <span class="math-container">$B$</span> says they are the same. If <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> are not conjugate, <span class="math-container">$A$</span> detects this, so <span class="math-container">$B$</span> also says they are not conjugate, contradicting the previous theorem. Square.</p>

<p>You can ask many follow-ups: can you make this topologically mixing (or some stronger gluing notion), can you use something weaker than CFL, and can you have the language be CFL rather than the forbidden patterns, etc. Have at it.</p>

CC BY-SA 4.0
2020-04-11T15:39:53.363Z
Sorry, I wrote this for two-sided subshifts, because I'm more used to them and was not reading carefully. I'm sure it's easy to adapt for one-sided, maybe the description works directly. You mention cellular automata; for cellular automata on full shifts, it's indeed known that conjugacy by homeomorphism or by reversible CA are both undecidable.
Ville Salo
CC BY-SA 4.0
2020-04-11T17:47:04.103Z
Excellent answer! Thanks!
Do you think the reduction can be simplified by starting from CFL universality? (it seems to follow the same lines)
Shaull
CC BY-SA 4.0
2020-04-11T17:58:08.977Z
Argh, between two hashes forbid all words of a given context-free language $L$. This is empty iff $L$ is universal. Silly me!
Ville Salo
CC BY-SA 4.0
2020-04-11T18:00:08.150Z
Ok not that easy, you get all/some hashless words in any case. Anyway, I imagine you can give a simpler proof based on this idea.
Ville Salo
CC BY-SA 4.0
2020-04-11T18:03:00.873Z
I agree that the idea seems correct in spirit (I'll be surprised if it can't be fixed).
Shaull
CC BY-SA 4.0
2020-04-11T18:07:55.993Z
So a natural question is: is emptiness decidable for this class?
Ville Salo
CC BY-SA 4.0
2020-04-11T19:41:44.093Z
I'm just now getting into the field, so I don't have the slightest idea. But I can let you know if I make any progress on this.
Shaull
CC BY-SA 4.0
2020-04-11T15:35:50.020Z
2020-04-11T15:52:49.070Z
2020-04-11T15:52:49.070Z
Ville Salo
<p>The question of whether two finite one directional shifts are conjugates is known to be decidable. </p>

<p>The same question for sofic shifts is famously open.</p>

<p>I have seen that some works manage to prove undecidability of related problems for cellular automata. My question is what is the known undecidability landscape?</p>

<p>Do we know that it's undecidable if the shift corresponds to e.g., a context-free grammar? A one counter automaton? Something else?</p>

<p>To keep things focused, I am more interested in undecidability results that step from the underlying computational model, rather than an increased dimension.</p>

<p>I didn't bother writing the definitions, since I assume anyone not familiar with them will not likely be able to answer the question anyway...</p>

CC BY-SA 4.0
2020-04-13T14:52:28.583Z
It's more on the "increased dimension" side, but you might be interested by decidability results for subshifts on infinite trees, it's kind of intermediate between one and two dimensions. You have for instance several papers of Nathalie Aubrun on this question: https://perso.ens-lyon.fr/nathalie.aubrun/publications.html
Denis
CC BY-SA 4.0
2020-04-13T18:31:36.580Z
Thanks! More importantly, I now know that you know things about shift, and so I'll just direct all future questions to you :)
Shaull
<automata-theory><undecidability><cellular-automata>
What is the minimal class of subshifts for which conjugacy is known to be undecidable?
Shaull
# What is the minimal class of subshifts for which conjugacy is known to be undecidable?

(Asked by: username_0 on 2020-03-29)

The question of whether two finite one directional shifts are conjugates is known to be decidable.

The same question for sofic shifts is famously open.

I have seen that some works manage to prove undecidability of related problems for cellular automata. My question is what is the known undecidability landscape?

Do we know that it's undecidable if the shift corresponds to e.g., a context-free grammar? A one counter automaton? Something else?

To keep things focused, I am more interested in undecidability results that step from the underlying computational model, rather than an increased dimension.

I didn't bother writing the definitions, since I assume anyone not familiar with them will not likely be able to answer the question anyway...

**Tags:** automata-theory, undecidability, cellular-automata
> **Comments:**
> **username_1**: It's more on the "increased dimension" side, but you might be interested by decidability results for subshifts on infinite trees, it's kind of intermediate between one and two dimensions. You have for instance several papers of Nathalie Aubrun on this question: https://perso.ens-lyon.fr/nathalie.aubrun/publications.html  
> **username_0**: Thanks! More importantly, I now know that you know things about shift, and so I'll just direct all future questions to you :)  

---

## 1 answers

### Answer by username_2 on 2020-04-11. Score: 2

Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e.

> Theorem. There is no algorithm that given two context-free languages, says "same" if they define the same subshift, and says "non-conjugate" if they are not conjugate.

Note that no requirement, even on halting, is made when they are distinct and conjugate.

Proof. Note that CFL are closed under unions and contain all regular languages, so we can forbid finitely many regular and CFL languages. We will forbid a bunch of things to force our configurations to simulate Turing machines.

Let $M$ be a Turing machine with state set $Q$ and alphabet $A$, suppose $Q \cap A = \emptyset$ and $\#, @ \notin A \cup Q$, and $0 \in A$. Let $q\_0 \in Q$ be the initial state of $Q$ and $q\_f$ the unique halting state.

We will construct two subshifts $X$ and $Y$ over the alphabet $Q \cup A \cup \{\#, @\}$ such that if $M$ reaches the halting state $q\_f$ from the initial configuration $q\_0 0^\omega$ then $X$ and $Y$ are not conjugate, and if $M$ does not, then $X = Y$ as sets.

I won't list the precise forbidden patterns since it's a lot of programming, but I'll explain what they accomplish. I'll say what needs to be true about subwords of a certain form, which you can turn into forbidden patterns by forbidding the complement of these conditions. First, with a regular set of forbidden patterns we force that $\#$ and $@$ alternate, and the word between any consecutive appearance of $\#$ and $@$ (in either order) is an element of $A^\* Q A^\*$ (so there's a Turing machine configuration between $\#$ and $@$).

Next, with a context-free set of forbidden patterns we force that in every pattern $u@v$ where $u, v \in (Q \cup A)^\*$, we have $u = v^R$ where $v^R$ denotes reversal. We also force that in every word $\#u@va$ with $|u| = |v|$, $u, v \in (Q \cup A)^\*$ and $a \in Q \cup A \cup \{\#, @\}$, we have $a = \#$, and the three symmetric conditions that together force that $\#$ and $@$ appear in a single arithmetic progression.

Next, the main trick. It's the one used in the standard proof of undecidability of whether two given context-free languages intersect: we require that in every word $@ v \# u @$, if $v$ does not contain $q\_f$, then $u$ is the configuration that follows $v^R$ in the rule of $M$. If $v$ does contain $q\_f$, then we require that $u^R$ is the unique word in $q\_0 0^\*$ of the correct length.

Finally, require that in every word $@ v \# w \# v^R @$ where $v \in (Q \cup A)^\*$, the state $q\_f$ appears somewhere in $w$. These patterns define the subshift $X$.

Let us analyze what kind of configurations appear in $X$. First, no matter whether $M$ halts on input $q\_0 0^\omega$, in $X$ you have all configurations of the form $x @ y$ and $x \# y$ where $x$ and $y$ are over the alphabet $Q \cup A$, and all the limits of such configurations under the shift action, namely the full shift $(Q \cup A)^{\mathbb{Z}}$. Let $Y \subset X$ be this subset. It's a sofic subshift.

Suppose then that both $\#$ and $@$ appear in a configuration of $X$ (recall that they must alternate, so this happens unless the configuration is in $Y$), then the rules force that $@$ and $\#$ appear periodically in an arithmetic progression, and the configuration is of the form
$$ \ldots v\_{-1} \# u\_0 @ v\_0 \# u\_1 @ v\_1 \# u\_2 @ v\_2 \# u\_3 @ \ldots $$
with all the $|u\_i|$ and $|v\_i|$ of the same length, $u\_i = v\_i^R$ and the $M$-successor of $u\_i$ is $u\_{i+1}$. Since the lengths are the same, the computation must enter a loop starting from any $u\_i$, i.e. $u\_m = u\_k$ for some $m < k$. The last rule then forces an appearance of $q\_f$ somewhere between $u\_m$ and $u\_k$. But this means there is an occurrence of $q\_0 0^n$ between them as well. Another application of this argument shows that the computation from $q\_0 0^n$ reaches the halting state $q\_f$.

We see that any configuration not in $Y$ is periodic, and must periodically repeat the accepting computation of $M$ on some $q\_0 0^n$, where $n$ is any integer large enough that he computation has time to halt. (And if $M$ does halt on $q\_0 0^n$, then periodically repeating the computation gives a valid configuration of $X$.)

In conclusion, if $M$ never halts on $q\_0 0^\omega$, $X = Y$, and if $M$ does, then $X$ contains an isolated periodic point while $Y$ does not, so $X$ and $Y$ are not conjugate. So an algorithm with the properties listed in the statement would solve the halting problem, thus cannot exist. Square.

> Corollary: Equality and conjugacy of subshifts given by forbidden context-free languages are both undecidable problems.

Proof. Let's do conjugacy. If conjugacy were decidable by algorithm $A$, then it would give an algorithm $B$ that accomplishes what we claimed cannot be done: given $X$ and $Y$, if $A$ says they are conjugate, $B$ claims they are the same, and if $A$ says they are not conjugate, $B$ claims they are not conjugate as well. Now if $X = Y$, certainly $A$ says they are conjugate, so $B$ says they are the same. If $X$ and $Y$ are not conjugate, $A$ detects this, so $B$ also says they are not conjugate, contradicting the previous theorem. Square.

You can ask many follow-ups: can you make this topologically mixing (or some stronger gluing notion), can you use something weaker than CFL, and can you have the language be CFL rather than the forbidden patterns, etc. Have at it.

> **Comments:**
> **username_2**: Sorry, I wrote this for two-sided subshifts, because I'm more used to them and was not reading carefully. I'm sure it's easy to adapt for one-sided, maybe the description works directly. You mention cellular automata; for cellular automata on full shifts, it's indeed known that conjugacy by homeomorphism or by reversible CA are both undecidable.  
> **username_0**: Excellent answer! Thanks! Do you think the reduction can be simplified by starting from CFL universality? (it seems to follow the same lines)  
> **username_2**: Argh, between two hashes forbid all words of a given context-free language $L$. This is empty iff $L$ is universal. Silly me!  
> **username_2**: Ok not that easy, you get all/some hashless words in any case. Anyway, I imagine you can give a simpler proof based on this idea.  
> **username_0**: I agree that the idea seems correct in spirit (I'll be surprised if it can't be fixed).  
> **username_2**: So a natural question is: is emptiness decidable for this class?  
> **username_0**: I'm just now getting into the field, so I don't have the slightest idea. But I can let you know if I make any progress on this.  

---

