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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="5 comma 6 comma 7 comma ellipsis"> <mml:semantics> <mml:mrow> <mml:mn>5</mml:mn> <mml:mo>,</mml:mo> <mml:mn>6</mml:mn> <mml:mo>,</mml:mo> <mml:mn>7</mml:mn> <mml:mo>,</mml:mo> <mml:mo> … </mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">5,6,7,\dots</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d greater-than 1"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">d&gt;1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , there is a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="b element-of double-struck upper N"> <mml:semantics> <mml:mrow> <mml:mi>b</mml:mi> <mml:mo> ∈ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">N</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">b\in \mathbb {N}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and an infinite binary sequence <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="tau"> <mml:semantics> <mml:mi> τ </mml:mi> <mml:annotation encoding="application/x-tex">\tau</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a substring of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="tau"> <mml:semantics> <mml:mi> τ </mml:mi> <mml:annotation encoding="application/x-tex">\tau</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has Kolmogorov complexity greater than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d StartAbsoluteValue tau EndAbsoluteValue minus b"> <mml:semantics> <mml:mrow> <mml:mi>d</mml:mi> <mml:mspace width="thinmathspace"/> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi> τ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mo> − </mml:mo> <mml:mi>b</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">d\,|\tau |-b</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The second result says that from the standpoint of computability theory, any behavior possible from an arbitrary effectively closed subset of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n Superscript double-struck upper N"> <mml:semantics> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">N</mml:mi> </mml:mrow> </mml:mrow> </mml:msup> <mml:annotation encoding="application/x-tex">n^{\mathbb {N}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> (i.e., a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Pi 1 Superscript 0"> <mml:semantics> <mml:msubsup> <mml:mi mathvariant="normal"> Π </mml:mi> <mml:mn>1</mml:mn> <mml:mn>0</mml:mn> </mml:msubsup> <mml:annotation encoding="application/x-tex">\Pi ^0_1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> class) is exhibited by an effectively closed subshift. In technical terms, every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Pi 1 Superscript 0"> <mml:semantics> <mml:msubsup> <mml:mi mathvariant="normal"> Π </mml:mi> <mml:mn>1</mml:mn> <mml:mn>0</mml:mn> </mml:msubsup> <mml:annotation encoding="application/x-tex">\Pi ^0_1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> Medvedev degree contains a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Pi 1 Superscript 0"> <mml:semantics> <mml:msubsup> <mml:mi mathvariant="normal"> Π </mml:mi> <mml:mn>1</mml:mn> <mml:mn>0</mml:mn> </mml:msubsup> <mml:annotation encoding="application/x-tex">\Pi ^0_1</mml:annotation> </mml:semantics>