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

preprint2016arXivOpen access

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.