45 citations · 158 across the 57 of their papers we have counts for
36 papers · 1 filter
A Three-Dimensional SFT with Sparse Columns
Ville Salo, Ilkka Törmä
We construct a nontrivial three-dimensional subshift of finite type whose projective -subdynamics, or -trace, is 2-sparse, meaning that there are at most two nonzero symbol…
Symbol Frequencies in Surjective Cellular Automata
Benjamin Hellouin de Menibus, Ilkka Törmä, Ville Salo
We study the behavior of probability measures under iteration of a surjective cellular automaton. We solve the following question in the negative: if the initial measure is ergodic…
Topological entropy of Turing complete dynamics
Renzo Bruera, Robert Cardona, Eva Miranda +2
We explore the relationship between Turing completeness and topological entropy of dynamical systems. We first prove that a natural class of Turing machines that we call "branching…
Automorphism groups of random substitution subshifts
Robbert Fokkink, Dan Rust, Ville Salo
We prove that for a suitably nice class of random substitutions, their corresponding subshifts have automorphism groups that contain an infinite simple subgroup and a copy of the a…
What can oracles teach us about the ultimate fate of life?
Ville Salo, Ilkka Törmä
We settle two long-standing open problems about Conway's Life, a two-dimensional cellular automaton. We solve the Generalized grandfather problem: for all , there exists…
Sofically presented dynamical systems
Johan Kopra, Ville Salo
Systems obtained by quotienting a subshift of finite type (SFT) by another SFT are called finitely presented in the literature. Analogously, if a sofic shift is quotiented by a sof…
Conjugacy of transitive SFTs minus periodic points
Ville Salo
It is a question of Hochman whether any two one-dimensional topologically mixing subshifts of finite type (SFTs) with the same entropy are topologically conjugate when their period…
A Physically Universal Turing Machine
Ville Salo, Ilkka Törmä
We construct a two-dimensional Turing machine that is physically universal in both the moving tape and moving head model. In particular, it is mixing of all finite orders in both m…
Four heads are better than three
Ville Salo
We construct recursively-presented finitely-generated torsion groups which have bounded torsion and whose word problem is conjunctive equivalent (in particular positive and Turing…
Cutting Corners
Ville Salo
We define and study a class of subshifts of finite type (SFTs) defined by a family of allowed patterns of the same shape where, for any contents of the shape minus a corner, the nu…
Gardens of Eden in the Game of Life
Ville Salo, Ilkka Törmä
We prove that in the Game of Life, if the thickness-four zero-padding of a rectangular pattern is not an orphan, then the corresponding finite-support configuration is not a Garden…
Trees in positive entropy subshifts
Ville Salo
I give a simple proof for the fact that positive entropy subshifts contain infinite binary trees where branching happens synchronously in each branch, and that the branching times…
Recoding Lie algebraic subshifts
Ville Salo, Ilkka Törmä
We study internal Lie algebras in the category of subshifts on a fixed group -- or Lie algebraic subshifts for short. We show that if the acting group is virtually polycyclic and t…
Trees are nilrigid
Ville Salo
We study cellular automata on the unoriented -regular tree , i.e. continuous maps acting on colorings which commute with all automorphisms of the tree. We prove that…
Entropy pair realization
Ville Salo
We show that the CPE class of Barbieri and García-Ramos contains a one-dimensional subshift for all countable ordinals , i.e.\ the process of alternating topological and tra…
A note on directional closing
Ville Salo
We show that directional closing in the sense of Guillon-Kari-Zinoviadis and Franks-Kra is not closed under conjugacy. This implies that being polygonal in the sense of Franks-Kra…
Minimal subshifts with a language pivot property
Ville Salo
We construct a binary minimal subshift whose words of length n form a connected subset of the Hamming graph for each n.
Nilpotent Endomorphisms of Expansive Group Actions
Ville Salo, Ilkka Törmä
We consider expansive group actions on a compact metric space containing a special fixed point denoted by , and endomorphisms of such systems whose forward trajectories are attr…
Sequentializing cellular automata
Jarkko Kari, Ville Salo, Thomas Worsch
We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidab…
No Tits alternative for cellular automata
Ville Salo
We show that the automorphism group of a one-dimensional full shift (the group of reversible cellular automata) does not satisfy the Tits alternative. That is, we construct a finit…
On pointwise periodicity in tilings, cellular automata and subshifts
Tom Meyerovitch, Ville Salo
We study implications of expansiveness and pointwise periodicity for certain groups and semigroups of transformations. Among other things we prove that every pointwise periodic fin…
Characterizing Asymptotic Randomization in Abelian Cellular Automata
Benjamin Hellouin de Menibus, Ville Salo, Guillaume Theyssier
Abelian cellular automata (CA) are CA which are group endomorphisms of the full group shift when endowing the alphabet with an abelian group structure. A CA randomizes an initial p…
Transitive action on finite points of a full shift and a finitary Ryan's theorem
Ville Salo
We show that on the four-symbol full shift, there is a finitely generated subgroup of the automorphism group whose action is (set-theoretically) transitive of all orders on the poi…
A note on subgroups of automorphism groups of full shifts
Ville Salo
We discuss the set of subgroups of the automorphism group of a full shift, and submonoids of its endomorphism monoid. We prove closure under direct products in the monoid case, and…