Simulation of Effective Subshifts by Two-dimensional Subshifts of Finite Type

Abstract

In this article we study how a subshift can simulate another one, where the notion of simulation is given by operations on subshifts inspired by the dynamical systems theory (factor, projective subaction...). There exists a correspondence between the notion of simulation and the set of forbidden patterns. The main result of this paper states that any effective subshift of dimension d -- that is a subshift whose set of forbidden patterns can be generated by a Turing machine -- can be obtained by applying dynamical operations on a subshift of finite type of dimension d + 1 -- a subshift that can be defined by a finite set of forbidden patterns. This result improves Hochman's [Hoc09].

References in corpus (2)

• Fixed Point and Aperiodic Tilings
• Fixed-point tile sets and their applications

Cited by in corpus (22)

• Ergodic optimization in dynamical systems
• A notion of effectiveness for subshifts on finitely generated groups
• Zero-temperature phase diagram for double-well type potentials in the summable variation class
• The group of reversible Turing machines
• A generalization of the simulation theorem for semidirect products
• Computing (or not) Quasi-Periodicity Functions of Tilings
• Weak colored local rules for planar tilings
• Subsystem entropies of shifts of finite type and sofic shifts on countable amenable groups
• Self-simulable groups
• A geometric simulation theorem on direct products of finitely generated groups
• Subshifts with sparse traces
• On the Besicovitch-Stability of Noisy Random Tilings
• Slopes of 3-dimensional Subshifts of Finite Type
• Zero-Temperature Chaos in Bidimensional Models with Finite-Range Potentials
• Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings
• Simulation of minimal effective dynamical systems on the Cantor sets by minimal tridimensional subshifts of finite type
• The expressiveness of quasiperiodic and minimal shifts of finite type
• On the computability properties of topological entropy: a general approach
• Fixed Point Constructions in Tilings and Cellular Automata
• On the absence of zero-temperature limit of equilibrium states for finite-range interactions on the lattice ${\mathbb{Z}}^2$
• Ammann Bars for Octagonal Tilings
• Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models