7 papers
Two block gluing constructions
Ville Salo, Ilkka Törmä, Ilkka Törmä
We prove two existence results about block gluing in two-dimensional SFTs. First, a large class of functions between exponential and logarithmic can be realized as block gluing fun…
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…
On Countable SFT Covers of Sparse Multidimensional Shift Spaces
Ilkka Törmä
A multidimensional sofic shift is called countably covered if it has an SFT cover containing only countably many configurations. In contrast to the one-dimensional setting, not all…
A perturbed cellular automaton with two phase transitions for the ergodicity
Hugo Marsan, Mathieu Sablik, Ilkka Törmä
The positive rates conjecture states that a one-dimensional probabilistic cellular automaton (PCA) with strictly positive transition rates must be ergodic. The conjecture has been…
Multidimensional tilings and MSO logic
Rémi Pallen, Ilkka Törmä
We define sets of coulourings of the infinite discrete plane using monadic second order (MSO) formulas. We determine the complexity of deciding whether such a formula defines a sub…
Structure and computability of preimages in the Game of Life
Ville Salo, Ilkka Törmä
Conway's Game of Life is a two-dimensional cellular automaton. As a dynamical system, it is well-known to be computationally universal, i.e.\ capable of simulating an arbitrary Tur…