Decidability problems in symbolic dynamics

Definitions and mathematical statement

A shift of finite type (SFT) is a space of symbol sequences specified by finitely many forbidden words. A sofic shift is the image of an SFT under a continuous shift-commuting map, equivalently the label sequences along paths in a finite labeled directed graph. Use either two-sided sequences indexed by $\mathbb Z$ or one-sided sequences indexed by $\mathbb N$, as specified. A conjugacy is a homeomorphism commuting with the shifts.

The principal decision questions ask for algorithms which halt on every input and decide conjugacy of two given SFTs, two given two-sided sofic shifts, or two given one-sided sofic shifts. Inputs are finite graph presentations; no bound on a possible conjugating block rule is given.

A further question starts with an SFT shift $S$ and an expansive automorphism $U$, defining $\alpha^{(a,b)}=S^aU^b$. A line $L\subset \mathbb R^2$ is expansive if some $R,\varepsilon>0$ make observation of $\alpha^v$ at every integer vector within distance $R$ of $L$ distinguish any two distinct points by at least $\varepsilon$. Determine whether the open component of expansive directions containing the $S$-direction can be effectively approximated from both sides.

The catalogue also mentions deciding whether a surjective full-shift block map has a continuous shift-commuting right inverse. That subquestion is decidable by the split-epicness theorem cited below. It is retained as resolved context; the conjugacy and expansive-direction questions are the targets here.

Short English statement

Resolve the remaining algorithmic classification and expansive-direction questions for finite symbolic presentations.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 4600030 (AMR-045-0030), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Boyle - Open Problems in Symbolic Dynamics (2008), Problem/Question/Conjecture 19.1. Original source indexed by AMR-045-0030. https://www.math.umd.edu/~mboyle/papers/openfinalsub3nov2007.pdf.
• S3 Salo, On von Neumann regularity of cellular automata, Theorem7; decidability of split epicness, following Salo–Törmä. https://arxiv.org/abs/2209.13373.