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

- (Q68185067) Does there exist a subgroup \(H \leq \mathrm{Aut}_2\) which is finitely generated and contains an isomorphic copy of \(\mathrm{Aut}_2\)?
- (Q31510155) Is the commutator subgroup \([\mathrm{Aut}_2, \mathrm{Aut}_2]\) is finitely generated?
- (Q71003309) Does the commutator subgroup \([\mathrm{Aut}_2, \mathrm{Aut}_2]\) contain an isomorphic copy of \(\mathrm{Aut}_2\)?
- (Q41006072) Do the automorphism groups of mixing \(\mathbb{Z}\)-SFTs always embed in each other?
- (Q52648523) Is the set of subgroups of \(\mathrm{Aut}_2\) closed under wreath produces with abelian base?
- (Q94425830) Does \(\mathbb{Z}_2 \wr (\mathbb{Z}_2 \wr \mathbb{Z}^2)\) embed in \(\mathrm{Aut}_2\)?
- (Q32632855) Does \(\mathbb{Z}_2 \wr (\mathbb{Z} \wr \mathbb{Z})\) embed in \(\mathrm{Aut}_2\)?
- (Q71824582) Does \(\mathbb{Z}_2 \wr (\mathbb{Z}_2 \wr (\mathbb{Z}_2 \wr \mathbb{Z})))\) embed in \(\mathrm{Aut}_2\)?
- (Q93226418) Let \(g \in \mathrm{Aut}_2\) be of infinite order. What are the possible word norm growth functions for \(g^n\). In particular, is \(\mathrm{log}(n)\) possible?
- (Q28615120) Are there ever distortion elements in \(\mathrm{Aut}(X)\) for \(X\) a minimal \(\mathbb{Z}\)-subshift? (see [Cyr-Franks-Kra-Petite, 2018])
- (Q83349536) Are there ever distortion elements in \(\mathrm{Aut}(X)\) for \(X\) a \(\mathbb{Z}\)-subshift of zero entropy? (see [Cyr-Franks-Kra-Petite, 2018])
- (Q56041295) Can we embed the \(3 \times 3\) Heisenberg group in \(\mathrm{Aut}_2\)? (see [Cyr-Franks-Kra-Petite, 2018])
- (Q47805222) Can we embed the Baumslag-Solitar group \(BS(1, 2)\) in \(\mathrm{Aut}_2\)? (see [Cyr-Franks-Kra-Petite, 2018])
- (Q39301965) Does \(\mathrm{Aut}(A^{\mathbb{N}})\) have distorted infinite cyclic sybgroups?
- (Q43824104) Does some \(\mathbb{N}\)-subshift have distorted infinite cyclic sybgroups?
- (Q88293014) Which alternation diameters can be realized by automorphism groups of product subshifts on \(\mathbb{Z}\)? [Salo, 2019]
- (Q99642960\(n\)) Here \(n \in \{3, \ldots, 7\}\). Does the Tits alternative hold for finitely-generated subgroups of \(\mathrm{Aut}(\{0, \ldots, n-1\}^{\mathbb{N}})\)?

### Cellular automata

- (Q58966162) Prove or disprove that for \(G\) a f.g. infinite group there always exists a linear CA \(f : V^G \to V^G\) with \(V^G\) a vector shift over a one-dimensional vector alphabet over a finite field \(F\), such that \(f\) has infinite order.
- (Q49883316) On what level of the lightface hierarchy is the set of pairs of shift-commuting homeomorphisms of \(A^{\mathbb{Z}}\) whose \(\mathbb{Z}\)-actions are topologically conjugate?
- (Q88904753) Does the hierarchy of alternated left-right and right-left sweeps in the sense of [Kari-Salo-Worsch, 2022] collapse on a finite level?
- (Q82791556) Does there exist an infinite mixing SFT \(X\) with alphabet contained in the natural numbers and \(f \in \mathrm{Aut}(X)\), such that \(\langle \sigma, f \rangle\) acts (set-theoretically) transitively on the set of nonzero points whose sum is finite?
- (Q72881388) If two cellular automata on \(A^{\mathbb{Z}}\) have topologically conjugate actions, and one is physically universal [Janzing, 2010], is the other one physically universal?
- (Q40119461) Is every group nilrigid?
- (Q73216310) Is the free group nilrigid?

