Isomorphism of subshifts is a universal countable Borel equivalence relation

We use the theory of Borel equivalence relations to analyze the equiva-lence relation of isomorphism among one-dimensional subshifts. We show that this equivalence relation is a universal countable Borel equivalence relation, so that it admits no definable complete invariants fundamentally simpler than the equivalence classes. We also see that the classification of higher dimensional subshifts up to isomorphism has the same complexity as for the one-dimensional case. The problem of classifying one-dimensional and higher dimensional subshifts has been well studied, with the aim of finding invariants for isomorphism. One can consider this equivalence relation from the standpoint of descriptive set theory, and consider its complexity among Borel equivalence relations under the relation of Borel reducibility, ≤B. Definition 1. Let A be a finite set of symbols. A one-dimensional subshift on A is a closed subset of AZ which is invariant under the shift operator S, wher