2019/03/11 by Ronnie Pavlov, Pavlov, Ronnie, Pascal Vanier +1
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.CC #cs.DM #cs.FL #math.DS
paper · pdf · doi:10.48550/arxiv.1903.04325
arxiv created 2019/03/11 · arxiv updated 2019/03/12
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 0 or is a union of cones is realizable by subshifts with a wide range of 'intermediate' complexity growth rates between linear and exponential.