Forbidden substrings, Kolmogorov complexity and almost periodic sequences

Andrey Rumyantsev, Maxim Ushakov

Assume that for some $\alpha <1$ and for all nutural $n$ a set $F_n$ of at most $2^{\alpha n}$ "forbidden" binary strings of length $n$ is fixed. Then there exists an infinite binary sequence…