JAC 2010

Journées Automates Cellulaires

Turku, Finland, December 15-17, 2010

Welcome Important Dates Committees Invited Speakers Call for Papers Call for Informal Presentations Participants
Registration Travel Venue Accommodation Climate Accepted papers Program

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.

Winter picture