Two notes on subshifts

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,\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$, there is a $b\in \mathbb {N}$ and an infinite binary sequence $X$ such that if $\tau$ is a substring of $X$, then $\tau$ has Kolmogorov complexity greater than $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^{\mathbb {N}}$ (i.e., a $\Pi ^0_1$ class) is exhibited by an effectively closed subshift. In technical terms, every $\Pi ^0_1$ Medvedev degree contains a $\Pi ^0_1$ subshift. This answers a question of Simpson.