1D effectively closed subshifts and 2D tilings
Bruno Durand, Andrei Romaschenko and Alexander Shen
Laboratoire d'Informatique Fondamentale de Marseille
CNRS & Aix-Marseille Université, France
Abstract. Michael Hochman showed that every 1D effectively closed subshift
can be simulated by a 3D subshift of finite type and asked whether
the same can be done in 2D. It turned out that the answer is positive
and necessary tools were already developed in tilings theory.
We discuss two alternative approaches: first, developed by Nathalie Aubrun
and Mathieu Sablik, goes back to Leonid Levin; the second one, developed
by the authors, goes back to Peter Gacs.