Two notes on subshifts

Source abstract

We prove two unrelated results about subshifts. First, we give a condition on the lengths of forbidden words that is sufficient to guarantee that the corresponding subshift is nonempty. The condition implies that, for example, any sequence of binary words of lengths 5 , 6 , 7 , … 5,6,7,\dots is avoidable. As another application, we derive a result of Durand, Levin and Shen that there are infinite sequences such that every substring has high Kolmogorov complexity. In particular, for any d > 1 d>1 , there is a b ∈ N b\in \mathbb {N} and an infinite binary sequence X X such that if τ \tau is a substring of X X , then τ \tau has Kolmogorov complexity greater than d | τ | − b d\,|\tau |-b . The second result says that from the standpoint of computability theory, any behavior possible from an arbitrary effectively closed subset of n N n^{\mathbb {N}} (i.e., a Π 1 0 \Pi ^0_1 class) is exhibited by an effectively closed subshift. In technical terms, every Π 1 0 \Pi ^0_1 Medvedev degree contains a Π 1 0 \Pi ^0_1 subshift. This answers a question of Simpson.