We prove several results about the relationship between the word complexity function of a subshift and the set of Turing degrees of points of the subshift, which we call the Turing spectrum. Among other results, we show 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 (i.e. positive entropy) 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.
Citation: |
[1] |
J. Cassaigne, Special factors of sequences with linear subword complexity, in Developments in Language Theory II, At the Crossroads of Mathematics, Computer Science and Biology, Magdeburg, Germany, 17-21 July 1995, 1995, 25–34.
![]() ![]() |
[2] |
S. B. Cooper, Computability Theory, Chapman & Hall/CRC Mathematics Series, Chapman & Hall/CRC, 2004.
![]() ![]() |
[3] |
E. Coven, A. Johnson, N. Jonoska and K. Madden, The symbolic dynamics of multidimensional tiling systems, Ergodic Theory and Dynamical Systems, 23 (2003), 447-460.
doi: 10.1017/S014338570200113X.![]() ![]() ![]() |
[4] |
M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Annals of Mathematics, 171 (2010), 2011-2038.
doi: 10.4007/annals.2010.171.2011.![]() ![]() ![]() |
[5] |
M. Hochman and P. Vanier, Turing degree spectra of minimal subshifts, Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017,154–161.
doi: 10.1007/978-3-319-58747-9_15.![]() ![]() ![]() |
[6] |
E. Jeandel and P. Vanier, Turing degrees of multidimensional SFTs, Theoretical Computer Science, 505 (2013), 81-92.
doi: 10.1016/j.tcs.2012.08.027.![]() ![]() ![]() |
[7] |
T. Kent and A. Lewis, On the degree spectrum of a $\Pi^0_1$ class, Transactions of the American Mathematical Society, 362 (2010), 5283-5319.
doi: 10.1090/S0002-9947-10-05037-3.![]() ![]() ![]() |
[8] |
M. Lothaire, Algebraic Combinatorics on Words, 2002.
doi: 10.1017/CBO9780511566097.![]() ![]() ![]() |
[9] |
E. McCarthy, Cototal enumeration degrees and their applications to effective mathematics, Proceedings of the American Mathematical Society, 146 (2018), 3541-3552.
doi: 10.1090/proc/13783.![]() ![]() ![]() |
[10] |
J. S. Miller, Two notes on subshifts, Proceedings of the American Mathematical Society, 140 (2012), 1617-1622.
doi: 10.1090/S0002-9939-2011-11000-1.![]() ![]() ![]() |
[11] |
H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press Cambridge, MA, USA, 1987.
![]() ![]() |
[12] |
P. Walters, An Introduction to Ergodic Theory, Graduate Texts in Mathematics, 79, Springer, 1982.
![]() ![]() |