Preamble

Here I list some open problems that have arisen from my research (with various coauthors, of course). Probably all the good questions were already asked before, and in such cases I try to give a reference. Do tell me if attributions are missing.

For now, I do not cite my own papers where the questions arose, nor explain the context, unless the question uses nonstandard terminology that is only explained in the paper (and even then, not necessarily). Hopefully this improves later. The questions have a randomly assigned id code, as I don't want to be married to a fixed ordering (because the categorization is currently rather bad). I may clarify a question without changing the id code, if I believe the content stays the exact same.

If you feel some question is not stated precisely enough, feel free to send me an email and I will add details. If you solve a problem, I'll be very interested in knowing. Many pairs of questions of course have substantial overlap or direct implications between them. I believe most of these questions are hard. There are a few where I don't remember why they were supposed to be hard, and there are a few I feel should be easy. This is not a fixed list, and I will keep updating it as I stumble into new or old problems.

Have fun.

Definitions

Definitions are mostly included in the questions, or just in the cited reference, but a few are listed here.

A (\(G\)-)subshift is a topologically closed \(G\)-invariant subset of \(A^G\) under \(G\)-translations, where \(A\) is a finite discrete alphabet. The full system \(A^G\) is the full shift. An SFT is a subshift defined by taking the points of the full shift whose orbit never enters a particular clopen set. We have natural analogs of these on monoids, in particular on \(\mathbb{N}\) (the shift may or may not be required to be surjective, but this shouldn't matter in the questions).

A morphism between subshifts is a continuous shift-commuting map. A factor map is a surjective morphisms, and an embedding is an injective one. A factor of a subshift is an image of it in a factor map. These terms also extend to other dynamical systems in an obvious way. A factor of an SFT is called sofic.

When \(X\) is a subshift, \(\mathrm{Aut}(X)\) refers to the group of self-homeomorphisms of \(X\) that commute with the shift maps on \(X\), i.e. its automorphisms. Write \(\mathrm{Aut}_n = \mathrm{Aut}(\{0,1,...,n-1\}^{\mathbb{Z}})\) for short. If \(G\) is a group, a subgroup \(H \leq G\) is universal if \(G \leq H\) (up to isomorphism).

A pattern is \(P \in A^D\) for (by default finite) \(D \subset G\), and the corresponding cylinder is \([P] = \{x \in A^G \;|\; x|D = P\}\), where \(G, A\) are understood from context.

Let \( G \) be a countably infinite group, \( A \) a finite alphabet with \( 0 \in A \). We have a continuous action \(G \curvearrowright A^G\) on the Cantor space \(A^G\) by \(gx_h = x_{g^{-1}h}\). Say \(G\) is nilrigid if the following holds Whenever a continuous function \(f : A^G \to A^G\) commutes with the \(G\)-action and satisfies \(\forall x \in A^G: f^n(x) \overset{n \rightarrow \infty}\longrightarrow 0^G\) where \(0^G \in A^G\) is the unique element of \(\{0\}^G\), we also have \( f^n(A^G) \overset{n \rightarrow \infty}\longrightarrow \{0^G\}. \)

Let \(G\) be a finitely-generated group with decidable word problem. We say \(G\) is self-simulable if all \(G\)-subshifts with a decidable language of defining forbidden patterns (a.k.a. \(\Pi^0_1\) or effective subshift) is sofic.

If \(H \leq G\) are groups, and \(X\) is a \(G\)-subshift, the \(H\)-trace of \(X\) is just \(\{x|_H \;|\; x \in X\}\). For a group \(G\) clear from context, the sunny-side-up is the subshift \(\{x \in \{0,1\}^G \;|\; \sum x \leq 1\}\). If \(G\) is a group, \(D \subset G\) is finite and \(P \in A^D\), then we write \([P] = \{x \in A^G \;|\; x|_D = P\}\). If \(H \leq G\) and \(X \subset A^H\) is a subshift, the free extension (or induction) is the subshift of \(A^G\) with the same forbidden patterns as \(X\). This idea extends naturally to other dynamical systems, by representing systems over a Cantor space alphabet.

If P is a property of configurations in \(A^G\), a configuration \(x \in A^G\) is asymptotically P if there is a configuration \(y \in A^G\) with property P such that \(\{g \in G \;|\; x_g \neq y_g\}\) is finite. If \(G = \mathbb{Z}^d\) a configuration is semilinear if for each \(a \in A\), \(\{\vec{v} \in \mathbb{Z}^d \;|\; x_{\vec{v}} = a\}\) is semilinear (definable in Presburger arithmetic). A configuration \(x \in A^G\) is periodic if \(\{g \in G \;|\; g\cdot x = x\}\) is a finite index subgroup of \(G\). If we have singled out a zero symbol \(0 \in A\) (usually meaning literally \(0 \in A\)), then the support of \(x \in A^G\) is \(\{g \in G \;|\; x_g \neq 0\}\).

Open problems

Automorphism groups

Cellular automata

SFTs on groups

Topological full groups and Turing machines

Game of Life

Let \(X = \{0,1\}^{\mathbb{Z}^2}\) and \(g : X \to X\) the Game of Life. For a rectangular pattern \(P \in \{0,1\}^{\{0,1,...,m-1\} \times \{0,1,...,n-1\}}\) denote by \(\mathrm{pad}_i(P)\) the pattern \(Q \in \{0,1\}^{\{-i,-i+1,...,m+i-1\} \times \{-i,-i+1,...,n+i-1\}}\) obtained by padding with zeroes on each side.

CA with random initial conditions

A cellular automaton \(f\) on \(A^{\mathbb{Z}}\) is linear if it respects an abelian group structure on \(A\).

Unconventional symbolic dynamical systems

Groups

Subshifts on abelian groups

Assorted




References



[Janzing, 2010] Janzing, Dominik. "Is there a physically universal cellular automaton or Hamiltonian?." arXiv preprint arXiv:1009.1720 (2010).

[Kari-Salo, 2011] Kari, Jarkko, and Ville Salo. "A survey on picture-walking automata." Algebraic Foundations in Computer Science: Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement (2011): 183-213.

[Salo-Törmä, 2014] Salo, Ville, and Ilkka Törmä. "Playing with subshifts." Fundamenta Informaticae 132.1 (2014): 131-152.

[Salo-Törmä, 2015] Salo, Ville, and Ilkka Törmä. "Category theory of symbolic dynamics." Theoretical Computer Science 567 (2015): 21-45.

[Salo-Törmä, 2016] Salo, Ville, and Ilkka Törmä. "Plane-walking automata." Cellular Automata and Discrete Complex Systems: 20th International Workshop, AUTOMATA 2014, Himeji, Japan, July 7-9, 2014, Revised Selected Papers 20. Springer International Publishing, 2015.

[Salo-Törmä, 2017] Salo, Ville, and Ilkka Törmä. "Independent finite automata on Cayley graphs." Natural Computing 16 (2017): 411-426.

[Salo, 2017] Salo, Ville. "Decidability and universality of quasiminimal subshifts." Journal of Computer and System Sciences 89 (2017): 288-314.

[Cyr-Franks-Kra-Petite, 2018] Cyr, V., Franks, J., Kra, B., & Petite, S. (2018). Distortion and the automorphism group of a shift. Journal of Modern Dynamics, 13.

[Salo, 2019] Salo, Ville. "Alternation diameter of a product object." arXiv preprint arXiv:1901.03613 (2019).

[Kari-Salo-Worsch, 2020] Kari, Jarkko, Ville Salo, and Thomas Worsch. "Sequentializing cellular automata." Natural Computing 19 (2020): 759-772.

[Salo, 2021] Salo, Ville. "Thompson's \(V\) in MCG of mixing SFT by PW-linear homeos." arXiv preprint arXiv:2103.15539 (2021).

[Kopra-Salo, 2021] Kopra, Johan, and Ville Salo. "Sofically presented dynamical systems." arXiv preprint arXiv:2105.06767 (2021).

[Salo-Törmä, 2021] Salo, Ville, and Ilkka Törmä. "Recoding Lie algebraic subshifts." Discrete and Continuous Dynamical Systems 41.2 (2021): 1005-1021.

[Salo, 2022] Salo, Ville. "Cutting corners." Journal of Computer and System Sciences 128 (2022): 35-70.

[Salo-Törmä, 2023] Salo, Ville, and Ilkka Törmä. "A physically universal Turing machine." Journal of Computer and System Sciences 132 (2023): 16-44.

[Poirier-Salo, 2024] Poirier, Leo, and Ville Salo. "Contractible subshifts." arXiv preprint arXiv:2401.16774 (2024).

Latest update: February 22nd, 2024.