  In this article, we study classes of multidimensional subshifts defined by
multihead finite automata, in particular the hierarchy of classes of subshifts
defined as the number of heads grows. The hierarchy collapses on the third
level, where all co-recursively enumerable subshifts are obtained in every
dimension. We also compare these classes to SFTs and sofic shifts. We are
unable to separate the second and third level of the hierarchy in one and two
dimensions, and suggest a related open problem for two-counter machines.

Formal Languages and Automata Theory