Simulation of effective subshifts by two-dimensional subshifts of finite type (Q368710)

A \(d\)-dimensional subshift is a closed and shift-invariant subset of \(A^{\mathbb Z^d}\) for a finite alphabet \(A\) with respect to the product topology; these can be characterized either via their language (the set of finite words that appear somewhere in an element of the subshift) or by a collection of forbidden words (finite configurations that are not seen anywhere in an element of the subshift). The simplest class is thus the class of shifts of finite type -- those that can be defined by forbidding finitely many words. Here the question of how dynamically natural operations like taking factors or projecting onto a subaction interact with the defining set of forbidden words is considered. For the classical setting \(d=1\), the shifts of finite type are precisely those whose language is accepted by a local automaton (a result of \textit{M.-P. Beal} [Symbolic coding (French). Paris: Mason (1993)]), and the factors of shifts of finite type (also known as the sofic shifts, introduced by \textit{B. Weiss} [Monatsh. Math. 77, 462--474 (1973; Zbl 0285.28021)]) are similarly characterized without the locality condition. For \(d>1\) entirely new phenomena come into play, and a richer interaction between computational and recursion-theoretic properties of languages and the dynamics of subshifts arises. The main result here is that any effective \(d\)-dimensional subshift (that is, a subshift whose set of forbidden words can be generated by a Turing machine) can be obtained by applying the dynamical operations of forming factors and projecting onto subdynamics starting with a \((d+1)\)-dimensional subshift of finite type. This improves a result of \textit{M. Hochman} [Invent. Math. 176, No. 1, 131--167 (2009; Zbl 1168.37002)].