### SFTs on groups

- (Q69313023) Do strongly irreducible SFTs on free groups have dense periodic points?
- (Q60039472) Do contractible SFTs [Poirier-Salo, 2024] on free groups have dense periodic points?
- (Q32530541) Is there a contractible SFT [Poirier-Salo, 2024] that is not equiconnected [Poirier-Salo, 2024], on some finitely-generated group \(G\)?
- (Q70544785) Does periodic asymptotic dimension [Poirier-Salo, 2024] stay finite in general residually finite group extensions?
- (Q58004875) What is the periodic asymptotic dimension [Poirier-Salo, 2024] of the free group with two generators?
- (Q73527718) Does the formula \(\mathrm{pdim}(G) \leq \mathrm{pdim}(K)+ \mathrm{pdim}(H)\) hold for periodic asymptotic dimension for (split or non-split) residually finite group extensions?
- (Q40844502) Is the group \(\mathrm{GL}(3, \mathbb{Z})\) self-simulable?
- (Q61891253) Is the group \(\mathrm{GL}(4, \mathbb{Z})\) self-simulable?
- (Q57744315) Is the group \(\mathrm{Aut}(F_3)\) self-simulable?
- (Q67892478) Is the group \(\mathrm{Aut}(F_4)\) self-simulable?
- (Q30095206) Is the group \(B_4\) self-simulable?
- (Q04951137) Is the group \(B_5\) self-simulable?
- (Q24550767) Is the group \(B_6\) self-simulable?
- (Q91241495) Let \(H, N\) be f.g. infinite groups with decidable word problem, and suppose \(N\) is nonamenable. Is the free extension of every effective zero-dimensional \(H\)-system to \(H \times N\) a factor of a subshift of finite type?
- (Q35767585) Let \(H, N\) be f.g. infinite amenable groups. Suppose that an \(H\)-subshift \(X\) has sofic free extension in \(H \times N\). Is \(X\) necessarily sofic?
- (Q40486487) Let \(G = H \times K\) be the direct product of two infinite finitely generated amenable groups with decidable word problem. Does \(G\) necessarily admit a nonempty strongly aperiodic SFT?
- (Q69508105) Let \(G = \mathbb{Z}_2 \wr \mathbb{Z}\) be the lamplighter group. Is there a nonempty minimal strongly aperiodic SFT on this group?
- (Q95122252) Let \(G = \mathbb{Z}_2 \wr \mathbb{Z}\) be the lamplighter group. Is there a nonempty mixing strongly aperiodic SFT on this group?
- (Q67371411) Suppose \(G\) and \(H\) are quasi-isometric finitely-generated groups. If \(G\) admits a strongly aperiodic SFT, does \(H\) admit one as well?

### Topological full groups and Turing machines

- (Q28144864) Is the set of subgroups of the topological full group of a full \(\mathbb{Z}\)-shift closed under free products?
- (Q70642959) Is the commutator subgroup of the group of reversible Turing machines \(\mathrm{RTM}(n, k)\) finitely generated?
- (Q81088309) On what level of the lightface hierarchy is the set of pairs of reversible Turing machines whose moving tape actions are topologically conjugate?
- (Q68731251) Is there a topologically mixing minimal one-dimensional Turing machine in the moving tape model?
- (Q66333933) Is there a physically universal [Salo-Törmä, 2023] one-dimensional Turing machine?
- (Q05283500) What are the possible movement functions of reversible Turing machines (asymptotically)? (The movement function is \(m : \mathbb{N} \to \mathbb{N}\), where \(m(n)\) is the maximal number of steps that the head can move in \(n\) time steps.)
- (Q00368174) Given two elements of the topological full group of a full \(\mathbb{Z}\)-shift, is it decidable whether they satisfy a non-trivial relation?

