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...

  • 1
    $\begingroup$ 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: perso.ens-lyon.fr/nathalie.aubrun/publications.html $\endgroup$ – Denis Apr 13 '20 at 14:52
  • $\begingroup$ Thanks! More importantly, I now know that you know things about shift, and so I'll just direct all future questions to you :) $\endgroup$ – Shaull Apr 13 '20 at 18:31

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.

  • $\begingroup$ 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. $\endgroup$ – Ville Salo Apr 11 '20 at 15:39
  • $\begingroup$ Excellent answer! Thanks! Do you think the reduction can be simplified by starting from CFL universality? (it seems to follow the same lines) $\endgroup$ – Shaull Apr 11 '20 at 17:47
  • $\begingroup$ Argh, between two hashes forbid all words of a given context-free language $L$. This is empty iff $L$ is universal. Silly me! $\endgroup$ – Ville Salo Apr 11 '20 at 17:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Ville Salo Apr 11 '20 at 18:00
  • $\begingroup$ I agree that the idea seems correct in spirit (I'll be surprised if it can't be fixed). $\endgroup$ – Shaull Apr 11 '20 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.