The relationship between word complexity and computational complexity in subshifts (Q1995561)

Given a finite set \(A\), a subshift over \(A\) is a subset of \(A^\mathbb{Z}\) which is closed in the product topology and invariant under the shift map \(\sigma\) defined by \((\sigma x)(n)=x(n+1)\). The word complexity function \(c_n(X)\) of a subshift \(X\) is defined by \(c_n(X)=|{\mathcal L}_n(X)|\), where \({\mathcal L}_n(X)\) is the set of all words of length \(n\), i.e., \(c_n(X)\) is the number of all words with length \(n\) appearing in some \(x\in X\). The Turing spectrum of a subshift \(X\), denoted by \(\mathrm{Sp} (X)\), is the set \(\{\mathbf{d} | \exists x\in X, \mathrm{deg}_T (x) = \mathbf{d}\}\) of all Turing degrees of all points of \(X\). \par The authors study the relationship between the word complexity function of a subshift and the Turing spectrum of the subshift. In particular, it is proved that a Turing spectrum can be realized via a subshift of linear complexity if and only if it consists of the union of a finite set and a finite number of cones, that a Turing spectrum can be realized via a subshift of exponential complexity if and only if it contains a cone, and that every Turing spectrum which either contains degree \(\mathbf 0\) or is a union of cones is realizable by subshifts with a wide range of ``intermediate'' complexity growth rates between linear and exponential.