### 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.- (Q28820954) Let \(i \in \mathbb{N}\) be minimal such that \([\mathrm{pad}_i(P)] \cap g(X) \neq \emptyset \implies \forall j: [\mathrm{pad}_j(P)] \cap g(X) \neq \emptyset \) What is the value of \(i\)?
- (Q52773486) Is it decidable whether a given finite-support configuration has a finite-support preimage in the action of Game of Life?
- (Q37342605) What is the minimal \(n\) such that some \(n \times n\)-periodic configuration has a Game of Life preimage, but no (spatially) periodic preimage?
- (Q99848042) Is Game of Life generically nilpotent?
- (Q15988843) Is Game of Life sensitive to initial conditions?
- (Q97141311\(p\)) Let \(X_p\) be the subshift of temporally \(p\)-periodic configurations for Game of Life. Are points of finite support dense in this subshift?
- (Q36263295\(p\)) Let \(X_p\) be the subshift of temporally \(p\)-periodic configurations for Game of Life. Is this subshift strongly irreducible?

### CA with random initial conditions

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

- (Q64157361) We say a CA \(f\) is
*Cesàro randomizing*if for every full support Bernoulli measure \(\mu\) on \(A^{\mathbb{Z}}\), the Cesàro averages of the measures \(f^n(\mu)\) tend to the uniform Bernoulli measure. Is Cesàro randomization decidable for linear CA? - (Q87474795) We say a CA \(f\) is
*strongly randomizing*if for every full support Bernoulli measure \(\mu\) on \(A^{\mathbb{Z}}\), the measure \(f^n(\mu)\) tends to the uniform Bernoulli measure. Is strong randomization decidable for linear CA? - (Q50740965) Given a finite poset \(P\) with a minimal element \(0\) and a freezing monotone CA \(f\) on \(P^{\mathbb{Z}^2}\), meaning \(f(x) \leq x\) pointwise for all \(x \in P^{\mathbb{Z}^2}\) and \(f\) preserves the order, is it decidable whether for all full-support Bernoulli measures \(\mu\), \(f^n(\mu)\) tends to the Dirac measure on \(0^{\mathbb{Z}^2}\)?
- (Q56787677) Given a finite poset \(P\) with a minimal element \(0\) and a freezing monotone CA \(f\) on \(P^{\mathbb{Z}^2}\), meaning \(f(x) \leq x\) pointwise for all \(x \in P^{\mathbb{Z}^2}\) and \(f\) preserves the order, is it decidable whether there exists a full-support Bernoulli measure \(\mu\), such that \(f^n(\mu)\) tends to the Dirac measure on \(0^{\mathbb{Z}^2}\)?

### Unconventional symbolic dynamical systems

