Ville Salo's webpage

"Subshift" can mean many things, but for me usually it means a topologically closed set \(X \subset A^G\) where \(G\) is a countable group and \(A\) a finite alphabet, which is closed under the shift action of \(G\) defined by the formula \(gx_h = x_{g^{-1}h}\). The automorphism group of a subshift is the group of self-homeomorphisms that commute with the actions of all \(g \in G\).

I have several results dealing with the construction of finitely-generated subgroups of \(A^{G}\) (in particular the classical case \(G = \mathbb{Z}\)), limitations on them, and on the structure of automorphism groups of minimal subshifts and countable subshifts. I have so many papers on this topic that it's hard to choose one result to mention, but perhaps the most interesting one is that I found here the first examples of natural finitely-generated groups where the conjugacy problem is undecidable (and then also finitely-presented such groups).

Let \(G\) be a countable group and \(A\) a finite alphabet. Then \(G\) acts on \(A^G\) by the formula \(gx_h = x_{g^{-1}h}\). A subshift of finite type or SFT is a set of the form \(\{x \in A^G\;|\; \forall g\in G: gx \notin C\}\) where \(C\) is clopen. A sofic shift is a factor (shift-commuting continuous image) of a subshift of finite type. Two classical topics are the construction of SFTs (equivalently, of sofic shifts) where the group action is free, and proofs that the emptiness problem for SFTs is undecidable. These can be seen as interesting geometric properties of the group.

I have looked at these problems these problems in many types of groups. In a large class of ("sufficiently complicated") groups, we showed with Barbieri and Sablik that the sofic shifts coincide with computable subshifts. This provides a very strong hammer solving the above problems and beyond. We have also shown such "simulation theorems" in other settings. In particular, with Bartholdi we solved the two problems listed above for the lamplighter group \(\mathbb{Z}_2 \wr \mathbb{Z}\). The importance of this specific group is that it is very simple, but contains no (Euclidean or hyperbolic) planes. All constructions of SFTs before this were somehow based on using planes in the group and doing classical tiling theory on them. Ultimately, we also use a plane, it is just well-hidden.

Lightface classification is a specific type of activity in effective descriptive set theory. We have mathematical objects that we can represent on a computer in some way, either as finite bit strings, or infinite ones. We try to understand the complexity of sets of objects that have a specific property, the idea being that this is an absolute bound on how hard it is to solve the property or give equivalent formulas.

I'll mention one recent result of mine. Let's say a cellular automaton is a continuous shift-commuting function \(f : A^{\mathbb{Z}^d} \to A^{\mathbb{Z}^d}\). This is a continuous self-map of the full shift \(A^{\mathbb{Z}^d}\), which is a compact metric space, so we are in a very standard case of dynamical systems. Such a map is sensitive (to initial conditions) if there exists \(\varepsilon > 0\) such that for any point \(x\) of the space, there are points arbitrarily close to it, whose trajectories eventually separate from that of \(x\) by at least \(\varepsilon\). This is considered one of the main ingredients of "chaos" in dynamical systems.

Recently, we showed with Tom Favereau that sensitivity is very difficult to solve on a computer, given the description of a cellular automaton. In fact, in the case of dimension one (\(d=1\)), it is impossible to solve even if you know the solution to the halting problem. In two dimensions, it is even impossible if you know the halting problem of Turing machines that know the solution to the halting problem. But it's no harder than that. (In technical terms, the problems are \(\Pi^0_2\)-complete and \(\Sigma^0_3\)-complete, respectively.)

Often, in symbolic dynamics our basic objects (subshifts, their automorphism groups, cellular automata...) are so complicated, that we can't expect to have any simple descriptions of any phenomena. So what we do is try to show that we can in some sense to absolutely anything.

For example, we gave an example of a "physically universal" Turing machine with Ilkka Törmä (it can implement any transformation of space, in a sense). As another example (not really in the spirit of the previous paragraph, but whatever), I've shown that every even permutation of \(\{0,1\}^n\) (for \(n \geq 4\)) can be written as a composition of the "flip the \(i\)th bit if the left neighbor is \(1\) or the right neighbor is \(0\)". You can try to flip a single bit here. As far as I know, no human has ever succeeded in this (of course it's easy to write a search script, that's what I did for my paper).

Subshifts (over a fixed group) form a category. It has products, so you can talk about internal algebras. For examples, internal groups are a classical object, and are called group shifts. Something we observed with Ilkka Törmä many years ago is that sometimes properties of the variety imply properties for internal algebras in this category. For example, if an algebra is "shallow" (meaning "affine maps" are equivalent to ones of bounded depth) then every internal subshift algebra is isomorphic to one whose operations are defined cellwise (i.e. the alphabet of the subshift is in the variety).

We still don't have an example of a variety which is non-shallow, but where the same happens, but we have looked at various classes of lattices and Lie algebras, among others.

Sometimes people speak of symbolic dynamics as "the swamp of undecidability", a funny term due to Douglas Lind. While, as I've discussed above, it's possible to turn this pessimism around into universality results, sometimes it's still nice to consider more restricted classes, where there are less constructions and more proofs. I have invented several classes of SFTs that are better-behaved than general SFTs, in particular TEP subshift and avoshifts. The latter generalizes group shifts.

Imagine you drop some type of turtle (with a very small brain) on some type of graph. It walks around, trying to understand where it is. What kind of properties can be observed by a turtle, if we cleverly program its brain?

For example, for subshifts on groups that are defined this way, we showed with Ilkka Törmä that 3 turtles can already define the same subshift that any finite amount can, if the groups is not torsion and has decidable word problem (otherwise, I've shown the sharp limit is 4 turtles). On torsion groups, on the other hand, you may need an arbitrary amount of turtles.

Much of dynamics studies things like invariant measures and entropy. This is hot dynamics. By cold dynamics (a term I learned from Guillaume Theyssier), we mean all the other stuff. Zero entropy is still lukewarm dynamics for me, and I usually have in mind even colder stuff. Things like the trivial map, the map that takes all points to some zero point, dynamical systems with countably many points.

One example of such a result of mine. Let's say a cellular automaton is a continuous shift-commuting function \(f : A^G \to A^G\), where \(A\) is a finite alphabet and \(G\) a finitely-generated group. This is a continuous self-map of the full shift \(A^G\), which is a compact metric space, so we are in a very standard case of dynamical systems. Let's say such a map is asymptotically nilpotent if every point tends to the same zero-point \(0\), and nilpotent if this convergence is uniform. We showed with Ilkka Törmä that if \(G\) is residually finite and virtually solvable, then these properties are equivalent.

It's interesting to fix a single complex system, and then try to understand it. We've looked quite a lot at Game of Life with Ilkka Törmä. I don't think it's a particularly special cellular automaton (it's not even all that special in the class of totalistic rules that Conway took it from). It's really just a famous one, and thus seems like the natural canonical choice for an arbitrary complex rule to study.

With Ilkka Törmä, we have solved many open problems of the Game of Life community. Our main result is perhaps the solution to Conway's "unique father problem". We also have, for instance, periodic configurations that have a Game of Life preimage, but have no periodic such preimage.

With Ilkka Törmä, we develop the Python package Griddy, which can do various things related to symbolic dynamics.