- (Q69923565) Let \(X, Y\) be mixing \(\mathbb{Z}\)-SFTs. Let \(X', Y'\) be obtained by removing their periodic points. Suppose there is a continuous shift-commuting bijection from \(X'\) onto \(Y'\). Are \(X\) and \(Y\) topologically conjugate?
- (Q02501119) Let \(X, Y\) be respectively the binary full shift and the subshift of \(3\)-colorings of \(\mathbb{Z}\). Let \(X', Y'\) be obtained by removing their periodic points. Does \(X'\) embed into \(Y\)?
- (Q88708532) Let \(X, Y\) be respectively the binary full shift and the subshift of \(3\)-colorings of \(\mathbb{Z}\). Let \(X', Y'\) be obtained by removing their periodic points. Does \(X'\) factor onto \(Y'\)?
- (Q92427765) Let \(X, Y\) be respectively the binary full shift and the subshift of \(3\)-colorings of \(\mathbb{Z}\). Let \(X', Y'\) be obtained by removing their periodic points. Does \(X'\) factor onto \(Y\)?
- (Q61569144) Is topological conjugacy of \(\frac{\mathrm{sofic}}{\mathrm{sofic}}\)-systems [Kopra-Salo, 2021] semidecidable?
- (Q03967332) What kind of numbers appear as topological entropies of \(\frac{\mathrm{sofic}}{\mathrm{sofic}}\)-systems [Kopra-Salo, 2021]? Are they logarithms of roots of Perron numbers?
- (Q86347885) Given two eventually periodic points of a \(\frac{\mathrm{sofic}}{\mathrm{sofic}}\)-system, what kind of number is their distance in the metric defined in [Kopra-Salo, 2021], and can it be computed?
- (Q31253998) Are all \(\frac{\mathrm{subshift}}{\mathrm{sofic}}\)-systems finite-dimensional?
- (Q00684980) Are all \(\frac{\mathrm{sofic}}{\mathrm{subshift}}\)-systems finite-dimensional?
- (Q25384319) What can be said about the number of periodic points in a \(\frac{\mathrm{sofic}}{\mathrm{sofic}}\)-system? (Are there finitely many periodic points of a given period? Is the Artin-Mazur \(\zeta\)-function rational?)

### Groups

- (Q05259301) Does every strongly polycyclic group admit a midpointed translation-invariant convex geometry [Salo, 2022]?
- (Q80146349\(d\)) Here \(d \geq 2\). What are the maximal translation-invariant midpointed extensions of the standard convex geometry of \(\mathbb{Z}^d\)? [Salo, 2022]
- (Q87501041) Let \(G\) be a torsion-free finitely-generated infinite group. Let \(S\) be a finite subset of \(G\). We say \(T \subset G\) is
*closed for \(S\)-filling*if whenever \(gS \cap T = gS'\) where \(S' \sqcup \{s\} = S\), we have \(gs \in T\). Suppose that there is a finite subset \(T' \subset G\) such that the smallest set \(T \subset G\) which contains \(T'\) and is closed under \(S\)-filling is infinite. Is \(S\) necessarily contained in \(a\langle b \rangle c\) for some \(a, b, c \in G\)? - (Q62353942) Let \(G\) be a torsion-free finitely-generated infinite group. Let \(S\) be a finite subset of \(G\). For finite systems, \(T_1, T_2 \subset G\) we write \(T_1 \sim_S T_2\) if there exists \(g \in G\) and two distinct elements \(s_1, s_2 \in S\) such that the set difference \(T_1 \;\Delta\; T_2\) is \(\{gs_1, gs_2\}\), and both sets contain \(gS \setminus \{gs_1, gs_2\}\). If some finite \(T \subset G\) has an infinite connected component in the graph with edges \(\sim_S\), is \(S\) necessarily contained in \(a\langle b \rangle c\) for some \(a, b, c \in G\)?
- (Q30995752) Let \(G \leq \prod_{n \geq 2} A_{2n+1}\) be the Neumann group (generated by diagonal initial 3-cycles and diagonal full cycles). Does \(G * G\) admit a faithful action such that the connected components of the Schreier graph have uniformly subquadratic growth?

### Subshifts on abelian groups

- (Q27452691) Is the last sentence of Lemma 3 in [Salo, 2017] true?
- (Q86709357) Given two \(\mathbb{Z}\)-subshifts of finite type such that the space is countable, what is the complexity of the conjugacy problem? Is it decidable?
- (Q93289984) Given two sofic \(\mathbb{Z}\)-shifts such that the space is countable, what is the complexity of the conjugacy problem? Is it decidable?
- (Q78117387) Let \(X \subset \{0, 1\}^{\mathbb{Z}^2}\) be an SFT with the closure property \(x \in X \wedge \forall \vec v : y_{\vec v} \leq x_{\vec v} \implies y \in X\). Let \(p \in [0, 1]\) be the maximal measure of the cylinder \([1]\) in a shift-invariant probability measure on \(X\). Is \(p\) necessarily rational?
- (Q98495721) Is the sunny-side-up the \(\mathbb{Z}\)-trace of a \(\mathbb{Z}^3\)-SFT?

### Assorted

- (Q96058605) Is the head hierarchy of [Salo-Törmä, 2017] infinite on finitely-generated infinite torsion groups, if you allow telepathy (= shared state between far-away heads)?
- (Q44820604) On the group \(\mathbb{Z}\), do two-headed finite-state automata define the same subshifts as three-headed finite-state automata, in the sense of [Salo-Törmä, 2016]?
- (Q99641560) On the group \(\mathbb{Z}^2\), do two-headed finite-state automata define the same subshifts as three-headed finite-state automata, in the sense of [Salo-Törmä, 2016]?
- (Q25731482) Give a human proof that the embedding of Thompson's \(V\) in the mapping class group of a mixing SFT constructed in [Salo, 2021] splits.
- (Q38471943) Is there a universal algebraic variety \(V\) (with finitely many operations, and preferably as "natural" as possible) which is not shallow, yet all internal \(V\)-algebras in the category of subshifts on \(\mathbb{Z}\) can be cellwised. [Salo-Törmä, 2021]
- (Q84253285) Let \(X\) be a compact metric space. Let \(G \) be a group acting on \(X\), and \(H\) a semigroup acting on \(X\). Suppose the actions commute, \(H\) acts expansively, and \(G\) acts faithfully with all points periodic. Is \(G\) necessarily finite?
- (Q83394179\(n\)) Fill the \(n\)th empty square in Table 1 in [Salo-Törmä, 2015].
- (Q62356761) Are all sofic \(\mathbb{Z}\)-shifts \(X\) realizable through surjectivity of nonuniform cellular automata, in the sense that we can find a set of local rules such that the set of sequences over these rules which give a surjective map is exactly \(X\) (up to renaming symbols)?
- (Q80139192) Is the smallest subshift whose language contains the regular language \(0^*1^* + 1^*0^*\) realizable in the previous sense?
- (Q96181689) Is the smallest subshift whose language contains the regular language \((00 + 01)^*\) realizable in the previous sense?
- (Q63239731) Is the smallest subshift whose language contains the regular language \(0^*1^*0^*\) realizable in the previous sense?
- (Q51522054) Which subshifts are realizable in this sense, using only local rules of linear CA for some abelian group structure on the alphabet?
- (Q77059155) Which subshifts are winning shifts of \(\mathbb{N}\)-SFTs, in the sense of [Salo-Törmä, 2014]?
- (Q09685989) Which subshifts are winning shifts of mixing \(\mathbb{N}\)-SFTs, in the sense of [Salo-Törmä, 2014]?
- (Q68900134) Let \(X = \{0,1\}^{\mathbb{N}}\) be Cantor space. We construct another topological space by taking the clopen sets of \(X\) as points \(Y\), and for each \(x \in X\) we take \([x] = \{y \in Y \;|\; x \in y\}\) and the complements of such sets as a subbasis for a topology. Is this space definable by topological properties, and is it somehow "dual" to Cantor space?
- (Q46864016) Let \(X\) be an internal Jónsson-Tarski algebra in the category of subshifts over a group \(G\) (with block maps as morphisms). Suppose \(G\) has exponential growth. Is \(X\) necessarily the one-point subshift?
- (Q61373495) Is there a modular lattice subshift on \(\mathbb{Z}\) which is of finite type and mixing, and cannot be conjugated to a subshift \( Y \subset B^{\mathbb{Z}} \) where \(B\) is a modular lattice, so that the operations of \(X\) correspond to the cellwise operations of \(Y\).
- (Q05365023) Is the picture language class UFA [Kari-Salo, 2011] closed under union?
- (Q48675137) Are the picture language classes NFA and FNFA [Kari-Salo, 2011] equal in dimension three and higher?
- (Q13409404) Characterize the subsets \(D \subset \mathbb{Z}^2\) such that for \(X\) the Ledrappier subshift we have \(X|D = \{0,1\}^{\mathbb{Z}^2}\).
- (Q45457810\(S\)) Here \(S \Subset \mathbb{Z}^2\) is finite. Characterize the subsets \(D \subset \mathbb{Z}^2\) such that for all TEP subshifts \(X\) in the sense of [Salo, 2022], over any alphabet \(A\), we have \(X|D = A^{\mathbb{Z}^2}\).
- (Q16620019) Compile a list of open problems in symbolic dynamics. (Existing lists are missing many important problems.)

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